Cod sursa(job #556996)

Utilizator Andreid91Ciocan Andrei Andreid91 Data 16 martie 2011 13:38:29
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include<fstream.h>
#include<vector >

using namespace std;

vector <int> v[100005];

int cnt,sw[100005],nr[100005],n,last[100005],number[100005],sol[100005];

void deep (int nod)
{
	vector<int> :: iterator it;
	sw[nod]=1;
	for (it=v[nod].begin();it<v[nod].end();++it)
		if (sw[*it]==0)
			deep(*it);
		
	last[++cnt]=nod;
}

void build (int nod)
{
	vector<int> :: iterator it;
	nr[nod]=cnt;
	number[cnt]++;
	sol[number[cnt]]=nod;
	for (it=v[nod].begin();it<v[nod].end();++it)
		if (nr[*it]==0)
			build (*it);
}
	

void solve()
{
	int i;
	
	cnt=0;
	
	for (i=1;i<=n;i++)
		if (sw[i]==0)
			deep(i);
	
	cnt=0;
	for (i=1;i<=n;i++)
		if (nr[last[i]]==0)
		{
			cnt++;
			number[cnt]=number[cnt-1];
			build(last[i]);
		}
}

void afisare ()
{
	int i,j;
	ofstream g("ctc.out");
	g<<cnt<<'\n';
	for (i=1;i<=cnt;i++)
	{
		for (j=number[i-1]+1;j<=number[i];++j)
			g<<sol[j]<<' ';
		g<<'\n';
	}
	g.close();
}

void citire ()
{
	int i,m,x,y;
	ifstream f ("ctc.in");
	f>>n>>m;
	for (i=1;i<=m;i++)
	{
		f>>x>>y;
		v[x].push_back(y);
	}
	f.close();
}

int main()
{
	citire();
	solve ();
	afisare();
	return 0;
}