Cod sursa(job #673214)

Utilizator razvan2006razvan brezulianu razvan2006 Data 4 februarie 2012 09:06:13
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
#define pb push_back
int n,m;
vector <int> vec[100003],ctc[100003];
stack <int> s;
int index[100003],lowlink[100003];
bool ok[100003];
int ct,nrctc;
void tarjan(int nod){
	int i,w;
	index[nod]=lowlink[nod]=ct;
	ct++;
	s.push(nod);
	ok[nod] = 1;
	for (i=0; i<vec[nod].size(); i++)
		if (index[vec[nod][i]] == 999999){
			tarjan(vec[nod][i]);
			lowlink[nod] = min(lowlink[nod], lowlink[vec[nod][i]]);
		}
		else
			if (ok[vec[nod][i]] == 1)
				lowlink[nod] = min(lowlink[nod], index[vec[nod][i]]);

	if (index[nod] == lowlink[nod]){
		w = s.top();
		ok[s.top()] = 0;
		s.pop();
	    nrctc++;
		ctc[nrctc].pb(w);
		while (w != nod){
			w = s.top();
			ok[s.top()] = 0;
			s.pop();
			ctc[nrctc].pb(w);
		}
	}
}
int main()
{
	int i,j,x,y;
	ifstream f("ctc.in");
	ofstream g("ctc.out");
	f>>n>>m;
	for (i=1; i<=m; i++) {
		f>>x>>y;
		vec[x].pb(y);
	}
	for (i=1; i<=n; i++)
		index[i] = lowlink[i] = 999999;
 	for (i=1; i<=n; i++)
		if (index[i] == 999999)
			tarjan(i);

	g<<nrctc<<'\n';
	for(i=1;i<=nrctc;i++){
		for (j=0; j<(int)ctc[i].size(); j++)
			g<<ctc[i][j]<<" ";
		g<<'\n';
	}

	return 0;
}