Cod sursa(job #530302)

Utilizator mottyMatei-Dan Epure motty Data 7 februarie 2011 14:42:37
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.87 kb
#include <cstdio>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

const int N=100001, M=200002;

struct edge{
	int a, b;
};

edge stivie[M];

bool viz[N];

int n, m, stPos, up[N], lev[N], padre[N], result;

vector <int> graph[N];
vector <int> results[N];

void Read()
{
	int a, b;
	scanf("%d%d",&n,&m);
	
	for( int i=1; i<=m; ++i)
	{
		scanf("%d%d",&a,&b);
		
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
}

void Dfs(int nod)
{
	viz[nod] = 1;
	up[nod] = lev[nod];
	
	for( int i=0; i<graph[nod].size(); ++i)
		if(!viz[graph[nod][i]])
		{
			lev[graph[nod][i]]=lev[nod]+1;
			padre[graph[nod][i]]=nod;
			
			stivie[++stPos].a=nod;
			stivie[stPos].b=graph[nod][i];
			
			Dfs(graph[nod][i]);
			
			if(up[graph[nod][i]]<up[nod])
				up[nod]=up[graph[nod][i]];
			
			if(up[graph[nod][i]]>=lev[nod])
			{
				result++;
				while(stivie[stPos].a!=nod || stivie[stPos].b!=graph[nod][i])
				{
					results[result].push_back(stivie[stPos].a);
					results[result].push_back(stivie[stPos].b);
					stPos--;
				}
				
				results[result].push_back(nod);
				results[result].push_back(graph[nod][i]);
				stPos--;
			}
		}
		else if( padre[nod]!=graph[nod][i] && lev[graph[nod][i]]<lev[nod] )
		{
			if(up[nod]>lev[graph[nod][i]])
				up[nod]=lev[graph[nod][i]];
			
			stivie[++stPos].a=nod;
			stivie[stPos].b=graph[nod][i];
		}
}

void Print()
{
	printf("%d\n",result);
	
	for( int i=1; i<=result; ++i)
	{
		sort( results[i].begin(), results[i].end());
		results[i].resize( unique( results[i].begin(), results[i].end()) - results[i].begin() );
		
		for( int j=0; j<results[i].size(); ++j)
			printf("%d ",results[i][j]);
		
		printf("\n");
	}
}

int main()
{
	freopen("biconex.in","r",stdin);
	freopen("biconex.out","w",stdout);
	
	Read();
	Dfs(1);
	Print();
	
	return 0;
}