Cod sursa(job #797249)

Utilizator mihaibogdan10Mihai Bogdan mihaibogdan10 Data 13 octombrie 2012 17:32:16
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include<fstream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
ifstream fin("ctc.in"); ofstream fout("ctc.out");

int n, m, index, nrComp, entry_time[100001], compCurenta[100001];
vector <int> G[100001], lowlink(100001, 200001), sol[100001];
stack<int> S;

void SCC(int nod){
	int i, adj;
	
	S.push(nod);
	lowlink[nod] = entry_time[nod] = ++index;
	compCurenta[nod] = 1;
	
	for (i = 0; i < (int) G[nod].size(); i++){
		adj = G[nod][i];
		
		if (entry_time[adj] == 0) {
			SCC( adj );
			lowlink[nod] = min (lowlink[adj], lowlink[nod]);
		}
		//daca un nod e in S, e in componenta tare conexa curenta.
		else if (compCurenta[adj] == 1)
			lowlink[nod] = min (entry_time[adj], lowlink[nod]);
	}
	
	if (lowlink[nod] == entry_time[nod]){
		nrComp++;
		do {
			adj = S.top(), S.pop();
			compCurenta[adj] = 0;
			sol[nrComp].push_back(adj);
		}
		while (nod != adj);
	}
}

int main(){
	int i, x, y;
	
	fin >> n >> m;
	for (i = 0; i < m; i++) {
		fin >> x >> y;
		G[x].push_back(y);
	}
	
	for (i = 1; i <= n ; i++)
		if (!entry_time[i]) SCC(i);
	
	fout << nrComp << "\n";
	for (int i = 1; i <= nrComp; i++){
		for (int j = 0; j < sol[i].size(); j++) fout << sol[i][j] << " ";
		fout << "\n";
	}
}