Pagini recente » Cod sursa (job #2773721) | Cod sursa (job #2057883) | Cod sursa (job #172369) | Cod sursa (job #3150940) | Cod sursa (job #552506)
Cod sursa(job #552506)
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;
#define Nmax 100010
#define Mmax 200010
struct muchie {
int x, y;
} S[Mmax];
int n, m, N, nr, x, y;
int Tata[Nmax], Niv[Nmax], low[Nmax];
vector <int> V[Nmax], Sol[Nmax];
void citire () {
int x, y;
scanf ("%d %d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf ("%d %d", &x, &y);
V[x].push_back (y);
V[y].push_back (x);
}
}
void dfs (int nod, int niv) {
Niv[nod] = low[nod] = niv;
for (vector <int>::iterator it = V[nod].begin (); it != V[nod].end (); it++)
if (*it != Tata[nod]) {
if (!Niv[*it] && *it != 1) {
Tata[*it] = nod;
S[++N].x = nod; S[N].y = *it;
dfs (*it, niv + 1);
if (low[*it] >= niv) {
++nr;
do {
x = S[N].x; y = S[N].y;
Sol[nr].push_back (y);
N--;
} while (x != nod || y != *it);
Sol[nr].push_back (x);
}
if (low[nod] > low[*it]) low[nod] = low[*it];
}
else {
if (Niv[*it] < low[nod]) low[nod] = Niv[*it];
}
}
}
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 (1, 0);
printf ("%d\n", nr);
for (i = 1; i <= nr; i++) {
for (vector <int>::iterator it = Sol[i].begin (); it != Sol[i].end (); it++)
printf ("%d ", *it);
printf ("\n");
}
return 0;
}