Cod sursa(job #398233)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 18 februarie 2010 11:50:17
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include<stdio.h>
#include<stack>
#include<vector>
#define Nmax 100010
using namespace std;

int n,m,i,ctc,lowlink[Nmax],viz[Nmax],x,y,index[Nmax],idx,j;

vector <int> G[Nmax],Sol[Nmax];
stack <int> S;

void tarjan (int nod)
{
	viz[nod]=1;
	index[nod]=idx;
	lowlink[nod]=idx;
	++idx;
	
	S.push(nod);
	
	int N=G[nod].size(),i,fiu;
	
	for(i=0;i<N;i++)
	{
		fiu=G[nod][i];
		
		if(!index[fiu])
		{
			tarjan(fiu);
			if(lowlink[nod] > lowlink[fiu]) lowlink[nod]=lowlink[fiu];
		}
		else 
			if(viz[fiu])
				if(lowlink[nod] > lowlink[fiu]) lowlink[nod]=lowlink[fiu];
	}
	
	if(index[nod]==lowlink[nod])
	{
		ctc++;
		do
		{
			N=S.top();
			Sol[ctc].push_back(N);
			viz[N]=0;
			S.pop();
		}
		while(N!=nod);
	}
}

int main()
{
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	
	scanf("%d %d",&n,&m);
	
	for(i=1;i<=m;i++)
	{
		scanf("%d %d",&x,&y);
		G[x].push_back(y);
	}
	
	idx=1;
	
	for(i=1;i<=n;i++)
		if(!index[i]) tarjan(i);
	
	printf("%d\n",ctc);
		
	for(i=1;i<=ctc;i++)
	{
		m=Sol[i].size();
		
		for(j=0;j<m;j++)
			printf("%d ",Sol[i][j]);
		printf("\n");
	}
	
	return 0;
}