Pagini recente » Cod sursa (job #2221774) | Cod sursa (job #1512110) | Cod sursa (job #1172183) | Cod sursa (job #1225748) | Cod sursa (job #1781546)
#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 500005;
int Low[kMaxN], Time[kMaxN], Depth[kMaxN];
vector<int> Stack;
vector<int> G[kMaxN];
vector<vector<int>> BiComps;
void DFS(int node) {
static int timer;
Stack.push_back(node);
Low[node] = Time[node] = ++timer;
for(auto vec : G[node]) {
if(!Time[vec]) {
Depth[vec] = Depth[node] + 1;
DFS(vec);
Low[node] = min(Low[node], Low[vec]);
if(Low[vec] >= Time[node]) {
BiComps.push_back(vector<int>());
auto &To = BiComps.back();
while(true) {
To.push_back(Stack.back());
Stack.pop_back();
if(To.back() == vec)
break;
}
To.push_back(node);
}
} else if(Depth[vec] < Depth[node] - 1) {
Low[node] = min(Low[node], Time[vec]);
}
}
}
int main() {
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
int n, m;
cin >> n >> m;
while(m--) {
int a, b;
cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
DFS(1);
cout << BiComps.size() << endl;
for(auto x : BiComps) {
for(auto y : x)
cout << y << " ";
cout << '\n';
}
return 0;
}