Pagini recente » Cod sursa (job #3292134) | Cod sursa (job #260697) | Cod sursa (job #3200597) | Cod sursa (job #3232618) | Cod sursa (job #727559)
Cod sursa(job #727559)
#include <cstdio>
#include <set>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
#define NMAX 200050
int LEV[NMAX], LOW[NMAX], T[NMAX], N, M, K, IDX;
vector <int> G[NMAX];
stack < pair <int, int> > S;
set <int> C[NMAX];
void component (int, int), dfs (int), input (), output ();
int main () {
input ();
dfs (1);
output ();
return 0;
}
void dfs (int node) {
int son;
vector <int>::iterator it;
LEV[node] = LOW[node] = ++IDX;
for (it = G[node].begin (); it != G[node].end (); it++) {
son = *it;
if (son != T[node]) {
if (!LEV[son]) {
S.push (make_pair (node, son));
T[son] = node; dfs (son);
LOW[node] = min (LOW[node], LOW[son]);
if (LOW[son] >= LEV[node]) component (node, son);
}
else
LOW[node] = min (LOW[node], LEV[son]);
}
}
}
void component (int x, int y) {
K++; int a, b;
do {
a = S.top ().first; b = S.top ().second; S.pop ();
C[K].insert (a); C[K].insert (b);
}
while (a != x && b != y);
}
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);
printf ("%d\n", K);
for (int i = 1; i <= K; i++) {
for (set <int>::iterator it = C[i].begin (); it != C[i].end (); it++)
printf ("%d ", *it);
printf ("\n");
}
}