Algorithm to find vertex subsets induced by connected components of a bipartite graph

Question

Given a bipartite graph G = (U, V, E), I want to find all (maximal) subsets of V which are one "side" of a connected component of G.

For example, for the incidence matrix

    0 1 0 0 0 1
    1 0 0 0 0 1
    0 0 0 0 0 0
A = 0 0 0 0 1 0
    0 0 1 0 1 0
    0 1 0 0 0 0
    0 0 0 1 0 0

where the row indices represent U and the column indices represent V, the output should be the sets {0, 1, 5}, {2, 4}, and {3}.

Is this equivalent to any standard problem? More to the point, is there an efficient solution?

Answer 1

This is similar to finding all the connected components of a graph, which is linear in the number of edges and vertices. The standard algorithm for this approach is to do a breadth or depth first search on every vertex.

I don't think there would be a complexity speed up by leveraging the bipartite nature of the graph, except for reducing the constants associated with this algorithm.