Difference between revisions of "TADM2E 6.13"

From Algorithm Wiki
Jump to: navigation, search
 
Line 11: Line 11:
  
 
Total running time bound - O(n+m)
 
Total running time bound - O(n+m)
 +
 +
------------------------------------------------------------
 +
 +
We can use union-set provided by Skiena's book. Modify the find function replacing it by path compression, splitting, or halving [0]. Using both this and union by size make find and union run in (amortized) constant time [1]. Initializing the union-set is O(n), and running "m" union and finds are O(2m). Thus, the total running time is O(n+m)
 +
 +
[0]: en.wikipedia.org/wiki/Disjoint-set_data_structure#Pseudocode
 +
<BR>
 +
[1]: en.wikipedia.org/wiki/Disjoint-set_data_structure#Time_complexity

Latest revision as of 00:35, 11 November 2019

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)


We can use union-set provided by Skiena's book. Modify the find function replacing it by path compression, splitting, or halving [0]. Using both this and union by size make find and union run in (amortized) constant time [1]. Initializing the union-set is O(n), and running "m" union and finds are O(2m). Thus, the total running time is O(n+m)

[0]: en.wikipedia.org/wiki/Disjoint-set_data_structure#Pseudocode
[1]: en.wikipedia.org/wiki/Disjoint-set_data_structure#Time_complexity