Submission #7469261

---

Source Code Expand

import sys
def input():
	return sys.stdin.readline().strip()

N, Q = list(map(int, input().split()))


class Union_Find():
	def __init__(self, n):
		self.union = [i for i in range(n)]
		self.level = [0 for i in range(n)]

	def root(self, i, mode=0):
		keiro = [i]
		ans = i
		while ans != self.union[ans]:
			ans = self.union[ans]
			keiro.append(ans)
		if mode == 0:
			return ans
		else:
			return ans, keiro

	def unite(self, i, j):
		root_i, list_i = self.root(i, 1)
		root_j, list_j = self.root(j, 1)
		if root_i != root_j:
			if self.level[root_i] < self.level[root_j]:
				self.level[root_j] = max(self.level[root_i] + 1, self.level[root_j])
				for node in list_i:
					self.union[node] = root_j
			else:
				self.level[root_i] = max(self.level[root_j] + 1, self.level[root_i])
				for node in list_j:
					self.union[node] = root_i

UF = Union_Find(N)

for q in range(Q):
	P, A, B = list(map(int, input().split()))
	if P == 0:
		UF.unite(A, B)

	else:
		if UF.root(A) == UF.root(B):
			print("Yes")
		else:
			print("No")

Submission Info

Judge Result