Cod sursa(job #1368240)

Utilizator andreeadeacAndreea Ioana Deac andreeadeac Data 2 martie 2015 15:22:08
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 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];
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 mark){
    int p = lstt[x], y;
    vizt[x] = mark;
    while(p != 0)
    {
        y = vft[p];
        if (!vizt[y])
            dfst(y,mark);
        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;
    for(i=n;i>=1;i--){
        x=c[i];
        if(!vizt[x]){
            y++;
            dfst(x,y);
        }
    }
    fprintf(out,"%d\n",y);
    for(i=1;i<=y;i++){
        for(j=1;j<=n;j++)
            if(vizt[j]==i)
                fprintf(out,"%d ",j);
        fprintf(out,"\n");
    }
    return 0;
}