Reverse Delete algorithm is closely related to Kruskal’s algorithm. In Reverse Delete algorithm, we sort all edges in decreasing order of their weights. After sorting, we one by one pick edges in decreasing order. We include current picked edge if excluding current edge causes disconnection in current graph. The main idea is delete edge if its deletion does not lead to disconnection of graph. Your task is to print the value of total weight of Minimum Spanning Tree formed.
 
Example 1:
Input:
V = 4, E = 5
Arr[] = {0, 1, 10, 0, 2, 6, 0, 3, 5, 1, 3, 15, 2, 3, 4}
Output:
19
Explanation:
The weight of the Minimum Spanning
Tree formed is 19.
Example 1:
Input:
V = 4, E = 3
Arr[] = {0, 1, 98, 1, 3, 69, 0, 3, 25}
Output:
192
Explanation:
The weight of the Minimum Spanning
Tree formed is 192.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function RevDelMST() which takes 2 Integers V, and E and an array of length 3*E where each triplet consists of two nodes u and v and weight of thir edge w as input and returns the Weight of the Minimum Spanning Tree.
 
Expected Time Complexity: O(V*E)
Expected Auxiliary Space: O(E)
 
Constraints:
1 <= V,E <= 1000
1 <= u,v <= V
1 <= w <= 100

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def RevDelMST(self, Arr, V, E):

        # code here 

Solutions:
from collections import defaultdict

class Solution:

	def dfs(self, node, visited, adj):
		visited[node] = 1
		for nbr in adj[node]:
			if visited[nbr] == -1:
				self.dfs(nbr, visited, adj)

	def is_connected(self, V, adj):
		visited = [-1] * V
		cnt = 0
		for i in range(V):
			if visited[i] == -1:
				self.dfs(i, visited, adj)
				cnt += 1
		return cnt == 1

	def RevDelMST(self, arr, V, E):
		n = len(arr)
		adj = defaultdict(list)
		edges = []
		for i in range(0, n, 3):
			(u, v, w) = (arr[i], arr[i + 1], arr[i + 2])
			adj[u].append(v)
			adj[v].append(u)
			edges.append([u, v, w])
		edges.sort(key=lambda x: -x[2])
		cost = 0
		for (u, v, w) in edges:
			adj[u].remove(v)
			adj[v].remove(u)
			if not self.is_connected(V, adj):
				adj[u].append(v)
				adj[v].append(u)
				cost += w
		return cost


class Graph:

	def __init__(self, v):
		self.v = v
		self.adj = [0] * v
		self.edges = []
		for i in range(v):
			self.adj[i] = []

	def addEdge(self, u: int, v: int, w: int):
		self.adj[u].append(v)
		self.adj[v].append(u)
		self.edges.append((w, (u, v)))

	def dfs(self, v: int, visited: list):
		visited[v] = True
		for i in self.adj[v]:
			if not visited[i]:
				self.dfs(i, visited)

	def connected(self):
		visited = [False] * self.v
		self.dfs(0, visited)
		for i in range(1, self.v):
			if not visited[i]:
				return False
		return True

	def reverseDeleteMST(self):
		self.edges.sort(key=lambda a: a[0])
		mst_wt = 0
		for i in range(len(self.edges) - 1, -1, -1):
			u = self.edges[i][1][0]
			v = self.edges[i][1][1]
			self.adj[u].remove(v)
			self.adj[v].remove(u)
			if self.connected() == False:
				self.adj[u].append(v)
				self.adj[v].append(u)
				mst_wt += self.edges[i][0]
		return mst_wt

class Solution:

	def RevDelMST(self, Arr, V, E):
		g = Graph(V)
		for i in range(0, len(Arr), 3):
			g.addEdge(Arr[i], Arr[i + 1], Arr[i + 2])
		return g.reverseDeleteMST()


from collections import defaultdict

class Solution:

	def RevDelMST(self, Arr, V, E):
		graph = defaultdict(dict)
		matrix = []
		for i in range(0, len(Arr), 3):
			graph[Arr[i]][Arr[i + 1]] = Arr[i + 2]
			graph[Arr[i + 1]][Arr[i]] = Arr[i + 2]
			matrix.append([Arr[i], Arr[i + 1], Arr[i + 2]])
		count = 0
		matrix.sort(reverse=True, key=lambda x: x[2])
		for ele in matrix:
			del graph[ele[0]][ele[1]]
			del graph[ele[1]][ele[0]]
			if self.isConnected(graph, V, ele[0], ele[1]) == False:
				graph[ele[0]][ele[1]] = ele[2]
				graph[ele[1]][ele[0]] = ele[2]
				count += ele[2]
			else:
				continue
		return count

	def isConnected(self, graph, V, x, y):
		visited = [False] * V
		self.DFSHelper(0, graph, visited)
		for i in range(len(visited)):
			if visited[i] == False:
				return False
		return True

	def DFSHelper(self, node, graph, visited):
		visited[node] = True
		for (neighbor, weight) in graph[node].items():
			if visited[neighbor] == False:
				self.DFSHelper(neighbor, graph, visited)
			else:
				continue
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(V, E) = map(int, input().split())
		Arr = list(map(int, input().split()))
		ob = Solution()
		print(ob.RevDelMST(Arr, V, E))


