Cod sursa(job #363187)

Utilizator PopaStefanPopa Stefan PopaStefan Data 12 noiembrie 2009 09:21:38
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include<fstream>
#define nmax 90001


using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n,m,numar=1;
int nr,viz[nmax],postordine[nmax];
int comp[nmax];

struct nod
   {int inf; //valoarea nodului respectiv
    nod *urm;  //adresa urmatorului nod din lista
   };
nod *l[nmax],*a[nmax];

void citire()
{int i,m,x,y;
fin>>n>>m;
for(i=1;i<=m;i++)
  {fin>>x>>y;
   nod *c;
   c=new nod;
   c->inf=y;
   c->urm=l[x];
   l[x]=c;
   c=new nod;
   c->inf=x;
   c->urm=a[y];
   a[y]=c;
  }
}

void dfs(int x)
{viz[x]=1;
for(nod *c=l[x];c!=NULL ;c=c->urm)
  if(viz[c->inf]==0)
    dfs(c->inf);
postordine[++nr]=x;
}

void dfst(int x)
{viz[x]=0;
comp[x]=numar;
for(nod *c=a[x];c!=NULL ;c=c->urm)
  if(viz[c->inf]==1)
     dfst(c->inf);
}

int main()
{int i,j;
citire();
for(i=1;i<=n;i++)
  if(viz[i]==0) dfs(i);
for(i=n;i>=1;i--)
   if(viz[postordine[i]])
     {dfst(postordine[i]);
      numar++;
     }
fout<<numar-1<<'\n';
for(j=1;j<=numar;j++)
  {for(i=1;i<=n;i++)
     if(comp[i]==j)
       fout<<i<<' ';
  fout<<'\n';
  }
fin.close();
fout.close();
return 0;
}