Cod sursa(job #677287)

Utilizator batistaUPB-Oprea-Cosmin-Dumitru batista Data 9 februarie 2012 23:12:35
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include<fstream>
using namespace std;
struct nod{int info;nod*adr;}*v[100003],*vt[100003],*p;
int n,m,i,x,y;
short viz[100003];
int ord[100003],nr=0,nrctc;
int ctc[200003];
void dfs(int nod)
{
	viz[nod]=1;
	while(v[nod])
	{
		if(!viz[v[nod]->info])dfs(v[nod]->info);
		v[nod]=v[nod]->adr;
	}
	ord[++nr]=nod;
}

void dfst(int nod)
{
	viz[nod]=0;
	ctc[++nr]=nod;
	while(vt[nod])
	{
		if(viz[vt[nod]->info])dfst(vt[nod]->info);
		vt[nod]=vt[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=vt[y]; vt[y]=p;
	}
	for(i=1;i<=n;i++)
	  if(!viz[i])
	     dfs(i);
	  nr=0;
	for(i=n;i>=1;i--)
	 if(viz[ord[i]])
	 {
		dfst(ord[i]);
		ctc[++nr]=0;
		nrctc++;
	 }
	 g<<nrctc<<'\n';
	 i=1;
	 while(nrctc)
	 {
		while(ctc[i]){ g<<ctc[i]<<" ";i++; }
		i++;
		nrctc--;
		g<<'\n';
	 }
	f.close();g.close();
return 0;}