Difference between revisions of "TADM2E 6.13"
From Algorithm Wiki
| Line 3: | Line 3: | ||
This problem can be reduced to finding connected components in graph like this: | 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). | + | 1. Union phase - on every call we add one more edge to our graph, which is O(m) total. |
<BR> | <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. | 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. | DFS search is O(n) or O(n+m), which is within limits. | ||
<BR> | <BR> | ||
| − | 3. Find phase - on every call we just return component number from array. | + | 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) | ||
Revision as of 18:49, 21 December 2015
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)
