Pagini recente » Cod sursa (job #1033617) | Cod sursa (job #1310257) | Cod sursa (job #784212) | Cod sursa (job #3187519) | Cod sursa (job #731688)
Cod sursa(job #731688)
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#define NMax 100000
#define x first
#define y second
using namespace std;
vector <int> G[NMax], T[NMax], CV;
vector < vector <int> > BC;
int N, S, E, Q;
int Level[NMax], MinLevel[NMax];
stack < pair <int, int> > Edges;
inline void DetBC (int X, int Y)
{
vector <int> Component;
int NewX, NewY;
do
{
NewX=Edges.top ().x, NewY=Edges.top ().y;
Edges.pop ();
Component.push_back (NewX); Component.push_back (NewY);
}
while (NewX!=X or NewY!=Y);
sort (Component.begin (), Component.end ());
Component.erase (unique (Component.begin (), Component.end ()), Component.end ());
BC.push_back (Component);
}
inline void ComponentDFS (int X, int Father, int L)
{
Level[X]=MinLevel[X]=L;
int NSons=0; bool Critical=false;
for (vector <int> :: iterator Y=G[X].begin (); Y!=G[X].end (); ++Y)
{
if (*Y==Father) continue;
if (!Level[*Y])
{
++NSons; Edges.push (make_pair (X, *Y));
ComponentDFS (*Y, X, L+1);
if (MinLevel[*Y]>=Level[X])
{
Critical=true; DetBC (X, *Y);
}
}
MinLevel[X]=min (MinLevel[X], MinLevel[*Y]);
}
if (X==Father and NSons>1) Critical=true;
if (Critical) CV.push_back (X);
}
void BuildBC ()
{
for (int i=1; i<=N; ++i)
{
if (!Level[i]) ComponentDFS (i, i, 1);
}
}
void Solve ()
{
BuildBC ();
}
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);
}
scanf ("%d %d %d", &S, &E, &Q);
}
void Print ()
{
freopen ("biconex.out", "w", stdout);
printf ("%d\n", (int)BC.size ());
for (int i=0; i<(int)BC.size (); ++i)
{
for (int j=0; j<(int)BC[i].size (); ++j)
{
printf ("%d ", BC[i][j]);
}
printf ("\n");
}
}
int main()
{
Read ();
Solve ();
Print ();
return 0;
}