Cod sursa(job #849096)

Utilizator dragangabrielDragan Andrei Gabriel dragangabriel Data 6 ianuarie 2013 13:16:22
Problema Componente biconexe Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include<fstream>
#include<vector>
 
using namespace std;
 
 
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int urca[100001],nivel[100001];
vector <int> lv[100005];
vector <int> com[100005];
bool viz[100005];
int nr;
 
int n,m;
int cate,start;

void dfs(int nod,int niv,int tata)
{   int i;
    urca[nod]=niv;
    nivel[nod]=niv;
    int siz;
    siz=lv[nod].size();
    for(i=0;i<siz;i++)
    {
        int x=lv[nod][i];
        if(!nivel[x])
        {   
            dfs(x,niv+1,nod);
            if(urca[nod]>urca[x])urca[nod]=urca[x];
               else
                   if(urca[x]>=niv)    nr++;
        }
		else
            if(x!=tata&&nivel[x]<urca[nod]) urca[nod]=nivel[x];
    } 
}
 
int main()
{
    int i;
     
    fin>>n;
    fin>>m;
     
    for(i=1;i<=m;i++)
    {   
        int x,y;
        fin>>x>>y;
        lv[x].push_back(y);
        lv[y].push_back(x);
    }
    for(i=1;i<=n;i++)
        if(!nivel[i])dfs(i,1,0);
     
    fout<<nr<<"\n";
}