Problem:
 Score : 500 points    Problem Statement There are N cards placed face down in a row. On each card, an integer 1 or 2 is written.  Let A_i be the integer written on the i -th card.  Your objective is to guess A_1, A_2, ..., A_N correctly.  You know the following facts:   For each i = 1, 2, ..., M , the value A_{X_i} + A_{Y_i} + Z_i is an even number.   You are a magician and can use the following magic any number of times:  Magic : Choose one card and know the integer A_i written on it. The cost of using this magic is 1 .  What is the minimum cost required to determine all of A_1, A_2, ..., A_N ?  It is guaranteed that there is no contradiction in given input.      Constraints  All values in input are integers.  2 \leq N \leq 10^5  1 \leq M \leq 10^5  1 \leq X_i < Y_i \leq N  1 \leq Z_i \leq 100  The pairs (X_i, Y_i) are distinct.  There is no contradiction in input. (That is, there exist integers A_1, A_2, ..., A_N that satisfy the conditions.)         Input Input is given from Standard Input in the following format:  N  M  X_1  Y_1  Z_1  X_2  Y_2  Z_2  \vdots  X_M  Y_M  Z_M       Output Print the minimum total cost required to determine all of A_1, A_2, ..., A_N .        Sample Input 1 3 1
1 2 1      Sample Output 1 2  You can determine all of A_1, A_2, A_3 by using the magic for the first and third cards.       Sample Input 2 6 5
1 2 1
2 3 2
1 3 3
4 5 4
5 6 5      Sample Output 2 2       Sample Input 3 100000 1
1 100000 100      Sample Output 3 99999

Solution (Python):
import sys, math, collections, heapq, itertools
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0: a, b = b, a % b
    return b
 
def find(a, L):
    if L[a] == a: return a
    else: 
        L[a] = find(L[a], L)
        return L[a]
 
def unite(a, b, L, R):
    a = find(a, L)
    b = find(b, L)
    if a == b: return
    if R[a] < R[b]:
        L[a] = b
    else:
        L[b] = a
        if R[a] == R[b]: R[a] += 1
    
  
def solve():
    N, M = map(int, line_input())
    parent = [int(i) for i in range(N)]
    edge = [[] for i in range(N)]
    rank = [0] * N
    for i in range(M):
        x, y, z = map(int, line_input())
        unite(x-1, y-1, parent, rank)
    for i in range(N):
        parent[i] = find(i, parent)
    print(len(set(parent)))
    return 0
  
if __name__ == "__main__":
    solve()

Solution (Python):
from collections import defaultdict


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


class Solution:
    def main(self):
        N, M = map(int, input().split())
        ufind = UnionFind(N)
        for _ in range(M):
            X, Y, Z = map(int, input().split())
            ufind.union(X-1, Y-1)
        print(len(set([ufind.find(i) for i in range(N)])))


if __name__ == '__main__':
    Solution().main()

Solution (Python):
class Element:
	val = 0
	parent = None
	height = 0
	size = 1
	def __init__(self, val, parent=None, height=0, size=1):
		self.val = val
		if parent is None:
			self.parent = self
		else:
			self.parent = parent
		self.height = height
		self.size = size

class UnionFindTree:
	elemnts = []

	def __init__(self, n):
		self.elemnts = [Element(val=i) for i in range(n)]

	def root(self, x:int) -> Element:
		if self.elemnts[x].parent is self.elemnts[x]:
			return self.elemnts[x]
		return self.root(self.elemnts[x].parent.val)

	def same(self, x:int, y:int) -> bool:
		rx = self.root(x)
		ry = self.root(y)
		return rx is ry

	def unite(self, x:int, y:int):
		rx = self.root(x)
		ry = self.root(y)
		if rx == ry:
			return
		if rx.height < ry.height:
			rx.parent = ry
			ry.size += ry.height
		else:
			ry.parent = rx
			rx.size += ry.size
			if rx.height == ry.height:
				rx.height += 1

