Pagini recente » Cod sursa (job #2615786) | Cod sursa (job #2848711) | Cod sursa (job #510075) | Cod sursa (job #2909548) | Cod sursa (job #662190)
Cod sursa(job #662190)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
#define NM 100005
#define PB push_back
vector <int> G[NM], B[NM];
int N, M, Bdim, viz[NM], L[NM], how_high[NM], stiva[NM], stivadim;
void adauga(int nod)
{
++Bdim;
while (stiva[stivadim] != nod)
{
B[Bdim].PB(stiva[stivadim]);
--stivadim;
}
B[Bdim].PB(nod);
--stivadim;
}
void dfs(int nod, int fat)
{
viz[nod] = 1;
stiva[++stivadim] = nod;
L[nod] = L[fat] + 1;
how_high[nod] = L[nod];
int mlev = L[nod];
for (int i = 0; i < G[nod].size(); ++i)
{
int nnod = G[nod][i];
if (viz[nnod])
{
mlev = min(mlev, L[nnod]);
continue;
}
dfs(nnod, nod);
how_high[nod] = min(how_high[nod], how_high[nnod]);
if (how_high[nnod] < L[nod]) continue;
adauga(nnod);
B[Bdim].PB(nod);
}
how_high[nod] = min(how_high[nod], mlev);
}
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);
}
dfs(1, 0);
/*
for (int i = 1; i <= N; ++i) printf ("%d ", how_high[i]);
printf ("\n");
*/
printf ("%d\n", Bdim);
for (int i = 1; i <= Bdim; ++i)
{
for (int j = 0; j < B[i].size(); ++j) printf ("%d ", B[i][j]);
printf ("\n");
}
return 0;
}