Cod sursa(job #410253)

Utilizator miticaMitica mitica Data 4 martie 2010 11:01:47
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <algorithm>
#include <vector>
#include <stack>
#define nmax 100005

using namespace std;

int n,m,i,x,y,k;
vector <int> viz, viz2;
vector <int> G[nmax], Gt[nmax], Gs[nmax];
vector <int>::iterator it;
vector <int> s;

void df(int x)
{
	vector <int>::iterator it;
	viz[x]=true;
	for (it=G[x].begin();it!=G[x].end();++it)
		if (viz[*it]==false)
			df(*it);
	s.push_back(x);
}

void dft(int x)
{
	vector <int>::iterator it;
	viz2[x]=k;
	for (it=Gt[x].begin();it!=Gt[x].end();++it)
		if (viz2[*it]==-1)
			dft(*it);
}

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);
		x --; y --;
		G[x].push_back(y);
		Gt[y].push_back(x);
	}
	viz.resize(n);
	viz.assign(viz.size(),0);
	
	for (i=0;i<n;i++)
		if (viz[i]==false)
			df(i);
	k=0;
	viz2.resize(n);
	viz2.assign(viz2.size(),-1);
	for (; s.size(); s.pop_back())
		if (viz2[s.back()]==-1)
		{
			dft(s.back());
			k++;
		}
	for (i=0;i<n;++i)         
		Gs[viz2[i]].push_back(i); 
	printf("%d\n", k);
	for (i=0;i<k;i++)
	 {
	  for (it=Gs[i].begin();it!=Gs[i].end();++it)
		 printf("%d ", *it+1);
	  printf("\n");
	 }
	return 0;
}