Cod sursa(job #396685)

Utilizator mihaimoldovanMihai Moldovan mihaimoldovan Data 15 februarie 2010 18:46:36
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include<fstream>
#include<iostream>
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)
{
	//cout<<vf<<" ";cout.flush();
	v[vf]=1;
	for(nod *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]=nrc;
	t=new nod;
	t->info=x;
	t->next=c[nrc];
	c[nrc]=t;
	for(nod *t=gt[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),cout<<endl;
	//cout<<"2\n";cout.flush();
	for(int i=timp ; i ; --i)
		if(!vt[final[i]])
			dfst(final[i],++nrc);
}
void afis(nod * G[]){
	for(int i=1;i<=n;++i){
		cout<<i<<" : ";
		for(nod *p=G[i]; p ; p=p->next)
			cout<<p->info<<" ";
		cout<<endl;
	}
}

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);
	}
	//afis(g);
	//afis(gt);
//	cout<<"1\n";cout.flush();
	fin.close();
	kosaraju();
	//cout<<"1\n";cout.flush();
	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;
}