Cod sursa(job #1698566)

Utilizator florinpocolPocol Florin florinpocol Data 4 mai 2016 19:47:08
Problema Componente tare conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.44 kb
#include<stdio.h>
#define N 100010
 struct nod{int inf;struct nod *urm;};
struct nod *v[N],*C[N];
int n,m,i,a,b,viz[N],stiva[N],low[N],dsfnum[N],top,num,nc;
void readd(),solve(),visit(int p),prints();
int main()
{
    readd();
    solve();
    prints();
    return 0;
}
void readd()
{   struct    nod *paux;
    freopen("ctc.in","rt",stdin);
    freopen("ctc.out","wt",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    { scanf("%d%d",&a,&b);
      paux=calloc(1,sizeof(struct nod));
      paux->inf=b;
      paux->urm=v[a];
      v[a]=paux;
    }
}
void solve()
{   for(i=1;i<=n;i++)
    if(!viz[i]){num=0;visit(i);}
}

void visit(int p)
{   struct nod *paux;
    viz[p]=1;
    stiva[++top]=p;//add p to L
    dsfnum[p]=++num;//increment N
    low[p]=dsfnum[p];
    for(paux=v[p];paux;paux=paux->urm)
    {   if(viz[paux->inf]==2)continue;
    if(!viz[paux->inf]) visit(paux->inf);
    low[p]=(low[p]<low[paux->inf])?low[p]:low[paux->inf];
    }
    if(low[p]==dsfnum[p])
    {   nc++;
    for(;;)
    {
      paux=calloc(1,sizeof(struct nod));
      paux->inf=stiva[top];
      viz[stiva[top]]=2;
      paux->urm=C[nc];
      C[nc]=paux;
      top--;
      if(stiva[top+1]==p)break;
    }
    }
}
void prints()
{    struct   nod *paux;
    printf("%d",nc);
    for(i=1;i<=nc;i++)
    { printf("\n");
      for(paux=C[i];paux;paux=paux->urm)
       printf("%d ",paux->inf);
    }
    printf("\n");
}