Cod sursa(job #366384)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 21 noiembrie 2009 18:04:29
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <cstdio>
#include <vector>

using namespace std;

#define file_in "ctc.in"
#define file_out "ctc.out"

#define Nmax 110010 

int n,m,nr,ord[Nmax],a,b,viz[Nmax];
vector<int> v1[Nmax],v2[Nmax],v3[Nmax];

void dfs1(int nod)
{
	int i;

	viz[nod]=1;
	
	for (i=0;i<v1[nod].size();++i)
		 if (!viz[v1[nod][i]])
			 dfs1(v1[nod][i]);
		 ord[++nr]=nod;
}

void dfs2(int nod)
{
	int i;
	//nr++;
	v3[nr].push_back(nod);
	
	viz[nod]=1;
	
	for (i=0;i<v2[nod].size();++i)
		 if (!viz[v2[nod][i]])
			 dfs2(v2[nod][i]);
		 
}



int main()
{
	int i,j;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d", &n, &m);
	
	while(m--)
	{
		scanf("%d %d", &a, &b);
		
		v1[a].push_back(b);
		v2[b].push_back(a);
	}
	
	memset(viz,0,sizeof(viz));
	
	nr=0;
	for (i=1;i<=n;++i)
		 if (!viz[i])
		 {
			 dfs1(i);
		 }
	

	memset(viz,0,sizeof(viz));

	nr=0;
	for (i=n;i>=1;--i)
		 if (!viz[ord[i]])
		 {
           nr++;
		   dfs2(ord[i]);
		 }
		 
	printf("%d\n", nr);

	for (i=1;i<=nr;++i)
	{
		for (j=0;j<v3[i].size();++j)
		       printf("%d ", v3[i][j]);
		printf("\n");
	}
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}