Cod sursa(job #530731)

Utilizator Cristy94Buleandra Cristian Cristy94 Data 8 februarie 2011 12:59:27
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include<stdio.h>
#include<vector>
#include<queue>
#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];
queue <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]])
			df2(b[nod][i]);
	}	
}
void df(int nod){
	viz[nod]=1;
	s.push(nod);
	for(int i=0;i<(int)a[nod].size();++i){
		if(!viz[a[nod][i]])
			df(a[nod][i]);
	}
}
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);
		}
	memset(viz,0,sizeof(viz));
	while(! s.empty()){
		int nod=s.front();
		s.pop();
		nrs=0;
		if(!viz[nod]){
		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;
}