def main():
	N, M = map(int, input().split())
	uionfind = UnionFindTree(N)
	for i in range(M):
		u, v, z = map(int, input().split())
		uionfind.unite(u-1, v-1)
	ans_set = set()

	ans = 0
	for i in range(N):
		this_root = uionfind.root(i).val
		if not this_root in ans_set:
			ans += 1
			ans_set.add(this_root)
	print(ans)


if __name__ == '__main__':
	main()

Solution (Python):
N, M = list(map(int, input().split()))


class UnionFind():
    def __init__(self, n):
        self.rank = [1 for _ in range(n)]
        self.parent = [i for i in range(n)]

    def union(self, i, j):
        i = self.root(i)
        j = self.root(j)
        if i == j:
            return
        if self.rank[i] < self.rank[j]:
            self.parent[i] = j
        else:
            if self.rank[i] == self.rank[j]:
                self.rank[j] += 1
            self.parent[j] = i

    def same(self, i, j):
        return self.root(i) == self.root(j)

    def root(self, i):
        if self.parent[i] != i:
            self.parent[i] = self.root(self.parent[i])
        return self.parent[i]


uf = UnionFind(N)

for _ in range(M):
    X, Y, _ = list(map(int, input().split()))
    uf.union(X-1, Y-1)

ans = 0

for i in range(N):
    if uf.parent[i] == i:
        ans += 1

print(ans)

Solution (Python):
N, M = map(int, input().split())
class UnionFind():
    
    
    def __init__(self, n):
        self.n = n
        
        
        self.root = [-1]*(n+1)
        
        self.rnk = [0]*(n+1)

    
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    
    def Unite(self, x, y):
        
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        
        if(x == y):
            return 
        
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)] 
        
uf = UnionFind(N)
for m in range(M):
    a,b,c = map(int, input().split())
    uf.Unite(a-1, b-1)
ls = []
for n in range(N):
    ls.append(uf.Find_Root(n))
print (len(set(ls)))

Solution (Python):
n,m=map(int,input().split())
w=[i for i in range(n+1)]
s=[1]*(n+1)
def root(x):
    if w[x]==x:
        return x
    x=w[x]
    return root(w[x])
def unite(x,y):
    x=root(x)
    y=root(y)
    if x!=y:
        if s[x]<s[y]:
            w[x]=y
            s[y]+=1
        else:
            w[y]=x
            s[x]+=1
for i in range(m):
    x,y=list(map(int,input().split()))[:2]
    unite(x,y)
go=set()
for i in range(1,n+1):
    go.add(root(i))
print(len(go))

Solution (Python):
import sys
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
import collections
import itertools
import operator

class UnionFind:
  def __init__(self, elems=None):
    class KeyDict(dict):
      def __missing__(self, key):
        self[key] = key
        return key

    self.parent = KeyDict()
    self.rank = collections.defaultdict(int)
    self.size_ = collections.defaultdict(lambda: 1)

    if elems is not None:
      for elem in elems:
        _, _, _ = self.parent[elem], self.rank[elem], self.size_[elem]

  def find(self, x):
    if self.parent[x] == x:
      return x
    else:
      self.parent[x] = self.find(self.parent[x])
      return self.parent[x]

  def unite(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x == y:
      return
    if self.rank[x] < self.rank[y]:
      self.parent[x] = y
      self.size_[y] += self.size_[x]
    else:
      self.parent[y] = x
      self.size_[x] += self.size_[y]
    if self.rank[x] == self.rank[y]:
      self.rank[x] += 1

  def are_same(self, x, y):
    return self.find(x) == self.find(y)

  def grouper(self):
    roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
    root = operator.itemgetter(1)
    for _, group in itertools.groupby(sorted(roots, key=root), root):
      yield [x for x, _ in group]

  def size(self,x):
    return self.size_[self.find(x)]

g = UnionFind()
n,m = na()

for i in range(m):
    x,y,z = na()
    g.unite(x,y)

f = list(g.grouper())

a = 0
b = 0
for i in f:
    a+=len(i)
    b+=1

print(b+n-a)

Solution (Python):
from collections import defaultdict

N,M = map(int,input().split())

D = defaultdict(list) 
S = [0 for i in range(N)] 
for i in range(M):
    x,y,z = map(int,input().split())
    D[x].append(y)
    D[y].append(x)
    
ans = 0
for i in range(N):
    if S[i]>0:continue
    T = [i+1]
    S[i] = 1
    ans += 1
    while T:
        n = T.pop()
        for d in D[n]:
            if S[d-1]>0:continue
            else: S[d-1] = 1
            T.append(d)
        
print(ans)

Solution (Python):
class uf_tree:
    def __init__(self, n):
        self._size = n
        self.sizes = [1] * n
        self.par = list(range(n))
 
    def find(self, x):
        if x == self.par[x]:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]
 
    def unite(self, x, y):
        self._size -= 1
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.sizes[x] < self.sizes[y]:
            x, y = y, x
        self.par[y] = x
        self.sizes[x] += self.sizes[y]
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def size(self, x):
        return self.sizes[self.find(x)]


