Cod sursa(job #1279705)

Utilizator turbowin120Amarandei-Stanescu Alexandru turbowin120 Data 30 noiembrie 2014 19:08:51
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <stdio.h>
using namespace std;

const int M=200420;
const int N=101337;


struct grafuri{int  vf[M],urm[M],lst[N];}g1,g2;

int cnt;

int timp[N],cntt=1;

int sol[M], cnts=1;

bool viz[N];

int nr;

inline void adauga(int x, int y)
{
    ++nr;
    g1.vf[nr]=y;
    g1.urm[nr]=g1.lst[x];
    g1.lst[x]=nr;

    g2.vf[nr]=x;
    g2.urm[nr]=g2.lst[y];
    g2.lst[y]=nr;
}

void homodfs(int x)
{
    viz[x]=false;
    int y,p;
    p=g2.lst[x];

    sol[cnts++]=x;

    while (p!=0)
    {
        y=g2.vf[p];
        if(viz[y]) homodfs(y);
        p=g2.urm[p];
    }
}


void dfs(int x)
{
    viz[x]=true;
    int y,p;
    p=g1.lst[x];
    while (p!=0)
    {
        y=g1.vf[p];
        if(!viz[y]) dfs(y);
        p=g1.urm[p];
    }

    timp[cntt++]=x;

}
int main()
{
    int n,m,x,y;
    FILE * in, *out;
    in=fopen ("ctc.in","r");
    out=fopen ("ctc.out","w");
    fscanf(in,"%d%d",&n,&m);

    for(int i=1;i<=m;i++)
    {
        fscanf(in,"%d%d",&x,&y);
        adauga(x,y);

    }


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


    for(int i=cntt; i>0; i--)
        if(viz[timp[i] ]==1)
        {
            cnt++;
            homodfs(timp[i]);
            sol[cnts++]=0;
        }


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

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

    return 0;
}