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)?