Cod sursa(job #613868)

Utilizator alexeiIacob Radu alexei Data 4 octombrie 2011 21:59:55
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include<stdio.h>
#include<vector>
#include<stack>
#include<algorithm>

using namespace std;

#define pb push_back
#define mp make_pair
#define bp pop_back
#define p push

#define NMAX 100010
#define MMAX 200010

vector< int > G[NMAX];
stack< pair<int,int> > S;
vector< int > V[NMAX];

int Level[NMAX],Down[NMAX];
bool viz[NMAX];
int ans;

void scan( int node )
{
	viz[node]=1;
	
	Down[node]=Level[node];
	
	int i,sz=G[node].size();
	for(i=0; i<sz; ++i)
	{
		int v=G[node][i];
		
		if( !viz[v] ) // muchie inainte
		{
			Level[v]=Level[node]+1;
			
			S.push( mp(node,v) );
			
			scan( v );
			
			if( Down[v] >= Level[node] )
			{
				++ans;
				
				while( S.top().first!=node && S.top().second!=v )
				{
					V[ans].pb( S.top().second );
					S.pop();
				}
					
				V[ans].pb( S.top().first );
				V[ans].pb( S.top().second );
				S.pop();
			}
			
			Down[node]=min( Down[node], Down[v] );
		}
		else	// muchie 'inapoi' 
		{
			Down[node]=min( Down[node], Level[v] );
		}
	}
}
	
int main()
{

#ifndef WORK
	freopen("biconex.in","r",stdin);
	freopen("biconex.out","w",stdout);
#endif
	
	int N,M;
	scanf("%d%d",&N,&M);
	
	int a1,a2,i,j,sz;
	for(i=1; i<=M; ++i)
	{
		scanf("%d%d",&a1,&a2);
		G[a1].pb(a2);
		G[a2].pb(a1);
	}

	ans=0;
	
	for(i=1; i<=N; ++i)
	{
		if( !viz[i] )
		{
			Level[i]=1;
			scan( i );
		}
	}

	printf("%d\n",ans);
	
	for(i=1; i<=ans; ++i)
	{
		sz=V[i].size();
		for( j=0; j<sz; ++j )
			printf("%d ",V[i][j]);	
		printf("\n");
	}
	return 0;
}