Cod sursa(job #1262530)

Utilizator alexpascadiAlexandru Pascadi alexpascadi Data 13 noiembrie 2014 11:59:29
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <stdio.h>

using namespace std;

const int N=100001;
const int M=200001;

bool v[N];
int lst[2][N],nod[2][M],nxt[2][M],smen[N],rez[2*N];
int nr[2],n,m,nsmen,vf,nc,nrez;

void adauga(int e, int x, int y)
{
    nr[e]++;
    nod[e][nr[e]]=y;
    nxt[e][nr[e]]=lst[e][x];
    lst[e][x]=nr[e];
}

void dfs(int x)
{
    int p;
    v[x]=1;
    p=lst[0][x];
    while(p!=0)
    {
        if(!v[nod[0][p]])
            dfs(nod[0][p]);
        p=nxt[0][p];
    }
    smen[nsmen++]=x;
}

void dfsmen(int x)
{
    int p;
    v[x]=1;
    rez[nrez++]=x;
    //printf("%d ",x);
    p=lst[1][x];
    while(p!=0)
    {
        if(!v[nod[1][p]])
            dfsmen(nod[1][p]);
        p=nxt[1][p];
    }
}

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

    int i,x,y;
    fscanf(in,"%d%d",&n,&m);

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

    for(i=1;i<=n;i++)
        if(!v[i])
            dfs(i);

    for(i=1;i<=n;i++)
        v[i]=0;

    for(i=nsmen-1;i>=0;i--)
    {
        vf=smen[i];
        if(!v[vf])
        {
            dfsmen(vf);
            nc++;
            rez[nrez++]=-1;
            //printf("\n");
        }
    }

    fprintf(out,"%d\n",nc);
    for(i=0;i<nrez;i++)
    {
        if(rez[i]==-1)
            fprintf(out,"\n");
        else
            fprintf(out,"%d ",rez[i]);
    }

    return 0;
}