n, m = map(int, input().split())
uf = uf_tree(n+1)

for _ in range(m):
    x, y, z = map(int, input().split())
    if uf.same(x, y):
        continue
    uf.unite(x, y)
    

ans = uf._size - 1
print(ans)

Solution (Python):


import math



class UnionFind():
  def __init__(self, size):
    self.par = [-1]*size
      
  def root(self,x):
    if self.par[x] < 0:
      return x
    else:
      return self.root(self.par[x])
      
  def issame(self,x,y):
    if self.root(x)==self.root(y):
      return True
    else:
      return False
  
  def merge(self,x,y):
    x, y = [self.root(x), self.root(y)]
    if x == y:
      return False
    if self.par[x] > self.par[y]:
      x, y = y, x
    self.par[x] += self.par[y]
    self.par[y] = x
    return True

  def get_list(self):
    return self.par


def main():
  N,M = map(int, input().split())
  uf = UnionFind(N)
  for _ in range(M):
    x,y,z = map(int, input().split())
    uf.merge(x-1,y-1)

  ret = 0
  for p in list(uf.get_list()):
    if p < 0:
      ret += 1
  return ret


if __name__ == "__main__":
  print(main())

Solution (Python):
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
    def find(self, x):
        if self.par[x] == x:
          return x
        else:
          self.par[x] = self.find(self.par[x])
          return self.find(self.par[x])
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    def tree_num(self):
        return len([i for i in range(n) if self.par[i] == i])

n, m = map(int, input().split())
uf = UnionFind(n)

for i in range(m):
  x, y, z = map(int, input().split())
  uf.union(x-1, y-1)
print(uf.tree_num())

Solution (Python):
class UnionFind():
    
    
    def __init__(self, n):
        self.n = n
        
        
        self.root = [-1]*(n+1)
        
        self.rnk = [0]*(n+1)

    
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    
    def Unite(self, x, y):
        
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        
        if(x == y):
            return 
        
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
        
n,m=map(int,input().split())
t=UnionFind(n)
for i in range(m):
    x,y,z=map(int,input().split())
    t.Unite(x,y)
s=set()
for i in range(1,n+1):
    s.add(t.Find_Root(i))
print(len(s))

Solution (Python):
from collections import defaultdict

def dfs(u):
    st = [u]
    while st:
        u = st.pop()
        if cv[u]: continue
        cv[u] = 1
        for nxt in adj[u]:
            st.append(nxt)

n, m = [int(item) for item in input().split()]
data = []
ans = [-1] * n
adj = defaultdict(set)
for _ in range(m):
    x, y, z = [int(item) for item in input().split()]
    x -= 1
    y -= 1
    adj[x].add(y)
    adj[y].add(x)


cost = 0
cv = [0] * n
for i in range(n):
    if not cv[i]:
        cost += 1
        dfs(i)

print(cost)

Solution (Python):
import sys
input = sys.stdin.readline

