efficiently find connected components in undirected graph considering transitive equivalence
Using depth-first search, compute the connected components, by constructing a mapping that maps each node in a connected component to the first node you visited in that component. This is linear in the number of nodes and edges. Preserve that mapping. Two nodes are equivalent if and only if they map to the same node.