Pagini recente » Cod sursa (job #1589009) | Cod sursa (job #375658) | Cod sursa (job #1349538) | Cod sursa (job #1615770) | Cod sursa (job #555560)
Cod sursa(job #555560)
#include <cstdio>
#include <list>
using namespace std;
#define NMAX 100050
struct muchie {
int x, y;
} S[NMAX];
int T[NMAX], niv[NMAX], low[NMAX], N, nivel, sol, n;
list <int> G[NMAX], B[NMAX];
void citire (), biconex (), DFS (int), componenta (int, int), afisare ();
int main () {
citire ();
biconex ();
afisare ();
return 0;
}
void citire () {
freopen ("biconex.in", "r", stdin);
int m, i, x, y;
scanf ("%d %d\n", &n, &m);
for (i = 1; i <= m; i++) {
scanf ("%d %d", &x, &y);
G[x].push_back (y);
G[y].push_back (x);
}
}
void componenta (int x, int y) {
int i, j;
sol++;
do {
i = S[N].x, j = S[N].y, N--;
B[sol].push_back (j);
} while (i != x && j != y);
B[sol].push_back (x);
}
void DFS (int nod) {
int fiu;
list <int>::iterator it;
nivel++;
niv[nod] = low[nod] = nivel;
for (it = G[nod].begin (); it != G[nod].end (); it++) {
fiu = *it;
if (*it != T[nod]) {
if (!niv[fiu]) {
N++, S[N].x = nod, S[N].y = fiu;
T[fiu] = nod; DFS (fiu);
if (low[fiu] >= niv[nod]) componenta (nod, fiu);
low[nod] = min (low[nod], low[fiu]);
}
else
low[nod] = min (low[nod], niv[fiu]);
}
}
}
void biconex () {
for (int i = 1; i <= n; i++)
if (!niv[i]) DFS (i);
}
void afisare () {
freopen ("biconex.out", "w", stdout);
printf ("%d\n", sol);
for (int i = 1; i <= sol; i++) {
for (list <int>::iterator it = B[i].begin (); it != B[i].end (); it++)
printf ("%d ", *it);
printf ("\n");
}
}