Cod sursa(job #396662)

Utilizator mihaimoldovanMihai Moldovan mihaimoldovan Data 15 februarie 2010 18:24:34
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include<fstream>
using namespace std;
#define nn 100005
struct nod
{
	int info;
	nod *next;
};
nod *g[nn],*gt[nn],*t,*c[nn];
int v[nn],vt[nn],nrc,final[nn],timp,n,m;
void adauga(nod *g[],int a,int b)
{
	t=new nod;
	t->info=b;
	t->next=g[a];
	g[a]=t;
}
void dfs(int vf)
{
	v[vf]=1;
	for(t=g[vf];t;t=t->next)
		if(!v[t->info])
			dfs(t->info);
	final[++timp]=vf;
}
void dfst(int x,int nrc)
{
	vt[x]=1;
	t=new nod;
	t->info=x;
	t->next=c[nrc];
	c[nrc]=t;
	for(t=g[x];t;t=t->next)
		if(!vt[t->info])
			dfst(t->info,nrc);
}
void kosaraju()
{
	for(int i=1;i<=n;++i)
		if(v[i])
			dfs(i);
	for(int i=timp;i;--i)
		if(vt[i])
			dfst(final[i],++nrc);
}
int main()
{
	ifstream fin("ctc.in");
	fin>>n>>m;
	int a,b;
	for(;m;--m)
	{
		fin>>a>>b;
		adauga(g,a,b);
		adauga(gt,b,a);
	}
	fin.close();
	kosaraju();
	FILE *f=fopen("ctc.out","w");
	fprintf(f,"%d\n",nrc);
	for(int i=1;i<=nrc;++i)
	{
		for(t=c[i];t;t=t->next)
			fprintf(f,"%d ",t->info);
		fprintf(f,"\n");
	}
	fclose(f);
	return 0;
}