Cod sursa(job #1958069)

Utilizator Train1Train1 Train1 Data 7 aprilie 2017 23:19:28
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <vector>
#define NMax 100001
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector <int> v[NMax];
int low[NMax], dfn[NMax];
int n, m, x, y, ordin, fii, compc, RAD;
void dfs(int nod, int Tnod) {
    ordin++;
    dfn[nod] = ordin;
    low[nod] = ordin;
    if(Tnod == RAD) fii++;
    for(int i = 0; i < v[nod].size(); i++) {
        int fiu = v[nod][i];
        if(Tnod != fiu) {
            if(dfn[fiu] == 0) {
                dfs(fiu, nod);
                if(low[fiu] >= dfn[nod] && nod != RAD) {
                    compc++;
                }
            }
            low[nod] = min (low[nod], low[fiu]);
        }
    }
}
int main()
{
    fin>>n>>m;
    for(int i = 1; i <= m; i++) {
        fin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    ordin = 1;
    //low[1] = 1;
    for(int i = 1; i <= n; i++) {
        if(dfn[i] == 0) {
            RAD = i;
            dfs(i, 0);
        }
    }
    fout<<compc;
    /*
    for(int i = 1; i <= n; i++) {
        fout<<dfn[i]<<" ";
    }
    fout<<'\n';
    for(int i = 1; i <= n; i++) {
        fout<<low[i]<<" ";
    }*/
    fin.close();
    fout.close();
    return 0;
}