Cod sursa(job #1752091)

Utilizator GandalfTheWhiteGandalf the White GandalfTheWhite Data 2 septembrie 2016 19:08:23
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <cstdio>
using namespace std;
struct nod{
          int info;
          nod *urm;
          }*g[100001],*gt[100001],*comp[100001];
int viz[100001],n,nrc,post[100001],nr;

void read()
{
int m,i,x,y;
nod *p;
scanf("%d%d",&n,&m);
while (m--)
   {
   scanf("%d%d",&x,&y);
   p=new nod;
   p->info=y;p->urm=g[x];g[x]=p;
   p=new nod;p->info=x;p->urm=gt[y];gt[y]=p;
   }
}

void dfs(int vf)
{
nod *p;int i;
viz[vf]=1;
for (p=g[vf];p!=NULL;p=p->urm)
   {
   i=p->info;
   if (!viz[i]) dfs(i);
   }
post[++nr]=vf;
}

void dfst(int vf)
{
nod *p;
int i;
viz[vf]=0;
p=new nod;p->info=vf;p->urm=comp[nrc];comp[nrc]=p;
for (p=gt[vf];p!=NULL;p=p->urm)
   {
   i=p->info;
   if (viz[i]) dfst(i);
   }
}

void afis()
{
int i;
nod *p;
for (i=1;i<=nrc;i++)
    {
    for (p=comp[i];p!=NULL;p=p->urm)
        printf("%d ",p->info);
    printf("\n");
    }
}
int main()
{
int i;
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);

read();

for (i=1;i<=n;i++)
if (!viz[i]) dfs(i);

for (i=n;i>0;i--)
if (viz[post[i]])
    {
    nrc++;
    dfst(post[i]);
    }
printf("%d\n",nrc);
afis();
return 0;
}