Cod sursa(job #1270725)

Utilizator heracleRadu Muntean heracle Data 22 noiembrie 2014 12:06:02
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <cstdio>

FILE* in=fopen("ctc.in","r");
FILE* out=fopen("ctc.out","w");

int n,m;

const int Q=100007,W=200007;

int lst1[Q],lst2[Q],val1[W],val2[W],nxt1[W],nxt2[W],nr;

int viz[Q];

int ord[Q];

int rez[W];

int sfd(int nod)
{
    viz[nod]=0;

    int p=lst2[nod];

    rez[++rez[0]]=nod;

    while(p)
    {
        if(viz[val2[p]]==1)
        {
            sfd(val2[p]);
        }
        p=nxt2[p];
    }
}

int dfs(int nod)
{
    viz[nod]=1;

    int p=lst1[nod];

    while(p)
    {
        if(!viz[val1[p]])
        {
            dfs(val1[p]);
        }
        p=nxt1[p];
    }
    ord[++ord[0]]=nod;
}

int add(int a, int b)
{
    nr++;
    val1[nr]=b;
    val2[nr]=a;

    nxt1[nr]=lst1[a];
    nxt2[nr]=lst2[b];

    lst1[a]=nr;
    lst2[b]=nr;
}

int main()
{
    fscanf(in,"%d%d",&n,&m);

    int a,b;
    for(int i=1; i<=m; i++)
    {
        fscanf(in,"%d%d",&a,&b);
        add(a,b);
    }

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

    int nr=0;

    for(int i=ord[0]; i>0; i--)
    {
        if(viz[ord[i] ]==1)
        {
            nr++;
            sfd(ord[i]);
            rez[++rez[0]]=0;
        }

    }


    fprintf(out,"%d\n",nr);

    for(int i=1; i<=rez[0]; i++)
    {
        if(rez[i]==0)
            fprintf(out,"\n");
        else
            fprintf(out,"%d ",rez[i]);
    }

    return 0;
}