C++ :: Articulation Bridge Detection Algorithm

PSEUDOCODE

ARTICULATION-BRIDGE-DFS-VISIT(G,u)
    time = time + 1
    u.d = u.low = time
    u.color = GRAY
    for each v ∈ G.Adj[u]
        if v.color == WHITE
            v.π = u
            DFS-VISIT(G,v)
            if u.d == 1
                if G.Adj[u].size >= 2 AND v.low > u.d
                    bridgeCounter = bridgeCounter + 1
                    bridge.push(edge(u,v))
            else if v.low > u.d
                bridgeCounter = bridgeCounter + 1
                bridge.push(edge(u,v))
            u.low = min(u.low, v.low)
        else if u.π != v
            u.low = min(u.low, v.d)
    u.color = BLACK
    time = time + 1
    u.f = time

C++ Code

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <limits>
#define MAX 101
using namespace std;

enum colors {BLACK, WHITE, GRAY};
int color[MAX], d[MAX], p[MAX], f[MAX], low[MAX], t, vertex, edge, bridgeCounter;
int NIL = numeric_limits<int>::min();
bool backEdge[MAX][MAX];

typedef pair<int,int> edges;
vector<edges> bridge;
vector<edges>::iterator it;

void ARTICULATION_BRIDGE(vector<int>[]);
void DFS(vector<int>[]);
void DFS_VISIT(vector<int>[],int);

int main(void)
{
    //freopen("articbridge.txt", "r", stdin);
    vector<int> adjList[MAX];
    int u, v;
    cin >> vertex >> edge;
    for(int e=1; e<=edge; e++) {
        cin >> u >> v;
        adjList[u].push_back(v);
        adjList[v].push_back(u);
    }
    ARTICULATION_BRIDGE(adjList);
    cout << bridgeCounter << " Ariculation Bridges." << endl;
    for(it=bridge.begin(); it != bridge.end(); ++it) {
        cout << it->first << " - " << it->second << endl;
    }
    return 0;
}

void ARTICULATION_BRIDGE(vector<int> G[]) {
    DFS(G);
    sort(bridge.begin(), bridge.end());
}

void DFS(vector<int> G[]) {
    for(int u=0; u<=vertex; u++) {
        color[u] = WHITE;
        p[u] = NIL;
    }
    t = 0, bridgeCounter = 0;
    for(int u=1; u<=vertex; u++) {
        if(color[u] == WHITE) {
            DFS_VISIT(G,u);
        }
    }
}

void DFS_VISIT(vector<int> G[], int u) {
    t = t + 1;
    d[u] = low[u] = t;
    color[u] = GRAY;
    for(int i=0; i<G[u].size(); i++) {
        int v = G[u][i];
        if(color[v] == WHITE) {
            p[v] = u;
            DFS_VISIT(G,v);
            if(d[u] == 1) {
                if(G[u].size() >= 2 && low[v] > d[u]) {
                    // special case for root
                    // root is an artic. point if there are two or more children
                    bridgeCounter++;
                    bridge.push_back(edges(u,v));
                }
            } else if(low[v] > d[u]) {
                bridgeCounter++;
                bridge.push_back(edges(u,v));
            }
            low[u] = min(low[u],low[v]);
        } else if(p[u] != v) {
            low[u] = min(low[u],d[v]);
        }
    }
    color[u] = BLACK;
    t = t + 1;
    f[u] = t;
}

Sample Input

23 32
1 2
1 3
1 4
2 3
2 4
3 4
3 5
5 7
5 6
5 8
5 9
5 11
6 7
8 9
9 10
11 13
11 14
12 15
12 14
12 13
15 16
15 19
16 18
16 17
16 19
17 18
18 19
19 20
19 21
21 22
21 23
22 23

Sample Output

6 Ariculation Bridges.
3 - 5
5 - 11
9 - 10
12 - 15
19 - 20
19 - 21

.:: Artic. Bridge Related UVa Problems ::.

---

• 796 - Critical Links

Refference: Introduction to Algorithms - Thomas H. Cormen