Pagini recente » Cod sursa (job #1919315) | Cod sursa (job #2577321) | Cod sursa (job #1235008) | Cod sursa (job #2636224) | Cod sursa (job #2335418)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
vector< int > gr[MAXN];
int minim[MAXN], level[MAXN];
stack< pair< int, int > > edges;
int cntBiconexe = 0;
vector< int > sol[MAXN];
void get(int x, int y) {
int nowX = 0, nowY = 0;
do{
tie(nowX, nowY) = edges.top();
edges.pop();
sol[cntBiconexe].emplace_back(nowX);
sol[cntBiconexe].emplace_back(nowY);
} while(nowX != x || nowY != y);
sort(sol[cntBiconexe].begin(), sol[cntBiconexe].end());
sol[cntBiconexe].erase(unique(sol[cntBiconexe].begin(), sol[cntBiconexe].end()), sol[cntBiconexe].end());
++cntBiconexe;
}
void dfs(int node, int d) {
minim[node] = level[node] = d;
for(auto &x : gr[node]) {
if(!level[x]) {
edges.push(make_pair(node, x));
dfs(x, d + 1);
if(minim[x] >= level[node]) {
get(node, x);
}
minim[node] = min(minim[node], minim[x]);
} else minim[node] = min(minim[node], level[x]);
}
}
int main() {
#ifdef BLAT
freopen("input", "r", stdin);
#else
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
#endif
int n, m;
cin >> n >> m;
for(int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
gr[a].emplace_back(b);
gr[b].emplace_back(a);
}
dfs(1, 1);
cout << cntBiconexe << '\n';
for(int i = 0; i < cntBiconexe; ++i) {
for(auto &x : sol[i]) {
cout << x << ' ';
}
cout << '\n';
}
}