city-and-flood-1

Fatland is a town that started with N distinct empires, namely empires 1, 2, ..., N. But over time, the armies of some of these empires have taken over other ones. Each takeover occurred when the army of empire i invaded empire j. After each invasion, all of empire j became part of empire i, and empire j was renamed as empire i. 

Empire Huang, leader of Badland, wants to invade Fatland. To do this, he needs to calculate how many distinct empires still remain in Fatland after all the takeovers. Help him with this task.

Input:

The first line contains an integer N, the number of empires that were originally in Fatland.

The second line contains an integer K, denoting the number of takeovers that took place.

Each of the next K lines contains 2 space-separated integers i, j, representing that the army of empire i took over that of empire j. As a result, empire j does not exist anymore and is now renamed as empire i. It is guaranteed that empire i still exists.

Output: Output one integer, the number of empires that exist in Fatland.

Constraints:

1 ≤ N ≤ 10^5

1 ≤ K ≤ 10^5

SAMPLE INPUT
4
2
1 2
4 1

SAMPLE OUTPUT
2

Explanation

Fatland started with empires 1, 2, 3, 4. First, empire 1 invaded empire 2, so empire 2 was renamed to empire 1. Then, empire 4 invaded empire 1. So what were at the beginning empires 1 and 2 were renamed to empire 4. Now, only empires 3 and 4 remain, so the answer is 2.

Difficulty: EASY
Tags: Spanning trees

Starter code:

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

fa = []

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

if __name__ == '__main__':
	a = list(map(int, input().split()))
	N, K = 0, 0
	if len(a) == 1:
		N = a[0]
		K = int(input())
	else:
		N, K = a[0], a[1]
	fa = [i for i in range(N + 1)]
	for _ in range(K):
		i, j = list(map(int, input().split()))
		fi, fj = findfa(i), findfa(j)
		if fi != fj:
			fa[fj] = fi

	ans = 0
	for i in range(1, N + 1):
		if i == findfa(i):
			ans += 1
	print(ans)


inp=list(map(int, input().strip().split(" ")))	
if(len(inp)==2):
	emp=inp[0]
	tc=inp[1]
else:
	emp=inp[0]
	tc=int(input().strip())
cnt=0
while(tc>0):
	tc-=1
	val=list(map(int, input().strip().split(" ")))
	cnt+=1
print(emp-cnt)


parent=[]

def union(a,b):
	if not isSameset(a,b):
                parent[b-1]=parent[a-1]

def isSameset(a,b):
	if parent[a-1]==parent[b-1]:
		return True
	else:
		return False

def findSet(a):
	if parent[a-1]==a:
		return a
	else:
		return findSet(parent[a-1])

n=str(input())
if ' ' not in n:
	k=int(input())
else:
	n,k=n.split(' ')
n=int(n)
k=int(k)

for i in range(1,n+1):
	parent.append(i)

ct=n
for i in range(k):
	i,j=list(map(int,input().split()))
	if i!=j and parent[j-1]==j:
		ct-=1
		
	union(i,j)
'''
empires=[]

for kingdom in parent:
	temp=findSet(kingdom)
	#print "kingdom:",kingdom," Empire:",temp
	if temp not in empires:
		empires.append(temp)
		ct+=1
'''
print(ct)
	






def union(parents, depths, i, j):
	''' Union with under the deepest root '''
	if depths[i] > depths[j]:
		parents[j] = i
	else:
		parents[i] = j
		depths[i] = max(depths[i], depths[j] + 1)

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):
	depths = [1] * n
	parents = list(range(0, n))
	for i, j in xss:
		union(parents, depths, find(parents, i - 1), find(parents, j - 1))
	for i in range(n):
		find(parents, i)
	return len(set(parents))

if __name__ == '__main__':
	''' The input files on codemonk are hill formatted wtf ... '''
	malformed_input = input()
	if ' ' in malformed_input:
		n, k = list(map(int, malformed_input.split()))
	else:
		n = int(malformed_input)
		k = int(input())
	xss = [list(map(int, input().split())) for _ in range(k)] 
	print(solve(n, xss))