Cut Vertices (Articulation Points)

Runtime: O(E + V)

Finds all cut vertices in a graph.

High-Level Description

Do a depth-first search from an arbitrary vertex, and keep track of two quantites, Num and Low. Num[i] is simply the number of vertex i, in the order you come across it in the DFS. So, the vertex you start from is 0, and the next vertex you go to is 1, and so on. Low[i] is the minimum of Num[i], Num[x] where x is a vertex that connects to i directly, and Low[y], where y is a vertex that connects to i directly and has Num[y] > Num[i].

Intuitively, Low[i] is the lowest Num[x] amongst all vertices x that you can reach from vertex i by only going forwards in the DFS tree.

Now, to find articulation points, look for vertices i that have children, x, in the DFS tree such that Low[x] >= Num[i]. That means that x cannot reach any vertices higher than i in the DFS tree, and therefore it would disconnect x from some part of the graph if it was removed.

There is a special case for the root of the DFS tree. The root is an articulation point iff it has two children in the DFS tree.

Java

a[][] is an adjacency matrix.

n is the number of vertices.

k is just a counter for assigning num[i]

num and low are arrays as described above.

children[i] is a list of i's children in the DFS tree.

This code assumes a dense, undirected, possibly unconnected graph. It's fairly trivial to handle directed graphs, or sparse graphs.

static boolean[][] a;
static int n, k;
static int[] num, low;
static ArrayList<Integer>[] children;

public static void main(String args[])
{
    Scanner scan = new Scanner(System.in);

    while(true)
    {
        a = new boolean[n][n]; //Adjacency matrix
        HashSet<Integer> roots = new HashSet<Integer>(); //Set of all roots

        num = new int[n];
        low = new int[n];
        children = new ArrayList[n];
        k = 0;
        Arrays.fill(num, -1);
        Arrays.fill(low, 999999999);

        for(int i=0;i < n;i++)
            children[i] = new ArrayList<Integer>();

        for(int i=0;i < n;i++)
        {
            if(num[i] == -1)
            {
                getNumLow(i);
                roots.add(i);
            }
        }
       
        int rtn = 0;

        //Check roots separately
        for(int v : roots)
        {
            if(children[v].size() > 1)
                rtn++;
        }

        //Check other vertices
        for(int i=0;i < n;i++)
        {
            if(roots.contains(i))
                continue;

            for(int j=0;j < children[i].size();j++)
            {
                int v = children[i].get(j);
                if(low[v] >= num[i])
                {
                    rtn++;
                    break;
                }
            }
        }

        System.out.println(rtn);
    }
}



public static int getNumLow(int v)
{
    num[v] = k++;
    low[v] = num[v];

    for(int i=0;i < n;i++) //Note: This is not sparse! Replace with edge array for sparseness
    {
        if(a[v][i] && num[i] >= 0)
        {
            low[v] = Math.min(low[v], num[i]);
        }
        if(a[v][i] && num[i] == -1)
        {
            low[v] = Math.min(low[v], getNumLow(i));
            children[v].add(i);
        }
    }

    return low[v];
}

UVa

• Problem 315 (Network)
• Problem 10199 (Tourist Guide)