Cod sursa(job #383840)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 18 ianuarie 2010 11:25:24
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
#define nmax 100002
using namespace std;
int n,m,nr,st[nmax],viz[nmax];
vector<int> v[nmax];
vector<int> v_t[nmax];
vector<int> sol[nmax];

void dfs(int x)
{
	viz[x]=1;
	int i,lim=v[x].size();
	for(i=0;i<lim;i++)
		if(!viz[v[x][i]])
			dfs(v[x][i]);
	st[++nr]=x;
}

void dfs2(int x)
{
	viz[x]=1;
	sol[nr].push_back(x);
	int i,lim=v_t[x].size();
	for(i=0;i<lim;i++)
		if(!viz[v_t[x][i]])
			dfs2(v_t[x][i]);
}

int main()
{
	freopen("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	scanf("%d%d",&n,&m);
	int i,j,a,b;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&a,&b);
		v[a].push_back(b);
		v_t[b].push_back(a);
	}
	for(i=1;i<=n;i++)
		if(viz[i]==0)
			dfs(i);
	memset(viz,0,sizeof(viz));
//	for(i=1;i<=n;i++)
//		fprintf(stderr,"%d ",st[i]);
	nr=0;
	for(i=n;i>=1;i--)
	{
		if(!viz[st[i]])
		{
			++nr;
			dfs2(st[i]);
		}
	}
	printf("%d\n",nr);
	for(i=1;i<=nr;i++)
	{
		for(j=0;j<sol[i].size();j++)
			printf("%d ",sol[i][j]);
		printf("\n");
	}		
	return 0;
}