Pagini recente » Ciorna | Cod sursa (job #615699) | Cod sursa (job #204380) | Cod sursa (job #1997487) | Cod sursa (job #540546)
Cod sursa(job #540546)
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
#define NM 100005
#define PB push_back
vector <int> G[NM], comp[NM];
int N, M, STACK[NM], viz[NM], nr_comp, NIV[NM], NIVB[NM];
void solve (int nod, int tata, int nivel)
{
viz[nod] = 1;
NIVB[nod] = NIV[nod] = nivel;
for (int i = 0; i < G[nod].size(); ++i)
{
int nnod = G[nod][i];
if (nnod == tata) continue;
if (viz[nnod])
{
NIV[nod] = min(NIV[nod], NIVB[nnod]);
continue;
}
STACK[++STACK[0]] = nnod;
solve(nnod, nod, nivel + 1);
NIV[nod] = min(NIV[nod], NIV[nnod]);
if (NIV[nnod] >= nivel)
{
++nr_comp;
while (STACK[STACK[0]] != nnod)
{
comp[nr_comp].PB(STACK[STACK[0]]);
--STACK[0];
}
comp[nr_comp].PB(STACK[STACK[0]]);
--STACK[0];
comp[nr_comp].PB(nod);
}
}
}
int main()
{
freopen ("biconex.in", "r", stdin);
freopen ("biconex.out", "w", stdout);
scanf ("%d %d", &N, &M);
for (int i = 1; i <= M; ++i)
{
int a, b;
scanf ("%d %d", &a, &b);
G[a].PB(b);
G[b].PB(a);
}
G[0].PB(1);
G[1].PB(0);
STACK[++STACK[0]] = 0;
STACK[++STACK[1]] = 1;
solve (1, 0, 1);
printf ("%d\n", nr_comp);
for (int i = 1; i <= nr_comp; ++i)
{
for (int j = 0; j < comp[i].size(); ++j) printf ("%d ", comp[i][j]);
printf ("\n");
}
return 0;
}