Cod sursa(job #306095)

Utilizator utcistuBarcau Tomsa utcistu Data 19 aprilie 2009 18:28:30
Problema Componente biconexe Scor 20
Compilator c Status done
Runda Arhiva educationala Marime 2.01 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define VMAX 110000
#define EMAX 210000
#define MINIM(a,b) a<b?a:b

int start[EMAX],target[EMAX],prev[EMAX],last[VMAX],stack[EMAX],list[EMAX*2],p[VMAX],d[VMAX],b[VMAX];
char viz[VMAX];
int edgeNo,nodeNo,push=0,size=0,timp=0,biconexNo=0;

void dfsBiconex(int node)
{
    viz[node]=1;
    int i;
    d[node]=++timp;
    b[node]=d[node];
    if (last[node]!=-1 || timp!=1)
    {
    for (i=last[node];i>=0;i=prev[i])
    if (viz[target[i]] && target[i]!=p[node])
    {
        stack[++push]=i;
        b[node]=MINIM(b[node],d[target[i]]);
    }
    else if (!viz[target[i]])
    {
        p[target[i]]=node;
        stack[++push]=i;
        dfsBiconex(target[i]);
        if (b[target[i]]>=b[node])
        {
            biconexNo++;
            if (stack[push]!=i)
            {
            while (stack[push]!=i)
            {
                list[size++]=start[stack[push--]];
            }
            list[size++]=start[stack[push--]];
            }
            else
            {
                list[size++]=start[stack[push]];
                list[size++]=target[stack[push--]];
            }
            list[size++]=-1;
        }
        else
        {
            b[node]=b[target[i]];
        }
    }
    }
    else
    {
        biconexNo++;
        list[size++]=node;
        list[size++]=-1;
    }
    timp--;
}

int main()
{
    int i,x,y;
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    scanf("%d %d",&nodeNo,&edgeNo);
    for (i=0;i<nodeNo;i++) last[i]=-1;
    for (i=0;i<nodeNo;i++) p[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;
    }
    for (i=0;i<nodeNo;i++)
        if (!viz[i]) dfsBiconex(i);
    printf("%d\n",biconexNo);
    for (i=0;i<size;i++)
    if (list[i]==-1)
        puts("");
    else
        printf("%d ",list[i]+1);
    fclose(stdout);
    return 0;
}