articulation points and bridges, C++ (gcc)

articulation points and bridges

#include <bits/stdc++.h>

using namespace std;
#define pii pair<int, int>
#define mp make_pair
#define pb push_back

const int N = 1e5;

vector<int> g[N];

//https://www.hackerearth.com/practice/algorithms/graphs/articulation-points-and-bridges/tutorial/

int ar[N] = {0}, vis[N] = {0}, low[N] = {0}, dis[N] = {0}, timer = 0;

vector<pii> bridge;

void dfs(int s, int p){
    low[s] = dis[s] = timer++;
    vis[s] = 1;
    
    int child = 0;
    for(auto i : g[s]){
        if(!vis[i]){
            child++;
            dfs(i, s);
            low[s] = min(low[s], low[i]);
            if(dis[s] < low[i]) ar[s] = 1, bridge.pb(mp(i, s));     // dis[s] (not low[s]) as low[s] is not ready and also it's enough to cross this vertex
        }
        else if(i != p){
            low[s] = min(low[s], dis[i]);     //as 'i' has not yet completed.
        }
    }
    if(p == -1 && child > 1) ar[s] = 1;
}

int main(){
    int n, m;
    cin >> n >> m;
    while(m--){
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1, -1);
    int arti = 0;
    for(int j = 0; j <= n; j++)
        if(ar[j]) arti++;
    
    cout << arti << endl;
    for(int j = 0; j <= n; j++) if(ar[j]) cout << j << " ";
    cout << endl << bridge.size() << endl;
    for(auto &i : bridge)
        if(i.first > i.second) swap(i.first, i.second);
    
    sort(bridge.begin(), bridge.end());
    for(auto i : bridge) cout << i.first << " " << i.second << endl;
    return 0;
}


run \| edit \| history \| help	0

λ

                                      .NET NoSQL database for rapid development