Cod sursa(job #284089)

Utilizator katakunaCazacu Alexandru katakuna Data 20 martie 2009 23:02:51
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

int n, m, i, x, y, nrctc, nivel;
vector <int> v[100111], sol[100111];
stack <int> S;
int viz[100111], low[100111], niv[100111], in_stack[100111];

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);
		v[x].push_back(y);
	}
	
	fclose(f);
}

void DFS(int nod){

	nivel++;
	low[nod] = niv[nod] = nivel;
	vector <int>::iterator it;
	S.push(nod); in_stack[nod] = 1;
	
	for(it = v[nod].begin(); it != v[nod].end(); it++){
		if( niv[*it] && !in_stack[*it] ) continue;
		
		if( !niv[*it] ){
			DFS(*it);
			low[nod] = min(low[nod], low[*it]);
		}
		
		else
			low[nod] = min(low[nod], low[*it]);
	}
	
	if( niv[nod] == low[nod] ){
		nrctc++;
		do{
			x = S.top();
			S.pop();
			sol[nrctc].push_back(x);
			in_stack[x] = 0;
		} while( x != nod );
	}
	
}

void solve(){

	for(i=1; i<=n; i++)
		if( !niv[i] )
			DFS(i);

}

void afisare(){

	vector <int>::iterator it;
	FILE *g = fopen("ctc.out", "w");
	
	fprintf(g,"%d\n",nrctc);
	for(i = 1; i <= nrctc; i++){
		for(it = sol[i].begin(); it != sol[i].end(); it++)
			fprintf(g,"%d ",*it);
		
		fprintf(g,"\n");
	}
	
	fclose(g);
}

int main(){

	citire();
	solve();
	afisare();
	
	return 0;
}