Cod sursa(job #897033)

Utilizator deividFlorentin Dumitru deivid Data 27 februarie 2013 18:35:01
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include<stdio.h>
#include<vector>

#define maxn 100005

using namespace std;

FILE*f=fopen("ctc.in","r");
FILE*g=fopen("ctc.out","w");

int n,m,ctc;
int st[maxn],viz[maxn];
vector<int>G[maxn],Gt[maxn],C[maxn];

void dfp ( int nod ){
	viz[nod] = 1;
	
	for ( vector<int>::iterator itt = G[nod].begin() ; itt != G[nod].end() ; ++itt ){
		int vecin = (*itt);
		if ( !viz[vecin] ){
			dfp(vecin);
		}
	}
	
	st[++st[0]] = nod;
}

void dfm ( int nod ){
	viz[nod] = 0; C[ctc].push_back(nod);
	
	for ( vector<int>::iterator itt = Gt[nod].begin() ; itt != Gt[nod].end() ; ++itt ){
		int vecin = (*itt);
		if ( viz[vecin] ){
			dfm(vecin);
		}
	}
}

int main () {
	
	fscanf(f,"%d %d",&n,&m);
	int x,y;
	for ( int i = 1 ; i <= m ; ++i ){
		fscanf(f,"%d %d",&x,&y);
		G[x].push_back(y);
		Gt[y].push_back(x);
	}
	
	for ( int i = 1 ; i <= n ; ++i ){
		if ( !viz[i] ){
			dfp(i);
		}
	}
	
	for ( int i = n ; i >= 1 ; --i ){
		if ( viz[st[i]] ){
			++ctc;
			dfm(st[i]);
		}
	}
	
	fprintf(g,"%d\n",ctc);
	for ( int i = 1 ; i <= ctc ; ++i ){
		for ( int j = 0 ; j < C[i].size() ; ++j ){
			fprintf(g,"%d ",C[i][j]);
		}
		fprintf(g,"\n");
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}