Cod sursa(job #2157822)

Utilizator sandupetrascoPetrasco Sandu sandupetrasco Data 9 martie 2018 22:38:48
Problema Componente biconexe Scor 4
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <bits/stdc++.h>

#define pb push_back
#define x first
#define y second
#define MOD 1000000007

using namespace std;
typedef unsigned long long ll;
typedef pair<ll, ll> PII;
const int dirx[] = {-2, -1, 1, 2, 1, -1};
const int diry[] = {0, 1, 1, 0, -1, -1};
inline void debugMode()
{
#ifndef ONLINE_JUDGE
    freopen("biconex.in", "r", stdin);
    freopen("biconex.out", "w", stdout);
#endif
}

int n, m, Depth[100100], Low[100100];
bool viz[100100];

vector < int > V[100100];
set < int > Crit;

void dfs(int node, int dad, int depth){
    viz[node] = 1;
    Depth[node] = depth;
    Low[node] = depth;

    for (auto it: V[node]){
        if (!viz[it]){
            dfs(it, node, depth + 1);
            if (Low[it] >= Depth[node]){
                Crit.insert(node);
            }
            Low[node] = min(Low[node], Low[it]); 
        } else if (it != dad){
            Low[node] = min(Low[node], Depth[it]);
        }
    }
}

int main(){
    debugMode();
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;

    for (int i = 0, x, y; i < m; i++){
        cin >> x >> y;
        V[x].pb(y);
        V[y].pb(x);
    }

    dfs(1, -1, 0);
    if (V[1].size() > 1) Crit.insert(1);

    cout << Crit.size() + 1 << "\n";
    return 0;
}