Pagini recente » Cod sursa (job #103708) | Cod sursa (job #605675) | Cod sursa (job #2362198) | Cod sursa (job #2346566) | Cod sursa (job #669916)
Cod sursa(job #669916)
#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define NM 100005
int N, M, Bdim, L[NM], HH[NM], viz[NM], stack[NM];
vector <int> G[NM], B[NM];
void es (int nod)
{
++Bdim;
while (stack[stack[0]] != nod)
{
B[Bdim].push_back(stack[stack[0]]);
--stack[0];
}
--stack[0];
B[Bdim].push_back(nod);
}
void df (int nod, int fat)
{
L[nod] = L[fat] + 1;
HH[nod] = L[nod];
viz[nod] = 1;
stack[++stack[0]] = nod;
for (int i = 0; i < G[nod].size(); ++i)
{
int nnod = G[nod][i];
if (viz[nnod])
{
HH[nod] = min(HH[nod], L[nnod]);
continue;
}
df (nnod, nod);
HH[nod] = min(HH[nod], HH[nnod]);
if (HH[nnod] < L[nod]) continue;
es(nnod);
B[Bdim].push_back(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].push_back(b);
G[b].push_back(a);
}
df (1, 0);
printf ("%d\n", Bdim);
for (int i = 1; i <= Bdim; ++i)
{
//printf ("%d\n", B[i].size());
for (int j = 0; j < B[i].size(); ++j) printf ("%d ", B[i][j]);
printf ("\n");
}
return 0;
}