Cod sursa(job #1368207)

Utilizator andreeadeacAndreea Ioana Deac andreeadeac Data 2 martie 2015 15:09:31
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 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);
        cod=1;
        p = lst[x];
        while(p != 0)
        {
            nod = vf[p];
            p = urm[p];
            if(nod==y)
                cod=0;
        }
        if(cod==1)
            adaug(x,y);
        cod=1;
        p=lstt[y];
        while(p!=0){
            nod=vft[p];
            p=urmt[p];
            if(nod==x)
                cod=0;
        }
        if(cod==1)
            adaugt(x,y);
    }

    for(i=1;i<=n;i++)
        if(!viz[i])
            dfs(i);
    y=0;
    for(i=nr;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;
}