Pagini recente » Cod sursa (job #1713195) | Cod sursa (job #2973767) | Cod sursa (job #666097) | Cod sursa (job #2102335) | Cod sursa (job #851627)
Cod sursa(job #851627)
#include<cstdio>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
const int Nmax = 200001;
int lev[Nmax], low[Nmax], T[Nmax], N, M, K, cnt;
vector<int> G[Nmax];
stack<pair<int, int> > S;
set<int> sol[Nmax];
void component (int x, int y) {
int a, b;
++K;
do {
a = S.top().first; b = S.top().second;
S.pop();
sol[K].insert(a); sol[K].insert(b);
} while(a != x && b != y);
}
void dfs(int node) {
int son;
vector <int>::iterator it;
lev[node] = low[node] = ++cnt;
for(it=G[node].begin(); it!=G[node].end(); it++) {
son = *it;
if(son == T[node])
continue;
if(!lev[son]) {
S.push(make_pair(node, son));
T[son] = node;
dfs(son);
low[node] = min(low[node], low[son]);
if(lev[node]<=low[son])
component(node, son);
}
else
low[node] = min(low[node], lev[son]);
}
}
void input () {
freopen ("biconex.in", "r", stdin);
scanf ("%d %d", &N, &M);
int i, x, y;
for(i=1; i<=M; i++) {
scanf("%d %d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
}
void output () {
freopen ("biconex.out", "w", stdout);
int i;
set<int>:: iterator it;
printf("%d\n", K);
for(i=1; i<=K; i++) {
for(it=sol[i].begin(); it!=sol[i].end(); it++)
printf("%d ", *it);
printf("\n");
}
}
int main () {
input ();
dfs (1);
output ();
return 0;
}