Cod sursa(job #993803)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 4 septembrie 2013 14:41:06
Problema Componente biconexe Scor 8
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <bitset>

FILE *f=fopen("biconex.in","r");
FILE *g=fopen("biconex.out","w");

#define pb push_back

using namespace std;
const int Nmax = 100005;
const int Mmax = 200005;

bitset< Nmax > used,artic;
vector< int > lv[Nmax];
int tata[Nmax],niv[Nmax],nmin[Nmax];
int N,M,fr;

void DFS(int nodc)
{
    used[ nodc ] = true;
    nmin [ nodc ] = niv [ nodc ];
    for(vector< int > ::iterator it = lv[nodc].begin();it!=lv[nodc].end();++it)
    if(used[ *it ] == false)
    {
        niv [ *it ] = niv [ nodc ] + 1;
        tata [ *it ] = nodc;
        if( nodc == 1) ++fr;
        DFS( *it );
        if( nmin[ * it ] < nmin[ nodc ]) nmin[ nodc ] = nmin[ *it ];
        if( nmin[ *it ] >= niv[ nodc ]) artic[ nodc ] = 1;
    }
    else if( tata[ nodc ] != *it && niv[*it] < nmin[nodc])nmin[nodc]=niv[*it];
}

void get_Graph()
{
    fscanf(f,"%d%d",&N,&M);
    int a,b;
    for(int i=1;i<=M;++i)
    {
        fscanf(f,"%d%d",&a,&b);
        lv[a].pb(b);
        lv[b].pb(a);
    }
}

int main()
{
    get_Graph();
    DFS(1);
    int total=0;
    if(fr<=1)artic[1]=0;
    for(int i=1;i<=N;++i)
        if(artic[i]==true)++total;
    fprintf(g,"%d\n",total+1);
    return 0;
}