There are n stones at some integer coordinate points on a 2D plane. Each coordinate point may have at most one stone.
You need to remove some stones. 
A stone can be removed if it shares either the same row or the same column as another stone that has not been removed.
Given an array stones of length n where stones[i] = [xi, yi] represents the location of the ith stone, return the maximum possible number of stones that you can remove.
 
Example 1:
Input:
n=6
[[0 0] ,[ 0 1], [1 0] ,[1 2] ,[2 1] ,[2 2]]
Output:
5
Example:
One way to remove 5 stones are
1--[0,0]
2--[1,0]
3--[0,1]
4--[2,1]
5--[1,2]
Your Task:
You don't need to print or input anything. Complete the function maxRemove() which takes an integer array arr, an integer n as the input parameters and returns an integer, denoting the maximum number of stones that can be removed.
 
Expected Time Complexity: O(N+K)
Expected Space Complexity: O(K)
 
Constraints:
1 <= n <=1000
0 <= x[i], y[i]<= 10^{4}
No two stones are at same position.

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3



class Solution:

    def maxRemove(self, adj, n):

        # Code here

Solutions:
class DisjointSet:

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

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

	def unionByRank(self, u, v):
		up_u = self.findUParent(u)
		up_v = self.findUParent(v)
		if up_u == up_v:
			return
		if self.rank[up_u] < self.rank[up_v]:
			self.parent[up_u] = up_v
		elif self.rank[up_v] < self.rank[up_u]:
			self.parent[up_v] = up_u
		else:
			self.parent[up_v] = up_u
			self.rank[up_u] += 1
		return

	def unionBySize(self, u, v):
		up_u = self.findUParent(u)
		up_v = self.findUParent(v)
		if up_u == up_v:
			return
		if self.size[up_u] < self.size[up_v]:
			self.parent[up_u] = up_v
			self.size[up_v] += self.size[up_u]
		else:
			self.parent[up_v] = up_u
			self.size[up_u] += self.size[up_v]
		return

class Solution:

	def maxRemove(self, adj, n):
		maxr = 0
		maxc = 0
		for i in range(len(adj)):
			maxr = max(maxr, adj[i][0])
			maxc = max(maxc, adj[i][1])
		ds = DisjointSet(maxr + 1 + maxc + 1)
		for i in range(n):
			row = adj[i][0]
			col = adj[i][1] + maxr + 1
			ds.unionBySize(row, col)
		bosses = 0
		for i in range(len(ds.parent)):
			if ds.findUParent(i) == i and ds.size[i] > 1:
				bosses += 1
		return n - bosses


class Solution:

	def dfs(self, g, v, marked):
		marked[v] = 1
		for w in g[v]:
			if marked[w] == 0:
				self.dfs(g, w, marked)

	def maxRemove(self, adj, n):
		g = [[] for _ in range(n)]
		r_adj = {}
		for i in range(n):
			r_adj[adj[i][0] * n + adj[i][1]] = i
			for j in range(i + 1, n):
				if adj[i][0] == adj[j][0] or adj[i][1] == adj[j][1]:
					g[i].append(j)
					g[j].append(i)
		marked = [0] * n
		ans = 0
		for i in range(n):
			if not marked[i]:
				ans += 1
				self.dfs(g, i, marked)
		return n - ans


class Solution:

	def maxRemove(self, adj, n):
		r = 0
		c = 0
		for it in adj:
			r = max(r, it[0])
			c = max(c, it[1])
		ds = disjoint(r + c + 1)
		d = {}
		for it in adj:
			noderow = it[0]
			nodecol = it[1] + r + 1
			ds.unionsize(noderow, nodecol)
			d[noderow] = 1
			d[nodecol] = 1
		c = 0
		for it in d:
			if ds.findUPar(it) == it:
				c += 1
		return n - c

class disjoint:

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

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

	def unionsize(self, u, v):
		Up_u = self.findUPar(u)
		Up_v = self.findUPar(v)
		if Up_u == Up_v:
			return
		if self.size[Up_u] < self.size[Up_v]:
			self.parent[Up_u] = Up_v
			self.size[Up_v] += self.size[Up_u]
		else:
			self.parent[Up_v] = Up_u
			self.size[Up_u] += self.size[Up_v]


