Cod sursa(job #389574)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 1 februarie 2010 20:54:43
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <cstdio>
#include <vector>

using namespace std;

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

#define Nmax 101010

int n,m,ord[Nmax],sol,nr,viz[Nmax];
vector<int> G1[Nmax],G2[Nmax],v[Nmax];

void dfs(int nod)
{
	
	if (viz[nod]==1)
		return ;
	viz[nod]=1;
	
	for (int i=0;i<G1[nod].size();++i)
		 if (!viz[G1[nod][i]])
			 dfs(G1[nod][i]);
	
	ord[++nr]=nod;
}

void dfs2(int nod)
{
	if (viz[nod]==1)
		return ;
	v[sol].push_back(nod);
	viz[nod]=1;
	
	for (int i=0;i<G2[nod].size();++i)
		 if (!viz[G2[nod][i]])
			 dfs2(G2[nod][i]);
}




int main()
{
	int i,a,b,j;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d", &n, &m);
	
	for (i=1;i<=m;++i)
	{
		scanf("%d %d", &a, &b);
		
		G1[a].push_back(b);
		G2[b].push_back(a);
	}
	
	memset(viz,0,sizeof(viz));
	nr=0;
	for (i=1;i<=n;++i)
	     if (!viz[i])
			 dfs(i);
	memset(viz,0,sizeof(viz));	 
    sol=0;	
	for (i=n;i>=1;--i)
    	if (!viz[ord[i]])
	    {
		    sol++;
		    dfs2(ord[i]);
	    }
	
	printf("%d\n", sol);
	for (i=1;i<=nr;++i)
	{
		for (j=0;j<v[i].size();++j)
			 printf("%d ", v[i][j]);
		printf("\n");
	}
		 
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}