class UnionFindNode(object):
    """
    Union-Find構造
    ノードのグループ併合や、所属グループ判定を高速に処理する
    """

    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.rank_ = 1

    def __str__(self):
        template = "UnionFindNode(group_id: {}, \n\tparent: {}, value: {}, size: {})"
        return template.format(self.group_id_, self.parent_, self.value, self.rank_)

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        root = self.root()
        return root.group_id_

    def rank(self):
        root = self.root()
        return root.rank_

    def unite(self, unite_node):
        root = self.root()
        unite_root = unite_node.root()

        if root.group_id_ != unite_root.group_id_:
            if root.rank() > unite_root.rank():
                unite_root.parent_ = root
                root.rank_ = max(root.rank_, unite_root.rank_ + 1)
            else:
                root.parent_ = unite_root
                unite_root.rank_ = max(root.rank_ + 1, unite_root.rank_)


if __name__ == "__main__":
    N,M = map(int,input().split())
    ans = N
    node_list = [UnionFindNode(i) for i in range(N)]
    for i in range(M):
        X,Y,Z = map(int,input().split())
        X -= 1
        Y -= 1
        if node_list[X].root() != node_list[Y].root():
            ans -= 1
        node_list[X].unite(node_list[Y])
    print(ans)

Solution (Python):
n,m=map(int,input().split())
xyz=[list(map(int,input().split())) for i in range(m)]
ans=[0 for i in range(n+1)]
h=[[] for i in range(n+1)]
for i in xyz:
  x,y,z=i
  h[x].append(y)
  h[y].append(x)
fa=0
i=1
while(i<=n):
  if(ans[i]==0):
    q=[i]
    ans[i]=1
    fa+=1
    while(len(q)>0):
      t=q.pop()
      for j in h[t]:
        if(ans[j]==0):
          q.append(j)
          ans[j]=1
    i+=1 
  else:
    i+=1
print(fa)

Solution (Python):
n,m = map(int,input().split())
c = list(range(n+1))
k = n
a = []
for i in range(n+1):
  a.append([i])
  

for i in range(m):
    x,y,z = map(int,input().split())
    t = c[x]
    s = c[y]
    if t == s:
        continue
    
    if len(a[s]) > len(a[t]):
        t,s = s,t
    a[t] += a[s]
    for z in a[s]:
        c[z] = t
    a[s] = []
    k -= 1
    
print(k)

Solution (Python):
import sys
input = sys.stdin.readline

class Unionfind:

    __slots__ = ['nodes','size']

    def __init__(self, n):
        self.nodes = list(range(n))
        self.size = [1]*n

    def root(self, x):
        if self.nodes[x] == x:
            return x
        else:
            root_x = self.root(self.nodes[x])
            self.nodes[x] = root_x
            return root_x

    def unite(self, x, y):
        x = self.root(x); y = self.root(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.size[x] += self.size[y]
        self.nodes[y] = x

    def same(self, x, y):
        return self.root(x) == self.root(y)

N,M = map(int,input().split())
info = [list(map(int,input().split())) for _ in range(M)]

uf = Unionfind(N)

for x,y,z in info:
    x -= 1
    y -= 1
    uf.unite(x,y)

for i in range(N):
    uf.root(i)

ans = len(list(set(uf.nodes)))
print(ans)

Solution (Python):
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

def Find(x):    
    global table

    if table[x] == x:
        return x
    else:
        table[x] = Find(table[x])    
        size[x] = size[table[x]]
        return table[x]

def Unite(x,y):    
    global size
    global rank
    x = Find(x)
    y = Find(y)
    sx = Size(x)
    sy = Size(y)

    if x == y:
        return

    if rank[x] > rank[y]:
        table[y] = x
        size[x] = sx + sy
    else:
        table[x] = y
        size[y] = sx + sy
        if rank[x] == rank[y]:
            rank[y] += 1

def Check(x,y):
    if Find(x) == Find(y):
        return True
    else:
        return False

def Size(x):
    return size[Find(x)]

N,M = inpl()

table = [i for i in range(N)]    
rank  = [1 for i in range(N)]    
size  = [1 for i in range(N)]    

for i in range(M):
    x,y,z = inpl()
    x -= 1
    y -= 1
    if not Check(x,y):
        Unite(x,y)

cnt = [0]*N
for x in table:
    cnt[Find(x)] = 1
print(sum(cnt))

Solution (Python):
class Node:
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.rank = 0


class DisjointSet:
    def __init__(self, nodes):
        self.nodes = nodes

    def find_set(self, key):
        pivot = self.nodes[key]
        while pivot.key != pivot.parent.key:
            pivot = pivot.parent
        self.nodes[key].parent = pivot
        return pivot.key

    def same(self, x, y):
        return self.find_set(x) == self.find_set(y)

    def unite(self, x, y):
        y_root = self.find_set(y)
        x_root = self.find_set(x)
        if self.nodes[x].rank > self.nodes[y].rank:
            self.nodes[y_root].parent = self.nodes[x_root]
        elif self.nodes[x].rank < self.nodes[y].rank:
            self.nodes[x_root].parent = self.nodes[y_root]
        else:
            self.nodes[x_root].parent = self.nodes[y_root]
            self.nodes[y_root].rank = self.nodes[y_root].rank + 1


N, M = [int(i) for i in input().split()]
nodes = [Node(i) for i in range(N)]
for node in nodes:
    node.parent = node
ds = DisjointSet(nodes)

for _ in range(M):
    x, y, z = [int(i) for i in input().split()]
    x -= 1
    y -= 1
    if ds.same(x, y):
        pass
    else:
        ds.unite(x, y)
ans = len(set([ds.find_set(i) for i in range(N)]))
print(ans)

Solution (Python):
N, M =map(int,input().split())
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]
uf = UnionFind(N)
cnt = 0
for i in range(M):
  x, y, z = map(int, input().split())
  if not uf.is_same(x-1, y-1):
    cnt += 1
    uf.union(x-1,y-1)
    