class Solution:

	def maxRemove(self, adj, n):
		stones = adj
		maxRow = 0
		maxCol = 0
		for (i, j) in stones:
			maxRow = max(maxRow, i)
			maxCol = max(maxCol, j)
		ds = disjoint(maxRow + maxCol + 1)
		stoneNode = {}
		for i in stones:
			nodeRow = i[0]
			nodeCol = i[1] + maxRow + 1
			ds.unionsize(nodeRow, nodeCol)
			stoneNode[nodeRow] = 1
			stoneNode[nodeCol] = 1
		count = 0
		for i in stoneNode:
			if ds.findUPar(i) == i:
				count += 1
		return len(stones) - count

class disjoint:

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

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

	def unionsize(self, u, v):
		Up_u = self.findUPar(u)
		Up_v = self.findUPar(v)
		if Up_u == Up_v:
			return
		if self.size[Up_u] < self.size[Up_v]:
			self.parent[Up_u] = Up_v
			self.size[Up_v] += self.size[Up_u]
		else:
			self.parent[Up_v] = Up_u
			self.size[Up_u] += self.size[Up_v]


class Solution:

	def maxRemove(self, stones, n):

		def find(u):
			if u == parent[u]:
				return u
			else:
				parent[u] = find(parent[u])
				return parent[u]

		def union(u, v):
			(pu, pv) = (find(u), find(v))
			if pu == pv:
				return
			if size[pv] > size[pu]:
				parent[pu] = pv
				size[pv] += size[pu]
			else:
				parent[pv] = pu
				size[pu] += size[pv]
		mr = mc = 0
		for (i, j) in stones:
			mr = max(mr, i)
			mc = max(mc, j)
		parent = [i for i in range(mr + mc + 2)]
		size = [1 for i in range(mr + mc + 2)]
		d = {}
		for (i, j) in stones:
			union(i, j + mr + 1)
			d[i] = 1
			d[j + mr + 1] = 1
		c = 0
		for i in d:
			if find(i) == i:
				c += 1
		return n - c


from collections import defaultdict

class DisjointSet:

	def __init__(self, n):
		self.rank = [0] * (n + 1)
		self.size = [1] * (n + 1)
		self.parent = list(range(n + 1))

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

	def unionByRank(self, u, v):
		ulp_u = self.findUPar(u)
		ulp_v = self.findUPar(v)
		if ulp_u == ulp_v:
			return
		if self.rank[ulp_u] < self.rank[ulp_v]:
			self.parent[ulp_u] = ulp_v
		elif self.rank[ulp_v] < self.rank[ulp_u]:
			self.parent[ulp_v] = ulp_u
		else:
			self.parent[ulp_v] = ulp_u
			self.rank[ulp_u] += 1

	def unionBySize(self, u, v):
		ulp_u = self.findUPar(u)
		ulp_v = self.findUPar(v)
		if ulp_u == ulp_v:
			return
		if self.size[ulp_u] < self.size[ulp_v]:
			self.parent[ulp_u] = ulp_v
			self.size[ulp_v] += self.size[ulp_u]
		else:
			self.parent[ulp_v] = ulp_u
			self.size[ulp_u] += self.size[ulp_v]

class Solution:

	def maxRemove(self, adj, n):
		maxrow = 0
		maxcol = 0
		for (row, col) in adj:
			maxrow = max(maxrow, row)
			maxcol = max(maxcol, col)
		dsu = DisjointSet(maxrow + maxcol + 1)
		stonemap = defaultdict(int)
		for (r, c) in adj:
			rownode = r
			colnode = c + maxrow + 1
			dsu.unionBySize(rownode, colnode)
			stonemap[rownode] = 1
			stonemap[colnode] = 1
		cnt = 0
		for it in stonemap:
			if dsu.findUPar(it) == it:
				cnt += 1
		return n - cnt


class Solution:

	def maxRemove(self, adj, n):
		max_row = 0
		max_col = 0
		for i in adj:
			max_row = max(max_row, i[0])
			max_col = max(max_col, i[1])
		par = [i for i in range(max_row + max_col + 2)]
		vis = set()
		for (x, y) in adj:
			y = y + max_row + 1
			par_x = x
			par_y = y
			vis.add(par_x)
			vis.add(par_y)
			while par_x != par[par_x]:
				par_x = par[par_x]
			while par_y != par[par_y]:
				par_y = par[par_y]
			if par_x != par_y:
				par[par_x] = par_y
		cnt = 0
		for el in vis:
			if par[el] == el:
				cnt += 1
		return n - cnt


