Cod sursa(job #306039)

Utilizator utcistuBarcau Tomsa utcistu Data 19 aprilie 2009 14:51:03
Problema Componente tare conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.5 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define VMAX 100010
#define EMAX 310000

int start[EMAX],target[EMAX],prev[EMAX],last[VMAX],list[VMAX],ctc[VMAX];
char viz[VMAX];
int edgeNo,nodeNo,push,ctcNo=0;

void dfs(int node)
{
    viz[node]=1;
    int i;
    for (i=last[node];i>=0;i=prev[i])
    if (!viz[target[i]]) dfs(target[i]);
    list[push--]=node;
}

void dfs2(int node)
{
    viz[node]=1;
    int i;
    for (i=last[node];i>=0;i=prev[i])
    if (!viz[target[i]]) dfs2(target[i]);
    ctc[push++]=node+1;
}

int main()
{
    int i,x,y;
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d %d",&nodeNo,&edgeNo);
    for (i=0;i<nodeNo;i++) last[i]=-1;
    for (i=0;i<edgeNo;i++)
    {
        scanf("%d %d",&x,&y);x--;y--;
        start[i]=x;target[i]=y;prev[i]=last[x];last[x]=i;
    }
    push=nodeNo-1;
    for (i=0;i<nodeNo;i++)
        if (!viz[i]) dfs(i);
    for (i=0;i<nodeNo;i++) last[i]=-1;
    for (i=0;i<nodeNo;i++) viz[i]=0;
    for (i=0;i<edgeNo;i++)
    {
        x=start[i];start[i]=target[i];target[i]=x;
        prev[i]=last[start[i]];
        last[start[i]]=i;
    }
    push=0;
    for (i=0;i<nodeNo;i++)
    if (!viz[list[i]])
    {
        dfs2(list[i]);
        ctcNo++;
        ctc[push++]=-1;
    }
    printf("%d\n",ctcNo);
    for (i=0;i<push;i++)
    {
        if (ctc[i]==-1)
            puts("");
        else
            printf("%d ",ctc[i]);
    }
    fclose(stdout);
    return 0;
}