Cod sursa(job #432470)

Utilizator GotenAmza Catalin Goten Data 2 aprilie 2010 13:37:31
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include<fstream>
#include<vector>
#include<iostream>
#define nmax 100100
using namespace std;
vector <int> s,v[nmax],sol[nmax];
int acc[nmax],u[nmax],niv[nmax];
int nr,in;
void tarzan(int nod)
{
	acc[nod]=niv[nod]=++in;
	s.push_back(nod);
	u[nod]=1;
	vector <int> :: iterator fiu;
	for(fiu=v[nod].begin();fiu!=v[nod].end();fiu++)
		if(!niv[*fiu])
		{
			tarzan(*fiu);
			if(acc[nod]>acc[*fiu])
				acc[nod]=acc[*fiu];
		}
		else
			if(u[*fiu])
				if(acc[nod]>niv[*fiu])
					acc[nod]=niv[*fiu];
	if(acc[nod]==niv[nod])
	{
		nr++;
		do
		{
			sol[nr].push_back(s.back());
			s.pop_back();
			u[sol[nr].back()]=0;
		}
		while(sol[nr].back()!=nod);
	}
}
int main()
{
	int n,m,x,y,i;
	ifstream read ("ctc.in");
	ofstream write ("ctc.out");
	read>>n>>m;
	while(m--)
	{
		read>>x>>y;
		v[x].push_back(y);
	}
	for(i=1;i<=n;i++)
		if(!niv[i])
			tarzan(i);
	write<<nr<<'\n';
	vector <int> :: iterator fiu;
	for(i=1;i<=nr;i++)
	{
		for(fiu=sol[i].begin();fiu!=sol[i].end();fiu++)
			write<<*fiu<<' ';
		write<<'\n';
	}
	return 0;
}