Pagini recente » Cod sursa (job #2226781) | Cod sursa (job #2623201) | Cod sursa (job #1843888) | Cod sursa (job #2838276) | Cod sursa (job #431422)
Cod sursa(job #431422)
#include <cstdio>
#include <vector>
#include <list>
#include <stack>
using namespace std;
#define Nmax 100010
#define Mmax 200010
int n, m, nr_comp;
int Niv[Nmax], low[Nmax];
vector <int> V[Nmax];
list <int> Sol[Mmax];
stack <int> S;
void citire () {
int i, x, y;
scanf ("%d %d", &n, &m);
for (i = 1; i <= m; i++) {
scanf ("%d %d", &x, &y);
V[x].push_back (y);
V[y].push_back (x);
}
}
void biconex (int x, int y) {
int xx, yy;
do {
yy = S.top (); S.pop ();
xx = S.top (); S.pop ();
Sol[nr_comp].push_front (yy);
//Sol[nr_comp].push_front (xx);
} while (x != xx || y != yy);
Sol[nr_comp].push_front (xx);
}
void dfs (int nod, int niv, int tata) {
Niv[nod] = low[nod] = niv;
for (vector <int>::iterator it = V[nod].begin (); it != V[nod].end (); it++)
if (*it != tata) {
if ( !Niv [*it] ) {
S.push (nod); S.push (*it);
dfs (*it, niv + 1, nod);
if (low[*it] < low[nod]) low[nod] = low[*it];
if (low[*it] >= niv)
nr_comp++, biconex (nod, *it);
}
else
if (Niv[*it] < low[nod]) low[nod] = Niv[*it];
}
}
void afisare () {
printf ("%d\n", nr_comp);
for (int i = 1; i <= nr_comp; i++) {
for (list <int>::iterator it = Sol[i].begin (); it != Sol[i].end (); it++)
printf ("%d ", *it);
printf ("\n");
}
}
int main () {
freopen ("biconex.in", "r", stdin);
freopen ("biconex.out", "w", stdout);
citire ();
int i;
for (i = 1; i <= n; i++)
if (!Niv[i]) dfs (i, 1, 0);
afisare ();
return 0;
}