Given an integer N, denoting the number of computers connected by cables forming a network and a 2d array connections[][], with each row (i, j) representing a connection between i^{th} and j^{th} computer, the task is to connect all the computers either directly or indirectly by removing any of the given connections and connecting two disconnected computers. 
If its not possible to connect all the computers, print -1. 
Otherwise, print the minimum number of such operations required.
Example 1:
Input:
N = 4 
connections[][] = {{0, 1}, {0, 2}, {1, 2}}
Output:
1
Explanation: 
Remove the connection between computers 1 and 2 and connect computers 1 and 3.
Example 2:
Input:
N = 5
connections[][] = {{0, 1}, {0, 2}, {3, 4}, {2, 3}}
Output:
0
Explanation:
No removal of connections is required.
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function minimizeConnections() which takes the array connections[], number of computers N as input parameters and returns the minimum number of operations required to connect all computers with each other. If it is not possible to do so then return -1.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= N <= 10^{3}
0<=connections[i][0],connections[i][1]

Source: geeksforgeeks | Difficulty: EASY

Starter code: from typing import List





class Solution:

    def minimumConnections(self, n : int, m : int, c : List[List[int]]) -> int:

        # code here

        



Solutions:
from typing import List
from collections import defaultdict

class Solution:

	def minimumConnections(self, n: int, m: int, c: List[List[int]]) -> int:
		adj = [[] for _ in range(n)]
		for (i, j) in c:
			adj[i].append(j)
			adj[j].append(i)

		def dfs(i):
			q = [i]
			while len(q):
				for i in range(len(q)):
					s = q.pop(0)
					for nei in adj[s]:
						if not visited[nei]:
							visited[nei] = True
							q.append(nei)
		visited = [False] * n
		count = 0
		for i in range(n):
			if not visited[i]:
				visited[i] = True
				dfs(i)
				count += 1
		redundant = m - (n - 1)
		if redundant >= 0:
			return count - 1
		return -1


from typing import List

class DisjointSet:

	def __init__(self, n):
		self.parent = [i for i in range(n + 1)]
		self.rank = [0 for i in range(n + 1)]

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

	def unionbyrank(self, u, v):
		upu = self.findparent(u)
		upv = self.findparent(v)
		if self.rank[upu] < self.rank[upv]:
			self.parent[upu] = upv
		elif self.rank[upv] < self.rank[upu]:
			self.parent[upv] = upu
		else:
			self.parent[upv] = upu
			self.rank[upu] += 1

class Solution:

	def minimumConnections(self, n: int, m: int, c: List[List[int]]) -> int:
		ds = DisjointSet(n)
		extra = 0
		count = 0
		for (u, v) in c:
			if ds.findparent(u) == ds.findparent(v):
				extra += 1
			else:
				ds.unionbyrank(u, v)
		for i in range(0, n):
			if ds.parent[i] == i:
				count += 1
		ans = count - 1
		if extra >= ans:
			return ans
		return -1


from typing import List

class UnionFind:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.size = [1 for i in range(n)]

	def union(self, u, v):
		parent_u = self.find(u)
		parent_v = self.find(v)
		if parent_u == parent_v:
			return True
		if self.size[parent_u] < self.size[parent_v]:
			self.parent[parent_u] = parent_v
			self.size[parent_v] += self.size[parent_u]
		else:
			self.parent[parent_v] = parent_u
			self.size[parent_u] += self.size[parent_v]
		return False

	def find(self, u):
		if u == self.parent[u]:
			return u
		self.parent[u] = self.find(self.parent[u])
		return self.parent[u]

class Solution:

	def minimumConnections(self, n: int, m: int, c: List[List[int]]) -> int:
		ds = UnionFind(n)
		cntExtras = 0
		for i in c:
			(u, v) = (i[0], i[1])
			if ds.find(u) == ds.find(v):
				cntExtras += 1
			else:
				ds.union(u, v)
		cntc = 0
		for i in range(n):
			if ds.find(i) == i:
				cntc += 1
		ans = cntc - 1
		if cntExtras >= ans:
			return ans
		return -1


from typing import List
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def dfs(self, node, vis, adj):
		if vis[node]:
			return
		vis[node] = True
		if node in adj:
			for nbr in adj[node]:
				if vis[nbr] == False:
					self.dfs(nbr, vis, adj)

	def solve(self, n, m, connections):
		vis = [False] * n
		adj = defaultdict(list)
		edges = 0
		for i in range(m):
			u = connections[i][0]
			v = connections[i][1]
			adj[u].append(v)
			adj[v].append(u)
			edges += 1
		components = 0
		for i in range(n):
			if vis[i] == False:
				components += 1
				self.dfs(i, vis, adj)
		if edges < n - 1:
			return -1
		redundant = edges - (n - 1 - (components - 1))
		if redundant >= components - 1:
			return components - 1
		return -1

	def minimumConnections(self, n: int, m: int, connections: List[List[int]]) -> int:
		minOps = self.solve(n, m, connections)
		return minOps


from typing import List

class Solution:

	def minimumConnections(self, n: int, m: int, c: List[List[int]]) -> int:
		import sys
		sys.setrecursionlimit(110000001)
		if m < n - 1:
			return -1

		def DFS(i):
			visited[i] = True
			for x in G[i]:
				if not visited[x]:
					DFS(x)
		G = {}
		for i in range(n):
			G[i] = set()
		for (x, y) in c:
			G[x].add(y)
			G[y].add(x)
		visited = [False for i in range(n)]
		count = -1
		for i in range(n):
			if not visited[i]:
				count += 1
				DFS(i)
		return count