Cod sursa(job #1368258)

Utilizator andreeadeacAndreea Ioana Deac andreeadeac Data 2 martie 2015 15:32:25
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <cstdio>
using namespace std;

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

const int N=100001, M=200001;
int n,nrm,nr,nrc;
int lst[N], lstt[N], vft[M], urmt[M], mt, vf[M], urm[M], m,c[N],rez[2*N];
bool viz[N];
int vizt[N];

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

void dfst(int x){
    int p = lstt[x], y;
    vizt[x] = 1;
    rez[++nr]=x;
    while(p != 0)
    {
        y = vft[p];
        if (!vizt[y])
            dfst(y);
        p = urmt[p];
    }
}

void adaug(int x, int y)
{
    m++;
    vf[m] = y;
    urm[m] = lst[x];
    lst[x] = m;
}

void adaugt(int x, int y)
{
    mt++;
    vft[m] = x;
    urmt[m] = lstt[y];
    lstt[y] = mt;
}

int main()
{
    int i,j,x,y,cod,p,nod;
    fscanf(in,"%d%d",&n,&nrm);
    for(i=1;i<=nrm;i++){
        fscanf(in,"%d%d",&x,&y);
        adaug(x,y);
        adaugt(x,y);
    }

    for(i=1;i<=n;i++)
        if(!viz[i])
            dfs(i);
    y=0;
    nr=0;
    for(i=n;i>=1;i--){
        x=c[i];
        if(!vizt[x]){
            y++;
            dfst(x);
            rez[++nr]=-1;
        }
    }
    fprintf(out,"%d\n",y);
    for(i=1;i<=nr;i++)
        if(rez[i]==-1)
            fprintf(out,"\n");
        else
            fprintf(out,"%d ",rez[i]);
    return 0;
}