Cod sursa(job #729880)

Utilizator OwnedCheciches Marius Owned Data 30 martie 2012 17:34:47
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <stack>
#include <vector>
using namespace std;

#define maxn 100001
stack <int> s;
vector <int> a[maxn],comp[maxn];
int ins[maxn],jos[maxn],pos[maxn],p,nc,n,m;

void tarjan(int k){
	pos[k]=p;
	jos[k]=p;
	s.push(k);
	ins[k]=1;
	p++;
	int i,nod;
	for(i=0;i<a[k].size();i++){
		nod=a[k][i];
		if(pos[nod]<0){
			tarjan(nod);
			if(jos[nod]<jos[k])
				jos[k]=jos[nod];}
		else 
			if(ins[nod]&&jos[nod]<jos[k])
				jos[k]=jos[nod];}
	if(pos[k]==jos[k]){
		nc++;
		do{
			nod=s.top();
			comp[nc-1].push_back(nod);
			s.pop();
			ins[nod]=0;}
		while(nod!=k);}}

int main(){
	ifstream f("ctc.in");
	ofstream g("ctc.out");
	f>>n>>m;
	int i,x,y;
	for(i=1;i<=m;i++){
		f>>x>>y;
		a[x].push_back(y);}
	for(i=1;i<=n;i++)
		pos[i]=-1;
	for(i=1;i<=n;i++)
		if(pos[i]<0)
			tarjan(i);
	g<<nc<<"\n";
	for(i=0;i<nc;i++){
		for(x=0;x<comp[i].size();x++)
			g<<comp[i][x]<<" ";
		g<<"\n";}
	f.close();
	g.close();
	return 0;}