Pagini recente » Cod sursa (job #1775713) | Cod sursa (job #2953035) | Cod sursa (job #3126305) | Cod sursa (job #374562) | Cod sursa (job #3226672)
#include <bits/stdc++.h>
using namespace std;
ifstream in ("biconex.in");
ofstream out ("biconex.out");
const int V_MAX = 1e5;
const int E_MAX = 2e5;
int V, E;
vector<int> g[1 + V_MAX];
void readInput (void) {
in >> V >> E;
for (int i = 1; i <= E; i ++) {
int a, b; in >> a >> b;
g[a].push_back (b);
g[b].push_back (a);
}
}
struct defNode {
int depth, low;
bool visited;
} infos[1 + V_MAX];
stack<int> stk;
int k; vector<int> BCC[1 + V_MAX];
void dfs (int root, int p) {
infos[root].visited = true;
infos[root].low = infos[root].depth = infos[p].depth + 1;
stk.push (root);
for (int node : g[root]) {
if (!infos[node].visited) {
dfs (node, root);
infos[root].low = min (infos[root].low, infos[node].low);
if (infos[node].low >= infos[root].depth) {
k ++;
while (stk.top () != root) {
BCC[k].push_back (stk.top ());
stk.pop ();
}
BCC[k].push_back (root);
}
}
else
infos[root].low = min (infos[root].low, infos[node].depth);
}
}
int main()
{
readInput ();
dfs (1, 0);
out << k << " ";
for (int i = 1; i <= k; i ++) {
sort (BCC[i].begin (), BCC[i].end ());
for (int x : BCC[i])
out << x << " ";
out << "\n";
}
return 0;
}