Cod sursa(job #606251)

Utilizator batistaUPB-Oprea-Cosmin-Dumitru batista Data 3 august 2011 18:21:30
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include<fstream>
using namespace std;
struct nod{int info;nod *adr;}*v[100001],*v2[100001],*p;
int n,m,i,x,y,pred[100002],suc[100002],nrc,j;
void dfs_pred(int nod)
{  p=v[nod];
	pred[nod]=nrc;
	while(p)
	{
		if(!pred[p->info]) dfs_pred(p->info);
		if(p)p=p->adr;
	}
}
void dfs_suc(int nod)
{ p=v2[nod];
	suc[nod]=nrc;
	while(p)//parcurgere pe coloana(a 2-a lista)
	{
		if(!suc[p->info]) dfs_suc(p->info);
		if(p)p=p->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;
	}
	    nrc=1;
	for(i=1;i<=n;i++)
	  if(suc[i]==0) 
	  { 
		  dfs_suc(i); 
		  dfs_pred(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;}