Geek is a chemical scientist who is performing an experiment to find an antidote to a poison. The experiment involves mixing some solutions in a flask. Based on the theoretical research Geek has done, he came up with an n * 2 array 'mix', where mix[i] = {X, Y} denotes solutions X and Y that needs to be mixed.
Also, from his past experience, it has been known that mixing some solutions leads to an explosion and thereby completely ruining the experiment. The explosive solutions are also provided as a m * 2 array 'danger' where danger[i] = {P, Q} denotes that if somehow solutions P and Q get into the same flask it will result in an explosion.
Help the Geek by returning an array 'answer' of size n, where answer[i] = "Yes" if it is safe to mix solutions in 'mix[i]' or else answer[i] = "No". 
Note: Geek should follow the order of mixing of solutions as it is in 'mix' otherwise the antidote will be ineffective. Also, Geek will not mix the solutions in 'mix[i]' once he gets to know that mixing them will result in an explosion. Mixing a solution will effect the other solutions which will appear after it. 
Example 1:
Input:
n = 5, m = 2
mix = {{1, 2}, {2, 3}, {4, 5}, {3, 5}, {2, 4}}
danger = {{1, 3}, {4, 2}}
Output:
answer = {"Yes", "No", "Yes", "Yes", "No"}
Explanation:
Mixing the first solution(1 and 2) of 'mix' do not result in any kind of explosion hence answer[0] is "Yes", while mixing(2nd solution) 2 and 3 is not allowed because it will result in an explosion as 1 and 3 would be in same solution hence we have returned "No" as the answer for 2nd solution. Mixing the third solution(4 and 5) and 4th solution(3 and 5) of 'mix' do not result in any kind of explosion hence answer[2] and answer[3] is "Yes". While mixing 2 and 4 is not allowed because it will result in an explosion hence we have returned "No" as the answer for it.
Example 2:
Input:
n = 3, m = 2
mix = {{1, 2}, {2, 3}, {1, 3}}
danger = {{1, 2}, {1, 3}}
Output:
answer = {"No", "Yes", "No"}
Explanation:
Mixing solutions 1 and 2 is dangerous hence 
answer[0] = "No", but solutions 2 and 3 can 
be mixed without any problem therefore answer[1] 
= "Yes". Again, mixing solutions 1 and 3 is 
dangerous due to which answer[2] = "No".
 
Your Task:
You don't need to read input or print anything. Complete the function avoidExplosion() which takes the mix array, its size, danger array, and its size as input parameters and returns the result array or list.
Expected Time Complexity: O(n*m*log(n))
Expected Space Complexity: O(n)
 
Constraints:
0 < n < 1000
0 < m < 1000
1 <= mix[i][0], mix[i][1] <= n
1 <= danger[i][0], danger[i][1] <= n
mix[i][0] != mix[i][1]
danger[i][0] != danger[i][1]

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Spanning trees

Graph algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def avoidExlosion(self, mix, n, danger, m):

        #code here

Solutions:
class Solution:

	def avoidExlosion(self, mix, n, danger, m):

		def find(x):
			if par[x] != x:
				par[x] = find(par[x])
			return par[x]

		def union(u, v):
			u = par[u]
			v = par[v]
			if rank[u] > rank[v]:
				par[v] = u
			elif rank[u] < rank[v]:
				par[u] = v
			else:
				par[u] = v
				rank[v] += 1
		ans = []
		par = [0] * (n + 1)
		rank = [0] * (n + 1)
		for i in range(n + 1):
			par[i] = i
		for i in range(n):
			x = mix[i][0]
			y = mix[i][1]
			(px, py) = (find(x), find(y))
			boolean = True
			for j in range(m):
				(a, b) = (danger[j][0], danger[j][1])
				(pa, pb) = (find(a), find(b))
				if px == pa and py == pb or (px == pb and py == pa):
					boolean = False
			if boolean:
				union(x, y)
			if boolean:
				ans.append('Yes')
			else:
				ans.append('No')
		return ans


class Solution:

	def avoidExlosion(self, mix, n, danger, m):
		arr = [i for i in range(n + 1)]

		def union(i, j):
			(r1, r2) = (find(i), find(j))
			if r1 != r2:
				arr[r1] = r2
			return r2

		def find(i):
			while i != arr[i]:
				i = arr[i]
			return i
		ans = []
		for (x, y) in mix:
			(rx, ry) = (find(x), find(y))
			for (p, q) in danger:
				(rp, rq) = (find(p), find(q))
				if (rx, ry) == (rp, rq) or (rx, ry) == (rq, rp):
					ans.append('No')
					break
			else:
				union(rx, ry)
				ans.append('Yes')
		return ans


