Cod sursa(job #633962)

Utilizator paul24090FMI - Balauru Paul paul24090 Data 15 noiembrie 2011 10:53:32
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <cstdio>
#include <list>
#include <stack>

using namespace std;

const int MAX_N = 100005;

int n,m;
bool v[MAX_N];
list<int> l[MAX_N];
list<int> lt[MAX_N];
int st[MAX_N],nst;
list<int> ctc[MAX_N];
int nrCtc;

void DF1(int nod)
{
	v[nod] = true;
	list<int>::iterator it;
	
	for(it = l[nod].begin(); it != l[nod].end(); ++it)
		if(v[*it] == false)
			DF1(*it);
	st[++nst] = nod;
}

void DF2(int nod)
{
	v[nod] = true;
	list<int>::iterator it;
	
	ctc[nrCtc].push_back(nod);
	
	for(it = lt[nod].begin(); it != lt[nod].end(); ++it)
		if(v[*it] == false)
			DF2(*it);
}

int main()
{
	FILE* fp;
	int i,x,y,abc;
	
	fp = freopen("ctc.in","rt",stdin);
	fp = freopen("ctc.out","wt",stdout);
	
	abc = scanf("%d %d",&n,&m);
	for(i=1;i<=m;++i)
	{
		abc = scanf("%d %d",&x,&y);
		l[x].push_back(y);
		lt[y].push_back(x);
	}
	
	nrCtc = 0;
	
	for(i=1;i<=n;i++)
		if(v[i]==false)
			DF1(i);
	for(i=1;i<=n;i++)
		v[i]=false;
	for(i=n;i>=1;i--)
		if(v[st[i]]==false)
		{
			nrCtc++;
			DF2(st[i]);
		}
	printf("%d\n",nrCtc);
	list<int>::iterator it;
	for(i=1;i<=nrCtc;i++)
	{
		for(it = ctc[i].begin(); it != ctc[i].end(); ++it)
			printf("%d ",*it);
		printf("\n");
	}		
	return 0;
}