Given an array A[] that stores all number from 1 to N (both inclusive and sorted) and K queries.
The task is to do the following operations on array elements :
1. UNION X Z : Perform union of X and Z i.e. parent of Z will become the parent of X.
2. FIND X: Find the parent of X and print it.
Note: Initially all are the parent of themselves.
Input:
N = 5, K = 4
queries[] = {{find 4},
             {find 1},
             {unionSet 3 1},
             {find 3}}
Output:
4 1 1
Explanation:
1. The parent of 4 is 4. Hence the output is 4.
2. The parent of 1 is 1. Hence the output is 1.
3. After performing unionSet 3 1, parent of 3 becomes 1,
   since, parent of 1 is currently 1 itself.
4. The parent of 3 is now 1. Hence, the output is 1.
Your Task:  
You don't need to read input or print anything. Your task is to complete the functions- find() which takes an array A[] and an integer X as an input parameter and return the parent of X and the function unionSet() which takes an array A[] and two integers X and Z and performs the union of X and Z.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N, K <= 100

Source: geeksforgeeks | Difficulty: EASY
Tags: Spanning trees

Starter code: # function should return parent of x
def find(A, X):
    # Code here

# function shouldn't return or print anything
def unionSet(A, X, Z):
    # Code here


Solutions:
def find(A, X):
	if A[X - 1] == X:
		return X
	A[X - 1] = find(A, A[X - 1])
	return A[X - 1]

def unionSet(A, X, Z):
	parentX = find(A, X)
	parentZ = find(A, Z)
	if parentX != parentZ:
		A[parentX - 1] = parentZ


def find(A, X):
	if X == A[X - 1]:
		return X
	else:
		return find(A, A[X - 1])

def unionSet(A, X, Z):
	A[find(A, X) - 1] = A[find(A, Z) - 1]


def find(parent, root):
	if parent[root - 1] != root:
		parent[root - 1] = find(parent, parent[root - 1])
	return parent[root - 1]

def unionSet(parent, u, v):
	u = find(parent, u)
	v = find(parent, v)
	if u == v:
		return
	else:
		parent[u - 1] = v


def find(parent, root):
	if parent[root - 1] != root:
		parent[root - 1] = find(parent, parent[root - 1])
	return parent[root - 1]

def unionSet(parent, u, v):
	Up_u = find(parent, u)
	Up_v = find(parent, v)
	if Up_u == Up_v:
		return
	else:
		parent[Up_u - 1] = Up_v


def find(A, X):
	if A[0] != 0:
		A.insert(0, 0)
	par_a = X
	while par_a != A[par_a]:
		par_a = A[par_a]
	return par_a

def unionSet(A, X, Z):
	if A[0] != 0:
		A.insert(0, 0)
	par_a = X
	par_z = Z
	while par_a != A[par_a]:
		par_a = A[par_a]
	while par_z != A[par_z]:
		par_z = A[par_z]
	A[par_a] = par_z


def find(A, X):
	if A[X - 1] == X:
		return X
	r = find(A, A[X - 1])
	A[X - 1] = r
	return r

def unionSet(A, X, Z):
	px = find(A, X)
	pz = find(A, Z)
	A[px - 1] = A[pz - 1]


def find(A, X):
	if A[X - 1] != X:
		A[X - 1] = find(A, A[X - 1])
		return A[X - 1]
	return A[X - 1]

def unionSet(A, X, Z):
	(p_x, p_z) = (find(A, X), find(A, Z))
	A[p_x - 1] = p_z


def find(A, X):
	if A[X - 1] != X:
		A[X - 1] = find(A, A[X - 1])
	return A[X - 1]

def unionSet(A, X, Z):
	x = find(A, X)
	y = find(A, Z)
	A[x - 1] = y


def find(arr, x):
	if arr[arr[x - 1] - 1] == arr[x - 1]:
		return arr[x - 1]
	else:
		return find(arr, arr[x - 1])

def unionSet(arr, x, z):
	arr[find(arr, x) - 1] = find(arr, z)


def find(A, X):
	if A[X - 1] == X:
		return X
	A[X - 1] = find(A, A[X - 1])
	return A[X - 1]

def unionSet(A, X, Z):
	topPar_X = find(A, X)
	topPar_Z = find(A, Z)
	if topPar_X == topPar_Z:
		return topPar_X
	else:
		A[topPar_X - 1] = topPar_Z


def find(P, X):
	if P[X - 1] == X:
		return X
	P[X - 1] = find(P, P[X - 1])
	return P[X - 1]

def unionSet(P, X, Z):
	up_X = find(P, X)
	up_Z = find(P, Z)
	P[up_X - 1] = up_Z