Cod sursa(job #1261765)

Utilizator heracleRadu Muntean heracle Data 12 noiembrie 2014 17:50:08
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.94 kb
#include <cstdio>

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

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

int n,m;

const int Q=100002,W=200004;

int lst[Q],nxt[W],val[W],nr;

void add(int a, int b)
{
    nr++;
    val[nr]=b;
    nxt[nr]=lst[a];
    lst[a]=nr;
}

int viz[Q];

int nrs;

int go[Q],wh[Q];
int tat[Q];

int num;

int st[Q],nst;

void dfs(int nod)
{
    int p=lst[nod];
    viz[nod]=++num;
    go[nod]=nod;

    st[++nst]=nod;

    while(p)
    {
        if(viz[val[p]]!=0 && wh[val[p]]==0)
        {
            if(viz[go[nod] ] > viz[ val[p] ])
            {
                go[nod]=val[p];
            }
        }
        if(viz[val[p]]==0)
        {
            tat[val[p]]=nod;
            dfs(val[p]);
        }
        p=nxt[p];
    }


    wh[nod]=++nrs;
}



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 act=st[nst];

    int rez=0;

    while(act!=0)
    {
        if(go[act]!=act)
        {
            act=go[act];
        }
        else
        {
            rez++;

            act=st[viz[act]-1];
        }
    }

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

    act=nst;

    int nxt=st[nst];

    while(go[nxt]!=nxt)
        nxt=go[nxt];

    for(; act>0; act--)
    {
        if(st[act]==nxt)
        {
            fprintf(out,"%d\n",st[act]);

            nxt=st[viz[nxt]-1];

            while(go[nxt]!=nxt)
                nxt=go[nxt];
        }
        else
            fprintf(out,"%d ",st[act]);
    }



/*

    act=st[nst];

    int nxt=act;

    while(go[nxt]!=nxt)
    {
        nxt=go[nxt];
    }

    for(; act>0; act--)
    {
        if(act==nxt)
        {
            fprintf(out,"%d\n",st[act]);

            nxt=st[viz[nxt]-1];

            while(go[nxt]!=nxt)
                nxt=go[nxt];

        }
        else
            fprintf(out,"%d ",st[act]);
    }

*/
    return 0;
}