Cod sursa(job #1033534)

Utilizator andreip1996Paun Andrei andreip1996 Data 17 noiembrie 2013 09:37:38
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <cstdio>


struct nod
{
    int v;
    nod *urm;
};
nod *L[100002];
nod *LT[100002];
int ctc[100002],viz[100002],idx[100002];
int n,m,nr,nrctc;

void adaug(nod *&prim,int v)
{
    nod *nou=new nod;
    nou->v=v;
    nou->urm=prim;
    prim=nou;
}

void citire()
{

    freopen("ctc.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        adaug(L[x],y);
        adaug(LT[y],x);
    }
}

void DFS(int v)
{
    viz[v]=1;
    for(nod *p=L[v];p;p=p->urm)
       if(!viz[p->v])
            DFS(p->v);
    idx[++nr]=v;

}

void DFST(int v)
{
    viz[v]=0;ctc[v]=nrctc;
    for(nod *p=LT[v];p;p=p->urm)
       if(viz[p->v])
            DFST(p->v);
}


int main()
{
    citire();
    for(int i=1;i<=n;i++)
        if(!viz[i])
            DFS(i);
    for(int i=n;i>=1;i--)
        if(viz[idx[i]])
             {
                 nrctc++;
                 DFST(idx[i]);

             }
    freopen("ctc.out","w",stdout);
    printf("%d\n",nrctc);
    for(int i=1;i<=nrctc;i++)
    {
        for(int j=1;j<=n;j++)
            if(ctc[j]==i)
              printf("%d ",j);
        printf("\n");
    }
    return 0;
}