Cod sursa(job #488254)

Utilizator barneystinsonBarney barneystinson Data 28 septembrie 2010 00:22:54
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <cstdio>
#include <vector>
using namespace std;
#define NMAX 100002

int n,m,viz[NMAX],N,S[NMAX],sol;

vector <int> G[NMAX],GT[NMAX],CTC[NMAX];

void read();
void print();
void kosaraju();
void DFS1();
void DFS2();

int main(){
	
	read();
	
	kosaraju();
	
	print();
	
	return 0;
}

void DFS1(int nod){
	
	viz[nod]=1;
	for(int i =0; i< (int) G[nod].size() ; ++i){
		if(!viz[G[nod][i]]){
			DFS1(G[nod][i]);
		}
	}
	
	S[++N]=nod;
	
}

void DFS2(int nod){
	
	viz[nod]=0;
	CTC[sol].push_back(nod);
	for(int i =0; i< (int) GT[nod].size() ; ++i){
		if(viz[GT[nod][i]]){
			DFS2(GT[nod][i]);
		}
	}
	
}

void kosaraju(){
	
	for(int i=1 ; i<=n ; ++i ){
		if(!viz[i]){
			DFS1(i);
		}		
	}
	
	for( ; N>0 ; --N){
		if(viz[S[N]]){
			sol++;
			DFS2(S[N]);
		}
	}
	
}

void read(){
	
	int nod1,nod2;
	freopen("ctc.in", "r", stdin);
	
	scanf("%d %d ", &n, &m);
	
	for(int i=1; i<=m; ++i){
		
		scanf("%d %d ", &nod1, &nod2);
		
		G[nod1].push_back(nod2);
		GT[nod2].push_back(nod1);		
	}
	
}

void print(){
	
	freopen("ctc.out", "w", stdout);
	
	printf("%d \n", sol);
	
	for(int i=1; i<=sol ; ++i){
		for(int j=0; j < (int) CTC[i].size() ; ++j){
			printf("%d ", CTC[i][j]);
		}
		printf("\n");
	}
	
	/*for(int i=1; i<=n ;  ++i){
		for(int j=0 ; j< (int) GT[i].size() ; j++){
			printf("%d ", GT[i][j]);
		}
		printf("\n");
	}*/
	
}