Cod sursa(job #382486)

Utilizator ConsstantinTabacu Raul Consstantin Data 13 ianuarie 2010 19:29:30
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include<stdio.h>
#include<vector>
#define dim 100010
using namespace std;

vector<int >g[ dim ],t[ dim ], c[ dim ],s;
bool viz[ dim ];
int n,a,b,i,nr,m,N;

void df1(int nod){
int i,n;
n = g[nod].size();
viz[nod] = true;
for(i = 0; i  < n ; i++)
	if(!viz[g[nod][i]])
		df1(g[nod][i]);
N++;
s.push_back(nod);
}

void df2(int nod){
int i,n;
n = t[nod].size();
viz[nod] = 0;

for(i = 0; i<n;i++)
	if(viz[t[nod][i]])
		df2(t[nod][i]);
c[nr].push_back(nod);
}

void afisare(){
int n,i,j;

printf("%d\n",nr);

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


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",&a,&b);
	g[ a ].push_back(b);
	t[ b ].push_back(a);}
	
for(i = 1 ; i <= n ; i++)
	if(!viz[i])
		df1(i);
	
for(i = N-1; i >= 0; i -- )
	
	if(viz[s[i]]){nr++;df2(s[i]);}

afisare();
return 0;}