Pagini recente » Cod sursa (job #1709726) | Cod sursa (job #2566074) | Cod sursa (job #3205614) | Cod sursa (job #2861736) | Cod sursa (job #303949)
Cod sursa(job #303949)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define FIN "biconex.in"
#define FOUT "biconex.out"
#define MAX_N 100005
int N, M, L, Res;
vector <int> A[MAX_N], B[MAX_N];
int deg[MAX_N];
int U[MAX_N], Vmin[MAX_N], Niv[MAX_N], T[MAX_N], Mark[MAX_N];
int Sx[MAX_N], Sy[MAX_N];
void DFS(int nod)
{
int i;
U[nod] = 1;
Vmin[nod] = Niv[nod];
for (i = 0; i < deg[nod]; i++)
if (!U[A[nod][i]])
{
Niv[A[nod][i]] = Niv[nod] + 1;
T[A[nod][i]] = nod;
Sx[++L] = nod;
Sy[L] = A[nod][i];
DFS(A[nod][i]);
Vmin[nod] = min(Vmin[nod], Vmin[A[nod][i]]);
if (Vmin[A[nod][i]] >= Niv[nod])
{
++Res;
for (; L >= 0 && (Sx[L + 1] != nod || Sy[L + 1] != A[nod][i]); L--)
{
if (Mark[Sx[L]] != Res)
{
Mark[Sx[L]] = Res;
B[Res].push_back(Sx[L]);
}
if (Mark[Sy[L]] != Res)
{
Mark[Sy[L]] = Res;
B[Res].push_back(Sy[L]);
}
}
}
}
else
if (A[nod][i] != T[nod])
Vmin[nod] = min(Vmin[nod], Niv[A[nod][i]]);
}
int main ()
{
int i, x, y;
freopen (FIN, "r", stdin);
freopen (FOUT, "w", stdout);
scanf ("%d %d", &N, &M);
for (i = 1; i <= M; ++i)
{
scanf ("%d %d", &x, &y);
A[x].push_back(y);
A[y].push_back(x);
}
for (i = 1; i <= N; ++i) deg[i] = A[i].size ();
DFS (1);
printf ("%d\n", Res);
for (i = 1; i <= Res; ++i)
{
x = B[i].size ();
for (int j = 0; j < x; ++j)
printf ("%d ", B[i][j]);
printf ("\n");
}
return 0;
}