Cod sursa(job #409468)

Utilizator socheoSorodoc Ionut socheo Data 3 martie 2010 18:04:28
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;

vector <int> gp[100002],gm[100002],g[100002];
int n,m,i;
vector <int> tr;
vector <int> viz,d;
void read()
{	int q,w;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{	scanf("%d%d",&q,&w);
		gp[q].push_back(w);
		gm[w].push_back(q);
	}
}

void dfplus(int nod)
{   viz[nod]=1;
	for(vector <int>::iterator it=gp[nod].begin();it!=gp[nod].end();it++)
		if(viz[*it]==0)
			dfplus(*it);
	d.push_back(nod);
}

void dfminus(int nod,int nr)
{ tr[nod]=nr;
  for(vector<int>::iterator it=gm[nod].begin();it!=gm[nod].end();it++)
	  if(tr[*it]==0)
		  dfminus(*it,nr);
}

int main()
{	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	read();
	viz.resize(n+1);
	for(i=1;i<=n;i++)
		if(viz[i]==0)
			dfplus(i);
	int nr=1;
	tr.resize(n+1);
	while(d.size()!=0)
	{	if(tr[d.back()]==0)
			{dfminus(d.back(),nr);
			nr++;
			}
		d.pop_back();
	}
	for(i=1;i<=n;i++)
		g[tr[i]].push_back(i);
	nr--;
	printf("%d\n",nr);
	for(i=1;i<=nr;i++)
	{	for(vector<int>::iterator it=g[i].begin();it!=g[i].end();it++)
				printf("%d ",*it);
	printf("\n");
	}
return 0;
}