print(N-cnt)

Solution (Python):
from collections import defaultdict


class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def unite(self, x, y):
        return self._unite(self.find(x), self.find(y))

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            return x


utf = UnionFindTree()

N, M = map(int, input().split())
for n in range(N):
    utf.make(n + 1)

for m in range(M):
    x, y, z = map(int, input().split())
    utf.unite(x, y)

h = defaultdict(int)
for n in range(N):
    x = utf.find(n + 1)
    h[x] += 1

ans = 0
rest = N
for k, v in h.items():
    ans += 1
    rest -= v
print(ans + rest)

Solution (Python):
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

n,m = map(int,input().split())

class UnionFind():
    def __init__(self, N):
        self.rank = [0] * N
        self.par = [i for i in range(N)]
        self.counter = [1] * N

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            z = self.counter[x] + self.counter[y]
            self.counter[x], self.counter[y] = z, z
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def size(self, x):
        x = self.find(x)
        return self.counter[x]

    def same(self, x, y):
        return self.find(x) == self.find(y)
UF = UnionFind(n)
ans = n
for i in range(m):
    x,y,z = map(int,input().split())
    if  UF.same(x-1,y-1):
        continue
    else:
        UF.unite(x-1,y-1)
        ans -=1
print(ans)

Solution (Python):

import itertools
from collections import Counter
from collections import defaultdict
import bisect



class UnionFind():
    def __init__(self,size):
        self.table = [-1 for _ in range(size)]  

    
    def find(self,x):
        while self.table[x] >= 0:
            
            x = self.table[x]
        return x

    def is_same(self, x, y):
        return self.find(x) == self.find(y)

    def rewrite(self,x, p):
        while self.table[x] >= 0:
            
            tmp = x
            x = self.table[x]
            self.table[tmp] = p
        return

    
    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] != self.table[s2]:
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                    self.rewrite(y, s1)
                else:
                    self.table[s1] = s2
                    self.rewrite(x, s2)
            else:
                
                self.table[s2] = s1
                self.rewrite(y, s1)
        return

    def num_group(self):
        
        return self.table.count(-1)


def main():
    N, M = map(int, input().split())
    uf = UnionFind(N)

    for _ in range(M):
        x, y, z = map(int, input().split())
        uf.union(x - 1, y - 1)
    print(uf.num_group())

if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
N,K=map(int, input().split())

