|
|
| Line 1: |
Line 1: |
| − | 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.
| |
| − | <BR>
| |
| − | 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.
| |
| − | <BR>
| |
| − | 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
| |
| − | <BR>
| |
| − | [1]: en.wikipedia.org/wiki/Disjoint-set_data_structure#Time_complexity
| |
