Cod sursa(job #1088777)

Utilizator roby2001Sirius roby2001 Data 20 ianuarie 2014 20:04:22
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
/*
          ~Keep It Simple!~
*/

#include<stdio.h>
#include<list>

#define NMax 100005

using namespace std;

int N,M,idx[NMax],Lowlink[NMax],In_Stack[NMax],indeces;
list<int> G[NMax],S,A;
list< list<int> > Lists;

void StronglyConnectedComponentsInit(int node)
{
	idx[node] = Lowlink[node] = ++indeces;
	In_Stack[node] = 1;
	S.push_back(node);

	for(list<int>::iterator it = G[node].begin(); it!=G[node].end(); it++)
	{
		if(!idx[*it])
		{
			StronglyConnectedComponentsInit(*it);
			Lowlink[node] = min(Lowlink[node],Lowlink[*it]);
		}
		else if(In_Stack[*it])
		{
			Lowlink[node] = min(Lowlink[node],Lowlink[*it]);
		}
	}

	if( idx[node] == Lowlink[node])
	{
		int aux;
		A.clear();
		do
		{
			A.push_back(aux = S.back());
			S.pop_back(); In_Stack[aux] = 0;
		}while(aux != node);
			Lists.push_back(A);
	}
}

int main()
{
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);

	scanf("%d%d",&N,&M);

	int x,y;

	for(int i=1; i<=M; i++)
	{
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
	}

	indeces++;
	for(int i=1; i<=N; i++)
	  if(!idx[i])
	    StronglyConnectedComponentsInit(i);

	printf("%d\n",Lists.size());
	
	for(list<list<int>>::iterator it=Lists.begin(); it!=Lists.end(); it++)
	{
		for(list<int>::iterator j = it->begin(); j!=it->end(); j++)
			printf("%d ", *j);
		printf("\n");
	}
	
}