Pagini recente » Cod sursa (job #2835364) | Cod sursa (job #2335419)
#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;
scanf("%d%d", &n, &m);
for(int i = 0; i < m; ++i) {
int a, b;
scanf("%d%d", &a, &b);
gr[a].emplace_back(b);
gr[b].emplace_back(a);
}
dfs(1, 1);
printf("%d\n", cntBiconexe);
for(int i = 0; i < cntBiconexe; ++i) {
for(auto &x : sol[i]) {
printf("%d ", x);
}
printf("\n");
}
}