city-and-soldiers

Today, King Trophies is on another rampage to destroy the small village controlled by Alex. Please help his soldiers.

At first, there are N individual soldiers, who haven't yet joined together; each of these soldiers is the leader of his/her own group. You have to handle 3 types of operations:

1) Two groups find each other, and the leader of the first group steps down.

2) A becomes leader of his group

3) Output the leader of a certain group

Input:

The first line contains the number N, the number of soldiers, and Q, the number of operations. 

The next Q lines contains operations in the following format:

1 a b: Groups containing person a and person b find each other, and the leader of the group containing person a steps down, i.e., leader of group containing b becomes the leader of the merged group. If a is in b's group or vice versa ignore the operation.

2 a: a becomes the leader of his group.

3 a: Output the leader of the group containing person a.

Output:

Output the answer for each query of type 3. 

Constraints:

1 ≤ N ≤ 10^5

1 ≤ Q ≤ 10^5

SAMPLE INPUT
2 2
1 1 2
3 1

SAMPLE OUTPUT
2

Explanation

Here, 2 will take over after 1 steps down.

Difficulty: MEDIUM
Tags: Spanning trees

Starter code:

Solutions:
def root(i):
	global x
	start = i
	while i != x[i]:
		x[i] = x[x[i]]
		i = x[i]
	while start != x[start]:
		temp = start
		start = x[start]
		x[temp] = i
	return i
(n, m) = list(map(int, input().strip().split()))
count = n
x = list(range(n + 1))
size = [1] * ( n + 1)

for i in range(m):
	s = input().strip().split()
	if len(s) == 3:
		(c, a, b) = list(map(int, s))
		rA = root(a)
		rB = root(b)
		if rA != rB:
			count -= 1
			x[rA] = rB
	else:
		(c, a) = list(map(int, s))
		rA = root(a)
		if c == 2:
			x[rA] = a
			x[a] = a
		else:
			print(rA)
			
			
				
	#print(x)
	#print(size)
	


from collections import defaultdict
class UnionFind:

	def __init__(self):
		self.parents = defaultdict(int)
		self.size    = defaultdict(int)
		
	  

	def make_set(self,node_list):
		for node in node_list:
			self.parents[node] = node
			self.size[node]    = 1

			
	def Union(self,node1,node2):
		node1_root = self.Find(node1)
		node2_root = self.Find(node2)

		if node1_root == node2_root:
			 return
			
		self.parents[node1_root] = node2_root
		self.size[node2_root]    += self.size[node1_root]
		
	
			
			
	def Find(self,node):
		if self.parents[node] != node:
			self.parents[node] = self.Find(self.parents[node])    
		return self.parents[node]

	def make_leader(self,node):
		root = self.Find(node)
		self.parents[root] = node
		self.parents[node] = node

	
		
			
if __name__ == "__main__":
	N ,Q = [int(x) for x in input().split()]
	L=list(range(1,N+1))
	uf=UnionFind()
	uf.make_set(L)
	for i in range(Q):
		Q = [int(x) for x in input().split()]
		if Q[0]   == 1:
			uf.Union(Q[1],Q[2])

		elif Q[0] == 2:
			uf.make_leader(Q[1])     

		elif Q[0] == 3:
			print(uf.Find(Q[1]))
		
	
	
	#print X.size
		

	



def union(parents, i, j):
	''' Union with under the deepest root '''
	parents[i] = j

def find(parents, el):
	''' Find an element and compress the sets '''
	if parents[el] == el: return el
	leader = find(parents, parents[el])
	parents[el] = leader
	return leader

def solve(n, xss):
	res = []
	parents = list(range(0, n))
	for xs in xss:
		if xs[0] == 1:
			root_a = find(parents, xs[1] - 1)
			root_b = find(parents, xs[2] - 1)
			if root_a == root_b: continue
			union(parents, root_a, root_b)
		elif xs[0] == 2:
			el = xs[1] - 1
			root_a = find(parents, el)
			parents[root_a] = el
			parents[el] = el
		else:
			res.append(str(find(parents, xs[1] - 1) + 1))
	return '\n'.join(res)

if __name__ == '__main__':
	n, q = list(map(int, input().split()))
	xss = [list(map(int, input().split())) for _ in range(q)]
	print(solve(n, xss))


def root(arr,x):
	i=arr[x]
	while i!=arr[i]:
		i=arr[i]
	return i



listmp=list(input().split())
n=int(listmp[0])
q=int(listmp[1])

arr=[]
for i in range(0,n):
	arr.append(i)

for i in range(0,q):
	listmp=list(input().split())
	ch=int(listmp[0])
	if ch==3:
		print(1+root(arr,int(listmp[1])-1))
	
	elif ch==2:
		a=int(listmp[1])-1
		arr[root(arr,a)]=a
		arr[a]=a
	
	else:
		a=int(listmp[1])-1
		b=int(listmp[2])-1
		arr[root(arr,a)]=root(arr,b)


#!/usr/bin/env python
# encoding: utf-8

fa, leader = [], []

def findfa(x):
	if x == fa[x]:
		return x
	else:
		fa[x] = findfa(fa[x])
		return fa[x]

if __name__ == '__main__':
	N, Q = list(map(int, input().split()))
	fa = [i for i in range(N + 1)]
	leader = [i for i in range(N + 1)]
	for _ in range(Q):
		op = input().split()
		if op[0] == '1':
			a, b = int(op[1]), int(op[2])
			x, y = findfa(a), findfa(b)
			if x != y:
				fa[x] = y
		else:
			a = int(op[1])
			if op[0] == '2':
				leader[findfa(a)] = a
			else:
				print(leader[findfa(a)])