TADM2E 6.13

From Algorithm Wiki
Jump to: navigation, search

Not 100% certain:

This problem can be reduced to finding connected components in graph like this:

1. Union phase - on every call we add one more edge to our graph, which is O(m) total.
2. DFS phase - we use several runs of DFS algorithm. Every DFS call covers one component, so for each visited node we save DFS call number, which will be the number of component in the end. DFS search is O(n) or O(n+m), which is within limits.
3. Find phase - on every call we just return component number from array, which is O(m) total.

Total running time bound - O(n+m)