class UnionFindTree:
    def __init__(self, n):
        self.nodes = list(range(n+10))
    def find(self, x):
        if self.nodes[x] == x:
            return x
        parent = self.find(self.nodes[x])
        self.nodes[x] = parent
        return parent
    def unite(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return
        self.nodes[a] = self.nodes[b]
    def is_same(self, a, b):
        return self.find(a) == self.find(b)

uf = UnionFindTree(N)
for i in range(K):
    i,j,k=map(int, input().split())
    uf.unite(i,j)

st = set()
for i in range(1,N+1):
    par = uf.find(i)
    st.add(par)

print(len(st))

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * n

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] > self.rank[y]:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
        else:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

n, m = map(int,input().split())
edges = []
for i in range(m):
    a,b,_ = map(int,input().split())
    edges.append([a-1,b-1])

uf = UnionFind(n)
point = n*(n-1)//2
ans = []

while edges:
    ans.append(point)
    a, b = edges.pop()
    pa = uf.find(a)
    pb = uf.find(b)
    uf.union(a,b)

score = 0
for i in range(n):
    if uf.size[i] != 0:
        score += 1

print(score)

Solution (Python):
N, M = map(int, input().split())

nlist = [] * N
for i in range(N):
    nlist.append([])
for i in range(M):
    X, Y, Z = map(int, input().split())
    X -= 1
    Y -= 1
    nlist[X].append(Y)
    nlist[Y].append(X)

visit = [False] * N
ans = 0
for i in range(N):
    if visit[i]:
        continue
    ans += 1
    visit[i] = True
    vlist = nlist[i]
    while vlist:
        tmp = []
        for to in vlist:
            if visit[to]:
                continue
            visit[to] = True
            tmp.extend(nlist[to])
        vlist = tmp

print(ans)

Solution (Python):
n, m = map(int,input().split())
A = [list(map(int,input().split())) for i in range(m)]

B = [[] for i in range(n+1)]

deta = [-1 for i in range(n+1)]
for i in range(len(A)):
    B[A[i][0]].append(A[i][1])
    B[A[i][1]].append(A[i][0])
    deta[A[i][0]]=0
    deta[A[i][1]]=0

count = 0
start = 1

while start < n+1 :
    while start < n+1 and deta[start]!=0 :
        start += 1

    if start < n+1 :
        count += 1
        

        nurulist = [start]
        t = 0
        while t < len(nurulist):
            k = nurulist[t]
            for j in range(len(B[k])):
                if deta[B[k][j]] == 0:
                    deta[B[k][j]] = 1
                    nurulist.append(B[k][j])
            t += 1

print(count+deta.count(-1)-1)

Solution (Python):

import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


class UnionFind:
    def __init__(self, n):
        self._parents = list(range(n))
        self._ranks = [0] * n
        self._size = [1] * n

    def root(self, x):
        if self._parents[x] == x:
            return x
        self._parents[x] = self.root(self._parents[x])
        return self._parents[x]

    def size(self, x):
        return self._size[self.root(x)]

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return

        if self._ranks[rx] < self._ranks[ry]:
            self._parents[rx] = ry
            self._size[ry] += self._size[rx]
        else:
            self._parents[ry] = rx
            self._size[rx] += self._size[ry]
            if self._ranks[rx] == self._ranks[ry]:
                self._ranks[rx] += 1

    def same(self, x, y):
        return self.root(x) == self.root(y)



def solve(N: int, M: int, X: "List[int]", Y: "List[int]", Z: "List[int]"):
    uf = UnionFind(N)
    qq = UnionFind(N)

    for x, y, z in zip(X, Y, Z):
        x -= 1
        y -= 1
        uf.unite(x, y)
        
        
        
        

    return len(set([uf.root(i) for i in range(N)]))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    X = [int()] * (M)  
    Y = [int()] * (M)  
    Z = [int()] * (M)  
    for i in range(M):
        X[i] = int(next(tokens))
        Y[i] = int(next(tokens))
        Z[i] = int(next(tokens))
    result = solve(N, M, X, Y, Z)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()