TADM2E 5.22 - Revision history

Matt: Undo revision 1064 by FuckMatt (talk)

2020-08-01T00:46:37Z

Undo revision 1064 by FuckMatt (talk)

Matt: Undo revision 1092 by FuckMatt (talk)

2020-08-01T00:46:21Z

Undo revision 1092 by FuckMatt (talk)

FuckMatt: Redirected page to UNTV

2020-07-31T10:16:21Z

Redirected page to UNTV

FuckMatt: Blanked the page

2020-07-31T09:37:52Z

Blanked the page

Matt: Undo revision 1009 by MattWars (talk)

2020-07-28T09:58:26Z

Undo revision 1009 by MattWars (talk)

Show changes

MattWars at 07:07, 28 July 2020

2020-07-28T07:07:30Z

Show changes

Bkarpov96: Undo revision 883 | Why are u doing this? What's the point? It's wiki for learning book

2020-07-23T08:13:47Z

Undo revision 883 | Why are u doing this? What's the point? It's wiki for learning book

Fucs: Undo revision 870 by Bkarpov96 (talk)

2020-07-22T22:53:30Z

Undo revision 870 by Bkarpov96 (talk)

Bkarpov96: Undo revision 856 by Bkarpov96Wars (talk)

2020-07-22T11:21:50Z

Undo revision 856 by Bkarpov96Wars (talk)

Bkarpov96Wars: Blanked the page

2020-07-22T00:21:41Z

Blanked the page

← Older revision	Revision as of 00:46, 1 August 2020
Line 1:	Line 1:
−	+	<pre>
	+	Working with the list of edges of an undirected graph G
	+	Read the edges of G and create an adjacency matrix A, and simultaneously calculate the degree of each vertex in the array B # O(m)
	+	- Consider an edge UW, if the data about it already exists A[U][W] == A[W][U] == 1, then a multiple edge is found, skip it
	+	Initialize the queue Q
	+	Add to Q all vertexes whose degree is 2 # O(n) iterations, O(1) get the vertex degree via the array B
	+	- The presence of a vertex in the queue is noted in the array C, which consists of bool flags
	+	Loop until the queue Q is empty: # O(n) iterations
	+	- Extract vertex V from Q # V has degree 2 => V located between vertexes U and W
	+	- Delete the edge UV, B[U] -= 1
	+	- Delete the edge VW, B[W] -= 1
	+	- Delete vertex V, C[V] = False
	+	- If U and W are not adjacent, connect U and W with an edge and increase the degrees of U and W by 1 # Checking the adjacency O(1) via the adjacency matrix
	+	- If U's degree is 2 and U is not in queue Q, add U to Q # Getting vertex degree via B O(1), checking for presence in the queue via C O(1)
	+	- If W's degree is 2 and W is not in queue Q, add W to Q
	+	</pre>--[[User:Bkarpov96\|Bkarpov96]] ([[User talk:Bkarpov96\|talk]]) 08:17, 7 July 2020 (UTC)

← Older revision		Revision as of 00:46, 1 August 2020
Line 1:		Line 1:
−	~~#REDIRECT [[UNTV]]~~	+

← Older revision	Revision as of 10:16, 31 July 2020
Line 1:	Line 1:
−	+	#REDIRECT [[UNTV]]

← Older revision		Revision as of 09:37, 31 July 2020
Line 1:		Line 1:
−	~~<pre>~~	+
−	~~Working with the list of edges of an undirected graph G~~
−	~~Read the edges of G and create an adjacency matrix A, and simultaneously calculate the degree of each vertex in the array B # O(m)~~
−	~~- Consider an edge UW, if the data about it already exists A[U][W] == A[W][U] == 1, then a multiple edge is found, skip it~~
−	~~Initialize the queue Q~~
−	~~Add to Q all vertexes whose degree is 2 # O(n) iterations, O(1) get the vertex degree via the array B~~
−	~~- The presence of a vertex in the queue is noted in the array C, which consists of bool flags~~
−	~~Loop until the queue Q is empty: # O(n) iterations~~
−	~~- Extract vertex V from Q # V has degree 2 => V located between vertexes U and W~~
−	~~- Delete the edge UV, B[U] -= 1~~
−	~~- Delete the edge VW, B[W] -= 1~~
−	~~- Delete vertex V, C[V] = False~~
−	~~- If U and W are not adjacent, connect U and W with an edge and increase the degrees of U and W by 1 # Checking the adjacency O(1) via the adjacency matrix~~
−	~~- If U's degree is 2 and U is not in queue Q, add U to Q # Getting vertex degree via B O(1), checking for presence in the queue via C O(1)~~
−	~~- If W's degree is 2 and W is not in queue Q, add W to Q~~
−	~~</pre>--[[User:Bkarpov96\|Bkarpov96]] ([[User talk:Bkarpov96\|talk]]) 08:17, 7 July 2020 (UTC)~~