class Solution:

	def find(self, n, par):
		if par[n] == n:
			return n
		par[n] = self.find(par[n], par)
		return par[n]

	def union(self, x, y, size, par):
		(a, b) = (self.find(x, par), self.find(y, par))
		if a == b:
			return
		if size[a] < size[b]:
			par[a] = b
			size[b] += size[a]
		else:
			par[b] = a
			size[a] += size[b]

	def maxRemove(self, adj, n):
		(maxi1, maxi2) = (0, 0)
		c = 0
		for i in range(len(adj)):
			maxi1 = max(maxi1, adj[i][0])
			maxi2 = max(maxi2, adj[i][1])
		par = [i for i in range(maxi1 + maxi2 + 2)]
		size = [1 for i in range(maxi1 + maxi2 + 2)]
		visited = [0 for i in range(maxi1 + maxi2 + 2)]
		for i in adj:
			t1 = i[0]
			t2 = i[1] + maxi1 + 1
			self.union(t1, t2, size, par)
			visited[t1] = 1
			visited[t2] = 1
		for i in range(maxi1 + maxi2 + 2):
			if par[i] == i and visited[i] == 1:
				c += 1
		return len(adj) - c


class Solution:

	def maxRemove(self, adj, n):
		max_row = 0
		max_col = 0
		for i in adj:
			max_row = max(max_row, i[0])
			max_col = max(max_col, i[1])
		ds = disjoinset(max_row + max_col + 2)
		s = {}
		for i in adj:
			row_node = i[0]
			col_node = i[1] + max_row + 1
			ds.union(row_node, col_node)
			s[row_node] = 1
			s[col_node] = 1
		count = 0
		for i in s:
			if ds.parent[i] == i:
				count += 1
		return len(adj) - count

class disjoinset:

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

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

	def union(self, a, b):
		pa = self.find(a)
		pb = self.find(b)
		if pa == pb:
			return
		if self.rank[pa] > self.rank[pb]:
			self.parent[pb] = pa
			self.rank[pa] += self.rank[pb]
		else:
			self.parent[pa] = pb
			self.rank[pb] += self.rank[pa]


from collections import defaultdict

class UnionFind:

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

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

	def union(self, u, v):
		(rootx, rooty) = (self.find(u), self.find(v))
		if self.rank[rootx] < self.rank[rooty]:
			self.parent[rootx] = rooty
		elif self.rank[rootx] > self.rank[rooty]:
			self.parent[rooty] = rootx
		else:
			self.parent[rooty] = rootx
			self.rank[rootx] += 1

class Solution:

	def maxRemove(self, stones, n):
		un = UnionFind(n)
		rows = defaultdict(set)
		cols = defaultdict(set)
		for i in range(n):
			row_i = stones[i][0]
			col_i = stones[i][1]
			for j in rows[row_i]:
				if un.find(i) != un.find(j):
					un.union(i, j)
			for j in cols[col_i]:
				if un.find(i) != un.find(j):
					un.union(i, j)
			rows[row_i].add(i)
			cols[col_i].add(i)
		groups = set()
		for i in range(n):
			groups.add(un.find(i))
		return n - len(groups)


class DisjointSet:

	def __init__(self, n):
		self.parentArray = [i for i in range(n + 1)]
		self.sizeArray = [1 for i in range(n + 1)]

	def findUltimateParent(self, node):
		if self.parentArray[node] == node:
			return node
		self.parentArray[node] = self.findUltimateParent(self.parentArray[node])
		return self.parentArray[node]

	def unionBySize(self, u, v):
		parentU = self.findUltimateParent(u)
		parentV = self.findUltimateParent(v)
		if parentU == parentV:
			return
		if self.sizeArray[parentU] < self.sizeArray[parentV]:
			self.parentArray[parentU] = parentV
			self.sizeArray[parentV] += self.sizeArray[parentU]
		else:
			self.parentArray[parentV] = parentU
			self.sizeArray[parentU] += self.sizeArray[parentV]

class Solution:

	def maxRemove(self, stones, n) -> int:
		maxRow = 0
		maxCol = 0
		for (i, j) in stones:
			maxRow = max(maxRow, i)
			maxCol = max(maxCol, j)
		ds = DisjointSet(maxRow + maxCol + 1)
		stoneNode = {}
		for i in stones:
			nodeRow = i[0]
			nodeCol = i[1] + maxRow + 1
			ds.unionBySize(nodeRow, nodeCol)
			stoneNode[nodeRow] = 1
			stoneNode[nodeCol] = 1
		count = 0
		for i in stoneNode:
			if ds.findUltimateParent(i) == i:
				count += 1
		return len(stones) - count