Cod sursa(job #1155100)

Utilizator roxana.istratePoenaru Roxana roxana.istrate Data 26 martie 2014 17:33:23
Problema Componente tare conexe Scor 88
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <stack>
#include <vector>

#define MAX  100000

using namespace std;

int vect[MAX];
int out[MAX], k = 0;
vector<vector<int>> adiacenta;
vector<vector<int>> adiacentaInv;
stack<int> s;
ifstream fin("ctc.in");
ofstream fout("ctc.out");


void dfsRecInv(int v){
	out[k++] = v+1;
	vect[v] = 0;
	for(int i = 0 ; i < adiacentaInv[v].size(); i++){
		int x = adiacentaInv[v].at(i);
		if(vect[x] != 0)
			dfsRecInv(x);
	}
}


void dfsRec(int v){
	vect[v] = 1;
	for(int i = 0 ; i < adiacenta[v].size(); i++){
		int x = adiacenta[v].at(i);
		if(vect[x] != 1)
			dfsRec(x);
	}
	s.push(v);
}

void reverseG(){
	for(int i = 0; i < adiacenta.size(); i++){
		for(int j = 0; j < adiacenta[i].size(); j++){
			adiacentaInv[adiacenta[i].at(j)].push_back(i);
		}
	}

}

void ctc(){
	
	int x;
	int count = 0;
	while(s.size()){
		x = s.top();
		s.pop();
		if(vect[x] != 0){
			dfsRecInv(x);
			k++;
			count++;
		}
	}
	fout << count << "\n"; 
}

int main(){

	int n, m, a, b;
	
	fin >> n >> m;

	vector<int> v;
	for(int i = 0; i < n; i++){
		adiacenta.push_back(v);
		adiacentaInv.push_back(v);
	}

	for(int i = 0; i < m; i++){
		fin >> a >> b;
		adiacenta[--a].push_back(--b);
	}

	for(int i = 0; i < n ; i++){
		if(!vect[i]){
			dfsRec(i);
		}
	}
	reverseG();
	ctc();

	for(int i = 0 ; i < k; i++){
		if(out[i] != 0){
			fout << out[i] << " "; 
		}else{
			fout << "\n";
		}
	}

	return 0;
}