Count disjoint digraphs

Question

I have a boolean[][] 2D-array called matrix, which encodes a directed graph such that if matrix[i][j] == true, then vertex j is connected to vertex i (the inverse is not necessarily true).
I'm trying to create a Java method that will determine how many disjoint directed graphs I have.

So for Example, if vertex 0 was connected to vertex 1, and vertex 2 was connected to vertex 3 (<code>[{{0,0,0,0},{1,0,0,0},{0,0,0,0},{0,0,1,0}}]</code> would be the 2D array), I would have 2 disjoint digraphs.

If there are no connections, the number of disjoint digraphs would equal the number of vertices.

Answer 1

Start with a list of all of the nodes in the tree. Consider these your unvisited nodes.

Then repeat the following process until your list of unvisited nodes is gone.

1. Create an empty set, the "node-set", to represent the nodes that live in the current node's graph.
2. Perform a search starting at the current node. For each node you encounter in the search, remove it from your unvisited node list, then: (1) if the node already exists in another node-set, merge the current node-set and that other node-set and stop your search from that node, or (2) if that node already exists in the current node-set, stop your search from that node, or (3) if you have never seen that node, add it to the current node-set.

Once this process is complete, your node-sets correspond to the nodes that uniquely exist in each disjoint graph, so the number of node-sets is the value you seek.

Answer 2

It seems that you don't need strong connection, so very effective algorithm for disjoint-set forests will do the job. After union phase you will only have to count nodes with parent = self

P.S. Sedgewick lection about it

Answer 3

public int countDisjointSubgraphs() {
    int len = matrix.length;
    int[] nodes = new int[len];
    for (int i = 0 ; i < len ; i++) nodes[i] = i;
    for (int i = 0 ; i < len ; i++) {
        for (int j = 0 ; j < len ; j++) {
            if (matrix[i][j] || matrix[j][i])
                for (int k = 0 ; k < len ; k++)
                    if (nodes[k] == nodes[i]) nodes[k] = j;
        }
    }
    ArrayList<Integer> list = new ArrayList<Integer>();
    for (int i : nodes)
        if (list.indexOf(i) < 0) list.add(i);
    return list.size();
}