Cod sursa(job #530737)

Utilizator Cristy94Buleandra Cristian Cristy94 Data 8 februarie 2011 13:18:04
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include<stdio.h>
#include<vector>
#include<stack>
#include<string>
#define NMAX 100001
using namespace std;
FILE *f=fopen("ctc.in","r");
FILE *g=fopen("ctc.out","w");
int N,M,nr,sol[NMAX],nrs,nr2;
int viz[NMAX];
vector <int> a[NMAX],b[NMAX],sl[NMAX];
stack <int> s;
void df2(int nod){
	viz[nod]=-1;
    sol[++nrs]=nod;
	for(int i=0;i<(int)b[nod].size();++i){
		if(viz[b[nod][i]]!=-1)
			df2(b[nod][i]);
	}	
}
void df(int nod){
	viz[nod]=1;
	for(int i=0;i<(int)a[nod].size();++i){
		if(!viz[a[nod][i]])
			df(a[nod][i]);
	}
	s.push(nod);
}
void afis(){
	nr2++;
	for(int i=1;i<=nrs;++i)
		sl[nr2].push_back(sol[i]);
}
int main(){
	fscanf(f,"%d%d",&N,&M);
	for(int i=1;i<=M;++i)
	{ int x,y;
	  fscanf(f,"%d%d",&x,&y);
	  a[x].push_back(y);
	  b[y].push_back(x);
	}
	for(int i=1;i<=N;++i)
		if(!viz[i]){
			df(i);
		}
	while(! s.empty()){
		int nod=s.top();
		s.pop();
		nrs=0;
		if(viz[nod]!=-1){
		df2(nod);
		afis();
		}		
	}
	fprintf(g,"%d\n",nr2);
	for(int i=1;i<=nr2;++i){
		for(int j=0;j<(int)sl[i].size();++j)
			fprintf(g,"%d ",sl[i][j]);
		fprintf(g,"\n");
	}
return 0;
}