class Solution:

	def avoidExlosion(self, mix, n, danger, m):

		def makeparent(a, b):
			a = find(a)
			b = find(b)
			par[b] = a

		def find(a):
			while par[a] != a:
				a = par[a]
			return a
		par = [i for i in range(n + 2)]
		ans = []
		for (a, b) in mix:
			p1 = find(a)
			p2 = find(b)
			flag = 0
			for (c, d) in danger:
				p3 = find(c)
				p4 = find(d)
				if p1 == p3 and p2 == p4 or (p1 == p4 and p2 == p3):
					flag = 1
					break
			if flag:
				ans.append('No')
			else:
				ans.append('Yes')
				makeparent(a, b)
		return ans


class Solution:

	def avoidExlosion(self, mix, n, danger, m):
		rank = [0] * (n + 1)
		par = [i for i in range(n + 1)]
		ans = []

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

		def make(a, b):
			if rank[a] > rank[b]:
				par[b] = a
				rank[a] += 1
			else:
				par[a] = b
				rank[b] += 1
		for (i, j) in mix:
			a = find(i)
			b = find(j)
			for (x, y) in danger:
				s = find(x)
				t = find(y)
				if a == s and b == t or (a == t and b == s):
					ans.append('No')
					break
			else:
				make(a, b)
				ans.append('Yes')
		return ans


class Solution:

	def findParent(self, curr, parent):
		if curr == parent[curr]:
			return curr
		parent[curr] = self.findParent(parent[curr], parent)
		return parent[curr]

	def mergeParent(self, first, second, parent):
		a = self.findParent(first, parent)
		b = self.findParent(second, parent)
		if a == b:
			return
		parent[a] = b

	def avoidExlosion(self, mix, n, danger, m):
		parent = [0] * 1001
		ans = []
		for i in range(0, n):
			parent[i] = i
		for i in range(0, n):
			first = self.findParent(mix[i][0], parent)
			second = self.findParent(mix[i][1], parent)
			safe = True
			for j in range(0, m):
				firstD = self.findParent(danger[j][0], parent)
				secondD = self.findParent(danger[j][1], parent)
				if first == firstD and second == secondD or (first == secondD and second == firstD):
					safe = False
			if safe:
				ans.append('Yes')
				self.mergeParent(mix[i][0], mix[i][1], parent)
			else:
				ans.append('No')
		return ans


class Solution:

	def avoidExlosion(self, mix, n, danger, m):
		ds = list(range(n))

		def find(a):
			if ds[a] != a:
				ds[a] = find(ds[a])
			return ds[a]
		result = []
		for (x, y) in mix:
			(x, y) = (find(x - 1), find(y - 1))
			for (p, q) in danger:
				(p, q) = (find(p - 1), find(q - 1))
				if (x, y) == (p, q) or (x, y) == (q, p):
					result.append('No')
					break
			else:
				result.append('Yes')
				ds[x] = y
		return result


class Solution:

	def avoidExlosion(self, mix, n, danger, m):
		a = [i for i in range(n + 1)]

		def find(x):
			while x != a[x]:
				x = a[x]
			return x

		def merge(x, y):
			x = find(x)
			y = find(y)
			px = a[x]
			a[x] = y

			def unmerge():
				a[x] = px
			return unmerge
		ans = ['Yes'] * n
		for (i, (m1, m2)) in enumerate(mix):
			unmerge = merge(m1, m2)
			for (d1, d2) in danger:
				if find(d1) == find(d2):
					ans[i] = 'No'
					unmerge()
		return ans


class Solution:

	def avoidExlosion(self, mix, n, danger, m):
		parent = [i for i in range(n + 1)]
		ans = []
		for ele in mix:
			(u, v) = (ele[0], ele[1])
			flag = True
			while parent[u] != u:
				u = parent[u]
			while parent[v] != v:
				v = parent[v]
			for d in danger:
				(d1, d2) = (d[0], d[1])
				while parent[d1] != d1:
					d1 = parent[d1]
				while parent[d2] != d2:
					d2 = parent[d2]
				if (u, v) == (d1, d2) or (u, v) == (d2, d1):
					ans.append('No')
					flag = False
					break
			if flag:
				ans.append('Yes')
				parent[u] = v
		return ans


class Solution:

	def avoidExlosion(self, mix, n, danger, m):
		ans = []
		parent = [i for i in range(n + 1)]

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

		def combine(a, b):
			pa = findparent(a)
			pb = findparent(b)
			if pa == pb:
				return
			parent[pa] = pb
			return
		for i in range(n):
			first = findparent(mix[i][0])
			second = findparent(mix[i][1])
			flag = True
			for j in range(m):
				one = findparent(danger[j][0])
				two = findparent(danger[j][1])
				if first == one and second == two or (first == two and second == one):
					flag = False
			if flag:
				ans.append('Yes')
				combine(mix[i][0], mix[i][1])
			else:
				ans.append('No')
		return ans


class disjointSet:
	parent = []

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

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

