Cod sursa(job #703334)

Utilizator AplayLazar Laurentiu Aplay Data 2 martie 2012 11:52:46
Problema Componente biconexe Scor 8
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include<stdio.h>
#include<stdlib.h>
typedef struct nod{ int x; nod *urm;}NODE;
NODE *v[100010];
int n,m,d[100010],min[100010],k;

int minim(int a, int b)
{
    if(a<=b) return a;
    return b;
}

void citire()
{
    FILE *f=fopen("biconex.in","r");
    NODE*q;
    int x,y;
    fscanf(f,"%d%d",&n,&m);
    for(int i=0;i<m;++i)
    {
        fscanf(f,"%d%d",&x,&y);
        q=(NODE*)malloc(sizeof(NODE));
        q->x=y;
        q->urm = v[x];
        v[x] = q;
        q=(NODE*)malloc(sizeof(NODE));
        q->x=x;
        q->urm = v[y];
        v[y] = q;
    }
    fclose(f);
}

void dfs(int nod,int tata,int dist)
{
    d[nod]=min[nod]=dist;
    int nrf=0;
    bool critic = false;
    NODE *q=v[nod];
    while(q)
    {
        if(q->x != tata)
            if(d[q->x]==-1)
            {
                ++nrf;
                dfs(q->x,nod,dist+1);
                min[nod] = minim(min[q->x],min[nod]);
                if(min[q->x] >= d[nod]) critic = true;
            }
        else
            min[nod] = minim(min[nod],d[q->x]);
        q=q->urm;
    }
    if( (nod == 1  && nrf > 1) || (nod!=1 && critic) )
        //printf("%d ",nod);
        ++k;
}

int main()
{
    citire();
    for(int i=1;i<=n;++i) d[i]=-1;
    dfs(1,0,0);
    FILE *f=fopen("biconex.out","w");
    fprintf(f,"%d\n",k+1);
    fclose(f);
    return 0;
}