Cod sursa(job #895851)

Utilizator paul_gabryelPaul Buda paul_gabryel Data 27 februarie 2013 12:47:20
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb

#include <cstdio>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

const int N = 100001;

stack<pair<int,int> > S;
vector<vector<int> > V;
vector<int> G[N];
int n,m,lvl[N],low[N];

void READ ()
{
	
	ifstream in ("biconex.in");
	
	in>>n>>m;
	
	for( int x,y ; m ; --m )
	{
		in>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	} 
	
}

void BUILD (int x,int y)
{
	
	vector<int> C;
	
	pair<int,int> A;
	
	do{
		A=S.top();
		S.pop();
		C.push_back(A.first);
		C.push_back(A.second);
		}while( A.first != x || A.second != y );
	
	sort(C.begin(),C.end());
	
	V.push_back(C);
	
}

void DFS (int nod,int T,int L)
{
	
	low[nod]=L;
	lvl[nod]=L;
	
	for( vector<int>::iterator it=G[nod].begin() ; it < G[nod].end() ; ++it )
	{
		
		if( *it == T ) 
			continue;
		
		if( lvl[*it] != -1 )
		{
			low[nod]=min(low[nod],lvl[*it]);
			continue;
		}
		
		S.push(make_pair(nod,*it));
		DFS ( *it , nod , L+1 );
		low[nod]=min(low[nod],low[*it]);
		
		if( lvl[nod] <= low[*it] )
			BUILD ( nod , *it );
		
	}
	
}

void SOLVE ()
{
	
	for( int i=1 ; i <= n ; ++i )
		lvl[i]=-1;
		
	DFS ( 1 , 0 , 0 );
	
}

void OUT ()
{
	
	freopen ("biconex.out","w",stdout);
	
	printf("%d",V.size());
	
	for( size_t i=0 ; i < V.size() ; ++i )
	{
		printf("\n%d ",V[i][0]);
		for( vector<int>::iterator it=V[i].begin()+1 ; it < V[i].end() ; ++it )
			if( *it != *(it-1) )
				printf("%d ",*it);
	}
	
}

int main ()
{
	
	READ ();
	SOLVE ();
	OUT ();
	
	return 0;
	
}