city-and-campers

"Money money MONEY, I want money" thought Alex. "Now how do I get money? Well... I'll open up a camp!"

Well, unfortunately things didn't go so well for Alex's campers, and now there are N campers wandering around the city aimlessly. You have to handle Q queries; which consist of two groups finding each other and becoming one larger group. After each query, output the difference between the group of largest size and group of smallest size. If there is only one group, output 0. At first, everyone is in their own group.

Also note, if the two campers in the query are already in the same group, print the current answer, and skip merging the groups together.

Input:

The first line consists of two space separated integers, N and Q

The next Q line consists of two integers, A and B, meaning that the groups involving camper A and camper B find each other.

Output:

Output Q lines, the answer after each query. 

Constraints:

1 ≤ N ≤ 10^5

1 ≤ Q ≤ 10^5

SAMPLE INPUT
2 1
1 2

SAMPLE OUTPUT
0

Explanation

Here, the two campers find each other, so the answer is 0.

Source: hackerearth | Difficulty: EASY
Tags: Spanning trees


Solutions:
from sys import stdin
from heapq import heappop, heappush, heapify
from collections import defaultdict

class unionfind(object):
	def __init__(self, n):
		self._number_of_nodes, self._count = n, n
		self.roots, self.weights = list(range(n)), [1]*n

	def union(self, a, b):
		self[a] = b

	def find(self, key):
		return self[key]

	def is_connected(self, a, b):
		return self[a, b]

	def __len__(self):
		return self._count

	def __setitem__(self, a, b):
		aroot, broot = self[a], self[b]
		if aroot == broot:
			return
		if self.weights[aroot] > self.weights[broot]:
			aroot, broot = broot, aroot
		self.roots[aroot] = broot
		self.weights[broot] += self.weights[aroot]
		self.weights[aroot] = 0
		self._count -= 1

	def __getitem__(self, key):
		if isinstance(key, tuple):
			tmp = self[key[0]]
			for x in range(1, len(key)):
				if self[key[x]] != tmp:
					return False
			return True
		if isinstance(key, slice):
			return [self[x] for x in range(*key.indices(self._number_of_nodes))]
		roots = self.roots
		while roots[key] != key:
			roots[key] = roots[roots[key]]
			key = roots[key]
		return key


class CustomHeap(object):
	def __init__(self, arr):
		self.minheap = [[x, False] for x in arr]
		self.maxheap = [[-x, False] for x in arr]
		heapify(self.minheap)
		heapify(self.maxheap)
		self.minrefs = defaultdict(list)
		self.maxrefs = defaultdict(list)
		for x in self.minheap:
			self.minrefs[x[0]].append(x)
		for x in self.maxheap:
			self.maxrefs[x[0]].append(x)

	def insert(self, x):
		mir, mar = [x, False], [-x, False]
		heappush(self.minheap, mir)
		heappush(self.maxheap, mar)
		self.minrefs[mir[0]].append(mir)
		self.maxrefs[mar[0]].append(mar)

	def delete(self, x):
		ref = self.minrefs[x].pop()
		ref[1] = True
		ref = self.maxrefs[-x].pop()
		ref[1] = True

	def max(self):
		while self.maxheap[0][1]:
			heappop(self.maxheap)
		return -self.maxheap[0][0]

	def min(self):
		while self.minheap[0][1]:
			heappop(self.minheap)
		return self.minheap[0][0]

def main():
	nextint = iter(map(int, stdin.read().split())).__next__
	n, q = nextint(), nextint()
	uf = unionfind(n)
	myds = CustomHeap(uf.weights)
	for _ in range(q):
		a, b = nextint() - 1, nextint() - 1
		if uf[a] != uf[b]:
			myds.delete(uf.weights[uf[a]])
			myds.delete(uf.weights[uf[b]])
			uf[a] = b
			myds.insert(uf.weights[uf.find(a)])
		print(myds.max() - myds.min())

main()


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))
	group_sizes = [1] * n
	count_group_of_size = [0] * (n + 1)
	count_group_of_size[1] = n
	smaller_index = 1
	maxi = 1
	res = []
	for a, b in xss:
		root_a = find(parents, a - 1)
		root_b = find(parents, b - 1)
		if root_a != root_b:
			union(parents, depths, root_a, root_b)
			count_group_of_size[group_sizes[root_a]] -= 1
			count_group_of_size[group_sizes[root_b]] -= 1
			new_size = group_sizes[root_a] + group_sizes[root_b]
			group_sizes[root_a] = new_size
			group_sizes[root_b] = new_size
			count_group_of_size[new_size] += 1
			maxi = max(maxi, new_size)
			while count_group_of_size[smaller_index] == 0: smaller_index += 1
		res.append(str(maxi - smaller_index))
	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 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))
	group_sizes = [1] * n
	count_group_of_size = [0] * (n + 1)
	count_group_of_size[1] = n
	smaller_index = 1
	maxi = 1
	res = []
	for a, b in xss:
		root_a = find(parents, a - 1)
		root_b = find(parents, b - 1)
		if root_a != root_b:
			union(parents, depths, root_a, root_b)
			count_group_of_size[group_sizes[root_a]] -= 1
			count_group_of_size[group_sizes[root_b]] -= 1
			new_size = group_sizes[root_a] + group_sizes[root_b]
			group_sizes[root_a] = new_size
			group_sizes[root_b] = new_size
			count_group_of_size[new_size] += 1
			maxi = max(maxi, new_size)
			while count_group_of_size[smaller_index] == 0: smaller_index += 1
		res.append(str(maxi - smaller_index))
	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))