class Solution:

	def avoidExlosion(self, mix, n, danger, m):
		parent = list(range(n + 1))
		ds = disjointSet(n + 1)

		def union(s1, s2):
			if s1 > s2:
				parent[s1] = s2
			else:
				parent[s2] = s1

		def findUltimateParent(node):
			if parent[node] != node:
				parent[node] = findUltimateParent(parent[node])
			return parent[node]
		mixes = []
		for sol in range(n):
			(sol1, sol2) = mix[sol]
			s1 = findUltimateParent(sol1)
			s2 = findUltimateParent(sol2)
			for dsol in range(m):
				d1 = findUltimateParent(danger[dsol][0])
				d2 = findUltimateParent(danger[dsol][1])
				if (d1, d2) == (s1, s2) or (s1, s2) == (d2, d1):
					mixes.append('No')
					break
			else:
				mixes.append('Yes')
				union(s1, s2)
		return mixes


class disjointSet:
	parent = []

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

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

	def unionByRank(self, u, v):
		ultU = self.findUltimateParent(u)
		ultV = self.findUltimateParent(v)
		if ultU == ultV:
			return
		else:
			disjointSet.parent[ultU] = ultV

class Solution:

	def avoidExlosion(self, mix, n, danger, m):
		parent = list(range(n + 1))

		def findUltimateParent(node):
			if parent[node] != node:
				parent[node] = findUltimateParent(parent[node])
			return parent[node]
		mixes = []
		for sol in range(n):
			(sol1, sol2) = mix[sol]
			s1 = findUltimateParent(sol1)
			s2 = findUltimateParent(sol2)
			if s1 == s2:
				mixes.append('Yes')
				continue
			for dsol in range(m):
				d1 = findUltimateParent(danger[dsol][0])
				d2 = findUltimateParent(danger[dsol][1])
				if (d1, d2) == (s1, s2) or (s1, s2) == (d2, d1):
					mixes.append('No')
					break
			else:
				mixes.append('Yes')
				parent[s1] = s2
		return mixes


class Solution:

	def avoidExlosion(self, mix, n, danger, m):
		cx = [i for i in range(n + 1)]
		hx = [1 for i in range(n + 1)]
		solve = []
		mergeLast = []

		def setof(i):
			if i == cx[i]:
				return i
			return setof(cx[i])

		def merge(a, b):
			(a, b) = (setof(a), setof(b))
			if a == b:
				return
			if hx[b] > hx[a]:
				(a, b) = (b, a)
			mergeLast.append((a, b, cx[b]))
			hx[a] += hx[b]
			cx[b] = a
		for x in mix:
			(a, b) = x
			merge(a, b)
			foundE = False
			for d in danger:
				(ae, be) = d
				if setof(ae) == setof(be):
					foundE = True
					break
			solve.append('Yes' if not foundE else 'No')
			if foundE and len(mergeLast):
				(a, b, c) = mergeLast[0]
				hx[a] -= hx[b]
				cx[b] = c
			mergeLast = []
		return solve


from collections import defaultdict

class Solution:

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

	def avoidExlosion(self, mix, n, danger, m):
		dp = list(range(n + 1))
		ans = []
		for (a, b) in mix:
			(x, y) = (self.find(a, dp), self.find(b, dp))
			flag = True
			for (c, d) in danger:
				(i, j) = (self.find(c, dp), self.find(d, dp))
				if i == x and j == y or (i == y and j == x):
					ans.append('No')
					flag = False
					break
			if flag:
				dp[x] = y
				ans.append('Yes')
		return ans


class Solution:

	def avoidExlosion(self, mix, n, danger, m):
		ds = list(range(n))
		res = []
		for i in range(n):
			(x, y) = (mix[i][0] - 1, mix[i][1] - 1)
			(fx, fy) = (self.find(x, ds), self.find(y, ds))
			is_safe = True
			for j in range(m):
				(p, q) = (danger[j][0] - 1, danger[j][1] - 1)
				(fp, fq) = (self.find(p, ds), self.find(q, ds))
				if fx == fp and fy == fq or (fx == fq and fy == fp):
					is_safe = False
					break
			res.append('Yes' if is_safe else 'No')
			if is_safe:
				ds[fx] = fy
		return res

	def find(self, x, ds):
		if ds[x] != x:
			ds[x] = self.find(ds[x], ds)
		return ds[x]


class DisjointSet:

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

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

	def union(self, x, y):
		ul_x = self.find(x)
		ul_y = self.find(y)
		if ul_x == ul_y:
			return 1
		if self.size[ul_x] >= self.size[ul_y]:
			self.size[ul_x] += self.size[ul_y]
			self.parent[ul_y] = ul_x
		else:
			self.size[ul_y] += self.size[ul_x]
			self.parent[ul_x] = ul_y
		return 0

class Solution:

	def avoidExlosion(self, mix, n, danger, m):
		res = []
		dsu = DisjointSet(n)
		for (u, v) in mix:
			(ul_u, ul_v) = (dsu.find(u), dsu.find(v))
			flag = 1
			for (p, q) in danger:
				(ul_p, ul_q) = (dsu.find(p), dsu.find(q))
				if ul_u == ul_p and ul_v == ul_q or (ul_u == ul_q and ul_v == ul_p):
					res.append('No')
					flag = 0
					break
			if flag:
				res.append('Yes')
				dsu.union(u, v)
		return res