Cod sursa(job #2932565)

Utilizator Stefan_DomuncoStefan Domunco Stefan_Domunco Data 3 noiembrie 2022 09:49:35
Problema Componente biconexe Scor 4
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1e5 + 3;
vector <int> g[NMAX];
bitset <NMAX> viz, artPoint;
int niv[NMAX], nivMin[NMAX];
int n;

void dfs(int node, int depth)
{
    viz[node] = 1;
    niv[node] = nivMin[node] = depth;

    for(auto &it: g[node])
    {
        if(viz[it]){
            if(niv[it] + 1 == depth) continue;
            nivMin[node] = min(nivMin[node], niv[it]);
        }
        else{
            dfs(it, depth + 1);
            nivMin[node] = min(nivMin[node], nivMin[it]);

            if(nivMin[it] >= niv[node])
                artPoint[node] = 1;
        }
    }


}

int main()
{
    ifstream fin("biconex.in");
    ofstream fout("biconex.out");

    int i, a, b, m;

    fin >> n >> m;
    for(i = 1; i <= m; ++i)
    {
        fin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    for(i = 1; i <= n; ++i)
    {
        if(viz[i]) continue;

        dfs(i, 1);
    }

    int sol = 0;
    for(i = 1; i <= n; ++i)
    {
        if(artPoint[i]) ++sol;
    }

    fout << sol + 1;

    return 0;
}