Suppose I have an undirected graph G with vertices v1...vn and edges. Right now it is in adjacency list representation.
For every time moment I have as input some subset of vertices that are "active" at this moment. And I need to find all connected components in this subset of vertices for that time moment.
Right now I've implemented this using union-find data structure like this:
initialize sets for every active vertex so that every vertex has itself as "representative" (also called "parent") for every active vertex v for all neighbours of v in G v_neighbour if v_neighbour is active union set of v and set of v_neighbour
It should work OK, but I want to know if there is a more optimal approach? And what is the running time of that algorithm? O(N*M)?