1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class UF:
	def __init__(self, N):
		self.N = N
		self._id = [i for i in range(N)]

	def find(self, p):
		while p != self._id[p]:
			p = self._id[p]
		return p

	def union(self, p, q):
		p = self.find(p)
		q = self.find(q)
		if p==q:
			return
		self._id[p] = q