Pagini recente » Cod sursa (job #3289281) | Cod sursa (job #3274717) | Cod sursa (job #3285674) | Cod sursa (job #3262640) | Cod sursa (job #3293762)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
const int N_MAX = 1e5;
int N, M; vector<int> g[1 + N_MAX];
struct defNode {
int depth;
int low;
} infos[1 + N_MAX];
stack<int> S; bool visited[1 + N_MAX];
int k = 0; vector<int> BCC[1 + N_MAX];
void get_bcc (int root, int node) {
k ++;
while (S.top () != node) {
BCC[k].push_back (S.top ());
S.pop ();
}
BCC[k].push_back (node); S.pop ();
BCC[k].push_back (root);
}
void dfs (int root, int p) {
infos[root].low = infos[root].depth = infos[p].depth + 1;
visited[root] = true; S.push (root);
int children = 0;
for (int node : g[root]) {
if (node == p) continue;
if (visited[node]) infos[root].low = min (infos[root].low, infos[node].depth); /// back-edge
else {
children ++;
dfs (node, root);
infos[root].low = min (infos[root].low, infos[node].low);
if (infos[node].low >= infos[root].depth) /// root = art point
get_bcc (root, node);
}
}
}
int main()
{
fin >> N >> M;
for (int i = 1; i <= M; i ++) {
int u, v; fin >> u >> v;
g[u].push_back (v);
g[v].push_back (u);
}
dfs (1, 0);
fout << k << "\n";
for (int i = 1; i <= k; i ++) {
sort (BCC[i].begin (), BCC[i].end ());
for (int x : BCC[i]) fout << x << " ";
fout << "\n";
}
return 0;
}