Cod sursa(job #283823)

Utilizator katakunaCazacu Alexandru katakuna Data 19 martie 2009 22:21:23
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include<stdio.h>
#define nmax 100111

struct nod { int inf; nod *urm;} *v1[nmax], *v2[nmax], *sol[nmax];
int n, m, x, y, i, viz[nmax], st[nmax], u, nrctc;


void citire(){
	
	FILE *f = fopen("ctc.in", "r");
	
	fscanf(f,"%d %d",&n,&m);
	for(i=1; i<=m; i++){
		fscanf(f,"%d %d",&x,&y);
		nod *p = new nod; p->inf = y; p->urm = v1[x]; v1[x] = p;
		nod *q = new nod; q->inf = x; q->urm = v2[y]; v2[y] = q;
	}
	
	fclose(f);
}

void DFS1(int nc){

	viz[nc] = 1;
	nod *p;
	for(p = v1[nc]; p != NULL; p = p->urm)
		if( !viz[ p->inf ] )
			DFS1( p->inf );
	
	st[++u] = nc;

}

void DFS2(int nc){

	viz[nc] = 2;
	nod *q = new nod;
	q->inf = nc; q->urm = sol[nrctc]; sol[nrctc] = q;
	
	nod *p;
	for( p = v2[nc]; p != NULL; p = p->urm )
		if( viz[ p->inf ] != 2 )
			DFS2(p->inf);
	
}

void solve(){

	int i;
	for(i=1; i<=n; i++)
		if( !viz[i] )
			DFS1(i);
	
	for(i=n; i>=1; i--)
		if( viz[st[i]] != 2 ){
			nrctc++;
			DFS2(st[i]);
		}
	
	
}

void afisare(){

	nod *p;
	FILE *g = fopen("ctc.out","w");
	
	fprintf(g,"%d\n",nrctc);
	for(i=1; i<=nrctc; i++){
		for(p = sol[i]; p != NULL; p = p->urm)
			fprintf(g,"%d ",p->inf);
		
		fprintf(g,"\n");
	}
	
	fclose(g);
}


int main(){

	citire();
	solve();
	afisare();

	return 0;

}