Cod sursa(job #486714)

Utilizator ClasianMunteanu Petre Clasian Data 22 septembrie 2010 17:14:46
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include<fstream>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
struct nod { int info;
			 nod* lg;
			}*r,*vf[100001],*fv[100001],*af[100001];
int n,use[100001],temps,st[100001],nr;
void DF1(int i)
{ use[i]=1;
  for(nod* p=vf[i];p;p=p->lg)if(!use[p->info])DF1(p->info);
  st[++temps]=i;
}
void DF2(int i)
{ use[i]=1;
  nod* p=af[nr];
  p->info=i;
  p->lg=af[nr];
  af[nr]=p;
  for(p=fv[i];p;p=p->lg)if(!use[p->info])DF2(p->info);
}
int main()
{ int i,m,a,b;
  f>>n>>m;
  for(i=1;i<=n;i++) vf[i]=0,fv[i]=0;
  for(i=1;i<=m;i++) { f>>a>>b;
					  r=new nod;
					  r->info=b;
					  r->lg=vf[a];
					  vf[a]=r;
					  r=new nod;
					  r->info=a;
					  r->lg=fv[b];
					  fv[b]=r;
					}
  for(i=1;i<=n;i++)if(!use[i])DF1(i);
  memset(use,0,sizeof(use));
  for(i=n;i;i--)if(!use[st[i]]) { nr++;
								  DF2(st[i]);
								}
  g<<nr<<'\n';
  for(;nr;nr--) { for(r=af[nr];r;r=r->lg)g<<r->info<<' ';
                  g<<'\n';
                }
  f.close();
  g.close();  
  return 0;
}