C++ :: Articulation Points Detection Algorithm

PSEUDOCODE

ARTICULATION-POINTS-DFS-VISIT(G,u)
    dfn = dfn + 1
    u.d = u.low = dfn
    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
                    articPointsList.push_front(u)
            else if v.low >= u.d
                articPointsList.push_front(u)
            u.low = min(u.low, v.low)
        else if u.π != v
            u.low = min(u.low, v.d)
    u.color = BLACK

C++ Code

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <list>
#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;
int NIL = numeric_limits<int>::min();
bool backEdge[MAX][MAX];

list<int> articPoints;
list<int>::iterator it;

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

int main(void)
{
    //freopen("articpoints.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_POINTS(adjList);
    for(it=articPoints.begin(); it != articPoints.end(); ++it) {
        cout << *it << ends;
    }
    return 0;
}

void ARTICULATION_POINTS(vector<int> G[]) {
    DFS(G);
    articPoints.sort();
    articPoints.unique();
}

void DFS(vector<int> G[]) {
    for(int u=0; u<=vertex; u++) {
        color[u] = WHITE;
        p[u] = NIL;
    }
    t = 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
                    articPoints.push_front(u);
                }
            } else if(low[v] >= d[u]) {
                articPoints.push_front(u);
            }
            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

19 26
1 2
1 4
2 3
2 5
2 7
2 8
3 4
3 10
3 9
5 6
5 7
5 8
7 8
8 11
8 13
11 12
11 14
11 16
11 17
12 13
12 19
12 18
14 15
14 16
14 17
16 17

Sample Output

2 3 5 8 11 12 14

Refference: Introduction to Algorithms - Thomas H. Cormen