← Older revision	Revision as of 08:13, 23 July 2020
Line 1:	Line 1:
−	+	<pre>
	+	Working with the list of edges of an undirected graph G
	+	Read the edges of G and create an adjacency matrix A, and simultaneously calculate the degree of each vertex in the array B # O(m)
	+	- Consider an edge UW, if the data about it already exists A[U][W] == A[W][U] == 1, then a multiple edge is found, skip it
	+	Initialize the queue Q
	+	Add to Q all vertexes whose degree is 2 # O(n) iterations, O(1) get the vertex degree via the array B
	+	- The presence of a vertex in the queue is noted in the array C, which consists of bool flags
	+	Loop until the queue Q is empty: # O(n) iterations
	+	- Extract vertex V from Q # V has degree 2 => V located between vertexes U and W
	+	- Delete the edge UV, B[U] -= 1
	+	- Delete the edge VW, B[W] -= 1
	+	- Delete vertex V, C[V] = False
	+	- If U and W are not adjacent, connect U and W with an edge and increase the degrees of U and W by 1 # Checking the adjacency O(1) via the adjacency matrix
	+	- If U's degree is 2 and U is not in queue Q, add U to Q # Getting vertex degree via B O(1), checking for presence in the queue via C O(1)
	+	- If W's degree is 2 and W is not in queue Q, add W to Q
	+	</pre>--[[User:Bkarpov96\|Bkarpov96]] ([[User talk:Bkarpov96\|talk]]) 08:17, 7 July 2020 (UTC)

← Older revision		Revision as of 22:53, 22 July 2020
Line 1:		Line 1:
−	~~<pre>~~	+
−	~~Working with the list of edges of an undirected graph G~~
−	~~Read the edges of G and create an adjacency matrix A, and simultaneously calculate the degree of each vertex in the array B # O(m)~~
−	~~- Consider an edge UW, if the data about it already exists A[U][W] == A[W][U] == 1, then a multiple edge is found, skip it~~
−	~~Initialize the queue Q~~
−	~~Add to Q all vertexes whose degree is 2 # O(n) iterations, O(1) get the vertex degree via the array B~~
−	~~- The presence of a vertex in the queue is noted in the array C, which consists of bool flags~~
−	~~Loop until the queue Q is empty: # O(n) iterations~~
−	~~- Extract vertex V from Q # V has degree 2 => V located between vertexes U and W~~
−	~~- Delete the edge UV, B[U] -= 1~~
−	~~- Delete the edge VW, B[W] -= 1~~
−	~~- Delete vertex V, C[V] = False~~
−	~~- If U and W are not adjacent, connect U and W with an edge and increase the degrees of U and W by 1 # Checking the adjacency O(1) via the adjacency matrix~~
−	~~- If U's degree is 2 and U is not in queue Q, add U to Q # Getting vertex degree via B O(1), checking for presence in the queue via C O(1)~~
−	~~- If W's degree is 2 and W is not in queue Q, add W to Q~~
−	~~</pre>--[[User:Bkarpov96\|Bkarpov96]] ([[User talk:Bkarpov96\|talk]]) 08:17, 7 July 2020 (UTC)~~

← Older revision	Revision as of 11:21, 22 July 2020
Line 1:	Line 1:
−	+	<pre>
	+	Working with the list of edges of an undirected graph G
	+	Read the edges of G and create an adjacency matrix A, and simultaneously calculate the degree of each vertex in the array B # O(m)
	+	- Consider an edge UW, if the data about it already exists A[U][W] == A[W][U] == 1, then a multiple edge is found, skip it
	+	Initialize the queue Q
	+	Add to Q all vertexes whose degree is 2 # O(n) iterations, O(1) get the vertex degree via the array B
	+	- The presence of a vertex in the queue is noted in the array C, which consists of bool flags
	+	Loop until the queue Q is empty: # O(n) iterations
	+	- Extract vertex V from Q # V has degree 2 => V located between vertexes U and W
	+	- Delete the edge UV, B[U] -= 1
	+	- Delete the edge VW, B[W] -= 1
	+	- Delete vertex V, C[V] = False
	+	- If U and W are not adjacent, connect U and W with an edge and increase the degrees of U and W by 1 # Checking the adjacency O(1) via the adjacency matrix
	+	- If U's degree is 2 and U is not in queue Q, add U to Q # Getting vertex degree via B O(1), checking for presence in the queue via C O(1)
	+	- If W's degree is 2 and W is not in queue Q, add W to Q
	+	</pre>--[[User:Bkarpov96\|Bkarpov96]] ([[User talk:Bkarpov96\|talk]]) 08:17, 7 July 2020 (UTC)

← Older revision		Revision as of 00:21, 22 July 2020
Line 1:		Line 1:
−	~~<pre>~~	+
−	~~Working with the list of edges of an undirected graph G~~
−	~~Read the edges of G and create an adjacency matrix A, and simultaneously calculate the degree of each vertex in the array B # O(m)~~
−	~~- Consider an edge UW, if the data about it already exists A[U][W] == A[W][U] == 1, then a multiple edge is found, skip it~~
−	~~Initialize the queue Q~~
−	~~Add to Q all vertexes whose degree is 2 # O(n) iterations, O(1) get the vertex degree via the array B~~
−	~~- The presence of a vertex in the queue is noted in the array C, which consists of bool flags~~
−	~~Loop until the queue Q is empty: # O(n) iterations~~
−	~~- Extract vertex V from Q # V has degree 2 => V located between vertexes U and W~~
−	~~- Delete the edge UV, B[U] -= 1~~
−	~~- Delete the edge VW, B[W] -= 1~~
−	~~- Delete vertex V, C[V] = False~~
−	~~- If U and W are not adjacent, connect U and W with an edge and increase the degrees of U and W by 1 # Checking the adjacency O(1) via the adjacency matrix~~
−	~~- If U's degree is 2 and U is not in queue Q, add U to Q # Getting vertex degree via B O(1), checking for presence in the queue via C O(1)~~
−	~~- If W's degree is 2 and W is not in queue Q, add W to Q~~
−	~~</pre>--[[User:Bkarpov96\|Bkarpov96]] ([[User talk:Bkarpov96\|talk]]) 08:17, 7 July 2020 (UTC)~~