Cod sursa(job #581716)

Utilizator drywaterLazar Vlad drywater Data 14 aprilie 2011 15:31:55
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <stdio.h>
int n,m,i,x,y,st[100001],nrc,luat[100001],idx[100001],low[100001],indecs;
struct nod{int y; nod *next;};
nod *G[100001],*C[100001];
int add(int a, int b)
{
    nod *nou=new nod;
    nou->y=b;
    nou->next=G[a];
    G[a]=nou;
    return 0;
}
int gaseste(int vf)
{
    idx[vf]=low[vf]=indecs;
    indecs++;
    st[++st[0]]=vf;
    luat[vf]=1;
    nod *it=new nod;
    it=G[vf];
    while (it)
    {
        if (idx[it->y]==-1) {gaseste(it->y); if (low[vf]>low[it->y]) low[vf]=low[it->y];}
        else if (luat[it->y]) if (low[vf]>low[it->y]) low[vf]=low[it->y];
        it=it->next;
    }
    if (idx[vf]==low[vf])
    {
        nrc++;
        do
        {
        nod *nou=new nod;
        nou->y=st[st[0]];
        luat[st[st[0]]]=0;
        st[0]--;
        nou->next=C[nrc];
        C[nrc]=nou;
        }while (st[st[0]+1]!=vf);
    }
}
int main(void)
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
        idx[i]=-1;
        luat[i]=0;
    }
    for (i=1;i<=n;i++)
        if (idx[i]==-1) gaseste(i);
    printf("%d\n",nrc);
    for (i=1;i<=nrc;i++)
    {
        nod *it=new nod;
        it=C[i];
        while (it)
        {
            printf("%d ",it->y);
            it=it->next;
        }
        printf("\n");
    }
    return 0;
}