Thread: Disjoint set

but heard one can use multimaps

Well, if you want the nodes of each connected set, yes. Use a standard simple disjoint subgraph finder (pretty trivial using any kind of search), and keep a counter that counts the number of subgraphs you've found. And, while you walk the graph, add each node to the multimap, using the current count as an index. When you're done, the multimap will contain one key per subgraph, and all the nodes of the subgraph will be mapped at this key.

But since the key set is integral, 0-based and continuous, it intuitively sounds better to use a simple array/vector as the map, mapping to another container type.

http://www.boost.org/doc/libs/1_36_0...omponents.html

Do you understand how depth first visitation works? Given such a visitation function, you could write it as pseudo-code:

Code:

multimap<int, vertex> components;
graph g;
int currentComponent = 0;

for every vertex v in g {
  if v not marked {
    visit_depth(v, visitor);
    ++currentComponent;
  }
}
where visitor = function(vertex w) {
  mark w;
  insert w into components with key currentComponent;
}