Pagini recente » Cod sursa (job #482632) | Cod sursa (job #292885) | Cod sursa (job #2246076) | Cod sursa (job #1126589) | Cod sursa (job #604640)
Cod sursa(job #604640)
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#define NMax 100005
using namespace std;
vector <int> G[NMax];
vector < vector <int> > BC;
stack < pair <int, int> > Stack;
int N, Level[NMax], LowestL[NMax];
void Read ()
{
freopen ("biconex.in", "r", stdin);
int M;
scanf ("%d %d", &N, &M);
for (; M>0; --M)
{
int X, Y;
scanf ("%d %d", &X, &Y);
G[X].push_back (Y);
G[Y].push_back (X);
}
}
void Print ()
{
freopen ("biconex.out", "w", stdout);
printf ("%d\n", BC.size ());
for (int i=0; i<BC.size (); ++i)
{
sort (BC[i].begin (), BC[i].end ());
printf ("%d ", BC[i][0]);
for (int j=1; j<BC[i].size (); ++j)
{
if (BC[i][j]!=BC[i][j-1])
{
printf ("%d ", BC[i][j]);
}
}
printf ("\n");
}
}
inline int Min (int a, int b)
{
if (a<b)
{
return a;
}
return b;
}
void DetBC (int X, int Y)
{
int x, y;
vector <int> Component;
do
{
x=Stack.top ().first;
y=Stack.top ().second;
Stack.pop ();
Component.push_back (x);
Component.push_back (y);
}
while (x!=X or y!=Y);
BC.push_back (Component);
}
void DFS (int X, int Father, int L)
{
Level[X]=LowestL[X]=L;
for (unsigned i=0; i<G[X].size (); ++i)
{
int V=G[X][i];
if (V==Father)
{
continue;
}
if (Level[V]==0)
{
Stack.push (make_pair (X, V));
DFS (V, X, L+1);
LowestL[X]=Min (LowestL[X], LowestL[V]);
if (LowestL[V]>=Level[X])
{
DetBC (X, V);
}
}
else
{
LowestL[X]=Min (LowestL[X], LowestL[V]);
}
}
}
int main()
{
Read ();
for (int i=1; i<=N; ++i)
{
if (Level[i]==0)
{
DFS (i, 0, 1);
}
}
Print ();
return 0;
}