TADM2E 6.13 - Revision history

Matt: Undo revision 1146 by FuckyouMatt (talk)

2020-08-02T12:09:33Z

Undo revision 1146 by FuckyouMatt (talk)

FuckyouMatt: Blanked the page

2020-08-02T02:11:30Z

Blanked the page

Nitely at 00:35, 11 November 2019

2019-11-11T00:35:29Z

Zholnin at 18:49, 21 December 2015

2015-12-21T18:49:41Z

Zholnin at 18:49, 21 December 2015

2015-12-21T18:49:02Z

Zholnin: Created page with "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..."

2015-12-21T18:48:39Z

Created page with "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..."

New page

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).
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.

← Older revision	Revision as of 12:09, 2 August 2020
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

← Older revision		Revision as of 02:11, 2 August 2020
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~~

← Older revision		Revision as of 00:35, 11 November 2019
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

@@ Line 3: / Line 3: @@
 This problem can be reduced to finding connected components in graph like this:
-. Union phase - on every call we add one more edge to our graph, which is O(m).
+. Union phase - on every call we add one more edge to our graph, which is O(m) total.
 <BR>
 . 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>
-. Find phase - on every call we just return component number from array.
+. Find phase - on every call we just return component number from array, which is O(m) total.