Find all articulation points and bridges in a graph

findArtsAndBridge.cpp

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

void dfs(vector<vector<ll>> &graph,
         vector<pair<ll, ll>> &bridges,
         vector<bool> &isArt,
         vector<bool> &visited,
         vector<ll> &ids,
         vector<ll> &low,
         ll &id, ll &outEdgesCnt, ll begin, 
         ll parent, ll u) { // Focus on the last 2 parameters, the rest is unchanged
    if (parent == begin) outEdgesCnt++;
    visited[u] = true;
    low[u] = ids[u] = id; // Assign unique ID for each vertex, ID must follow order of DFS traversal
    id++;
    for (ll i : graph[u]) {
        if (i == parent) continue; // Avoid self-loop
        if (!visited[i]) {
            dfs(graph, bridges, isArt, visited, ids, low, id, outEdgesCnt, begin, u, i);
            low[u] = min(low[u], low[i]); // If a vertex can reach vertex u then it can reach vertex i too
            if (ids[u] < low[i]) { // Detected bridge
                // Explaination: Because each connected component with no bridge have the same value of low[i] so that when ids[u] < low[i] => u and i are in difference connected component with no bridge
                // Difference connected component with no bridge is guarentee to have low value lower than other component's low value or larger than other component's largest vertex ID
                bridges.push_back({u, i});
                isArt[u] = true;
            }
            if (ids[u] == low[i]) { // Detected cycle
                // Since low value of connected component with no bridge is the same and ids[u] < ids[i] so that there is the chance of ids[u] is the low value. If this happen, it mean we encountered a cycle
                // For now, mark u is articulation point because we doesn't know its out going edges count yet
                isArt[u] = true;
            }
        } else {
            low[u] = min(low[u], ids[i]); // Because vertex i is visited so that there is a path from u to i
        }
    }
}

pair<vector<ll>, vector<pair<ll, ll>>> findArtsAndBridges(vector<vector<ll>> &graph, ll n) {
    vector<pair<ll, ll>> bridges;
    vector<ll> arts, ids(n + 1), low(n + 1); // low[i] is lowest vertex ID can be reached from vertex i by going over 1 child vertex and 1 parent vertex
    vector<bool> visited(n + 1), isArt(n + 1);
    ll id = 1;
    for (ll i = 1; i <= n; i++) {
        if (!visited[i]) {
            ll outEdgesCnt = 0;
            dfs(graph, bridges, isArt, visited, ids, low, id, outEdgesCnt, i, -1, i);
            // Articulation point must have more than 1 out going edges so that when we remove that vertex, it will disconnect at least 2 subgraph contain those out going edges
            // Note that outEdgesCnt != graph[i].size() because out going edges here must lead us to unvisited vertex
            isArt[i] = outEdgesCnt > 1; 
        }
        if(isArt[i]) arts.push_back(i);
    }
    return {arts, bridges};
}

int main() {
    ll n, m;
    cin >> n >> m;
    vector<vector<ll>> graph(n + 1);
    while (m--) {
        ll a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    auto a = findArtsAndBridges(graph, n);
    cout << a.first.size() << ' ' << a.second.size();
}