class Solution:

	def RevDelMST(self, Arr, V, E):
		par = []
		rank = [1] * V
		edges = []
		for i in range(V):
			par.append(i)
		for i in range(0, len(Arr), 3):
			j = Arr[i]
			k = Arr[i + 1]
			l = Arr[i + 2]
			edges.append([l, j, k])
		edges.sort(key=lambda x: x[0])
		mst = []
		for (i, j, k) in edges:
			if not self.isConnected(j, k, par):
				mst.append([i, j, k])
				self.union(par, j, k, rank)
		su = 0
		for (i, j, k) in mst:
			su += i
		return su

	def pa(self, par, a):
		if par[a] == a:
			return a
		par[a] = self.pa(par, par[a])
		return par[a]

	def union(self, par, a, b, rank):
		para = self.pa(par, a)
		parb = self.pa(par, b)
		if rank[para] > rank[parb]:
			par[parb] = para
		elif rank[para] < rank[parb]:
			par[para] = parb
		else:
			rank[para] += 1
			par[parb] = para

	def isConnected(self, a, b, par):
		return self.pa(par, a) == self.pa(par, b)


class Solution:

	def findPar(self, node, parent):
		if node != parent[node]:
			parent[node] = self.findPar(parent[node], parent)
		return parent[node]

	def union(self, node1, node2, parent, rank):
		node1 = self.findPar(node1, parent)
		node2 = self.findPar(node2, parent)
		if rank[node1] > rank[node2]:
			parent[node2] = node1
		elif rank[node1] < rank[node2]:
			parent[node1] = node2
		else:
			parent[node1] = node2
			rank[node2] += 1

	def RevDelMST(self, Arr, V, E):
		ar = []
		for i in range(2, len(Arr), 3):
			ar.append((Arr[i], Arr[i - 1], Arr[i - 2]))
		ar = sorted(ar)
		parent = [i for i in range(V)]
		rank = [0] * V
		cost = 0
		for i in range(len(ar)):
			m_ele = ar[i]
			if self.findPar(m_ele[1], parent) != self.findPar(m_ele[2], parent):
				cost += m_ele[0]
				self.union(m_ele[1], m_ele[2], parent, rank)
		return cost


class Solution:

	def RevDelMST(self, Arr, n, E):
		edges = []
		for i in range(E):
			u = Arr[3 * i]
			v = Arr[3 * i + 1]
			w = Arr[3 * i + 2]
			edges.append([u, v, w])
		edges.sort(key=lambda x: x[2])
		parent = []
		rank = []
		for i in range(n):
			parent.append(i)
			rank.append(0)
		minWeight = 0
		for edge in edges:
			u = self.findByPathCompression(parent, edge[0])
			v = self.findByPathCompression(parent, edge[1])
			w = edge[2]
			if u != v:
				minWeight += w
				self.unionByRank(parent, rank, u, v)
		return minWeight

	def findByPathCompression(self, parent, node):
		if parent[node] == node:
			return node
		parent[node] = self.findByPathCompression(parent, parent[node])
		return parent[node]

	def unionByRank(self, parent, rank, u, v):
		if rank[u] < rank[v]:
			parent[u] = v
		elif rank[u] > rank[v]:
			parent[v] = u
		else:
			parent[v] = u
			rank[u] += 1


class Solution:

	def RevDelMST(self, arr, v, e):
		edges = []
		graph = [[0 for i in range(v)] for i in range(v)]
		for i in range(3, len(arr) + 1, 3):
			edges.append(arr[i - 3:i])
			graph[arr[i - 3]][arr[i - 2]] = 1
			graph[arr[i - 2]][arr[i - 3]] = 1

		def dfs(z, visited):
			visited[z] = 1
			for i in range(v):
				if graph[z][i] == 1 and (not visited[i]):
					dfs(i, visited)

		def connected():
			visited = [0] * v
			dfs(0, visited)
			for i in range(v):
				if visited[i] == 0:
					return 0
			return 1
		edges = sorted(edges, key=lambda x: x[2])
		ans = 0
		total = 0
		while edges:
			(u, e, w) = edges.pop()
			total += w
			graph[u][e] = 0
			graph[e][u] = 0
			if connected():
				ans += w
			else:
				graph[u][e] = 1
				graph[e][u] = 1
		return total - ans