Cod sursa(job #527416)

Utilizator siminescuPaval Cristi Onisim siminescu Data 31 ianuarie 2011 14:19:00
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include<fstream>
#include<vector>
using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

# define nmax 100002
vector <int> v[nmax], vt[nmax],c[nmax];
int N, M, l[nmax], lt[nmax], t[nmax], o[nmax], pas;
bool viz[nmax];

void citire()
{
	f>>N>>M;
	int a, b;
	for(;M;--M)
	{
		f>>a>>b;
		v[a].push_back(b);
		vt[b].push_back(a);
	}
	for(a=1;a<=N;++a)
	{
		l[a]=v[a].size();
		lt[a]=vt[a].size();
	}		
}
void dfv(int nod)
{
	viz[nod]=1; t[nod]=N-pas; pas++;
	int k;
	for(k=0;k<l[nod];++k)
		if(!viz[v[nod][k]]) dfv(v[nod][k]);
}
void dfvt(int nod)
{
	viz[nod]=1;
	c[pas].push_back(nod);
	int k;
	for(k=0;k<lt[nod];++k)
		if(!viz[vt[nod][k]]) dfvt(vt[nod][k]);
}
int main()
{
	citire(); int i, s, j;
	for(i=1;i<=N;i++)
		if(!viz[i]) dfv(i);
	for(i=1;i<=N;i++)
	{
		o[t[i]]=i; viz[i]=0;
	}
	pas=0;
	for(i=1;i<=N;i++)
		if(!viz[o[i]])
		{
			pas++;
			dfvt(o[i]);
		}
	g<<pas<<'\n';
	for(i=1;i<=pas;i++)
	{
		s=c[i].size();
		for(j=0;j<s;j++)
			g<<c[i][j]<<' ';
		g<<'\n';
	}
}