Cod sursa(job #549262)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 8 martie 2011 12:19:41
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <cstdio>
#include <vector>

using namespace std;

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

#define nmax 101000

int n,m,a,b,i,viz[nmax],j;
vector<int> G[nmax];
vector<int> Gt[nmax];
vector<int> sol[nmax];
int ord[nmax];
int nr;

void dfs(int nod){
	
	
	if (viz[nod])
		return ;
	
	viz[nod]=1;
	
	vector<int> :: iterator it;
	
	for (it=G[nod].begin();it!=G[nod].end();++it)
		 if (!viz[*it])
		 dfs(*it);
	
	ord[++ord[0]]=nod;
}

void dfst(int nod){
	
	
	if (viz[nod])
		return ;
	
	viz[nod]=1;
	
	sol[nr].push_back(nod);
	
	vector<int> :: iterator it;
	
	for (it=Gt[nod].begin();it!=Gt[nod].end();++it)
		if (!viz[*it]) 
		dfst(*it);
	
	//ord[++ord[0]]=nod;
}

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

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

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

}