Cod sursa(job #606276)

Utilizator batistaUPB-Oprea-Cosmin-Dumitru batista Data 3 august 2011 18:49:46
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include<fstream>
using namespace std;
struct nod{int info;nod *adr;}*v[100001],*v2[100001],*p,*cp1[100001],*cp2[100002];
int n,m,i,x,y,pred[100002],suc[100002],nrc,j;
void dfs_pred(int nod)
{ 
	pred[nod]=nrc;
	while(v2[nod])
	{
		if(!pred[v2[nod]->info]) dfs_pred(v2[nod]->info);
		v2[nod]=v2[nod]->adr;
	}
}
void dfs_suc(int nod)
{
	suc[nod]=nrc;
	while(v[nod])//parcurgere pe coloana(a 2-a lista)
	{
		if(!suc[v[nod]->info]) dfs_suc(v[nod]->info);
		v[nod]=v[nod]->adr;
	}
}
int main()
{
	ifstream f("ctc.in");ofstream g("ctc.out");
	f>>n>>m;
	for(i=1;i<=m;i++)
	{
		f>>x>>y;
		p=new nod;
		p->info=y; p->adr=v[x]; v[x]=p;
		p=new nod;
		p->info=x; p->adr=v2[y]; v2[y]=p;
	}
	for(i=1;i<=n;i++) {cp1[i]=v[i]; cp2[i]=v2[i];}
	    nrc=1;
	for(i=1;i<=n;i++)
	  if(suc[i]==0) 
	  { 
		  dfs_suc(i); v[i]=cp1[i];
		  dfs_pred(i); v2[i]=cp2[i];
	   for(j=1;j<=n;j++)
		 if(suc[j]!=pred[j]) suc[j]=pred[j]=0;
		nrc++;
	  }
	 g<<nrc-1<<"\n";
	for(i=1;i<nrc;i++)
	{
	  for(j=1;j<=n;j++)
		if(pred[j]==i && suc[j]==i) g<<j<<" ";
	  g<<"\n";
	}
	f.close();g.close();
return 0;}