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):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy


import heapq
sys.setrecursionlimit(10**6)

INF = 10**18
import bisect
import statistics
mod = 10**9+7



class UnionFind():
    
    
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    
    def group_count(self):
        return len(self.roots())

    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

class UnionFindLabel(UnionFind):
    def __init__(self, labels):
        assert len(labels) == len(set(labels))

        self.n = len(labels)
        self.parents = [-1] * self.n
        self.d = {x: i for i, x in enumerate(labels)}
        self.d_inv = {i: x for i, x in enumerate(labels)}

    def find_label(self, x):
        return self.d_inv[super().find(self.d[x])]

    def union(self, x, y):
        super().union(self.d[x], self.d[y])

    def size(self, x):
        return super().size(self.d[x])

    def same(self, x, y):
        return super().same(self.d[x], self.d[y])

    def members(self, x):
        root = self.find(self.d[x])
        return [self.d_inv[i] for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [self.d_inv[i] for i, x in enumerate(self.parents) if x < 0]


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

l = [i for i in range(1, N+1)]
u = UnionFindLabel(l)

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

    u.union(x, y)

print(len(u.roots()))

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

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

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != 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 samegrp(self, x, y):
        return self.root(x) == self.root(y)

n, m = [int(x) for x in input().split()]
A = UnionFind(n)
ans = n
for i in range(m):
    x, y, _ = [int(z) - 1 for z in input().split()]
    if not A.samegrp(x, y):
        ans -=1
    A.union(x, y)

print(ans)

Solution (Python):
n,m=map(int,input().split())

par=[i for i in range(n)]
size=[1]*n

def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
def union(a,b):
  x=find(a)
  y=find(b)
  if x!=y:
    if size[x]<size[y]:
      par[x]=par[y]
      size[y]+=size[x]
    else: 
      par[y]=par[x]
      size[x]+=size[y]
  else:
    return

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


ans={find(i) for i in range(n)}

print(len(ans))

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N,M=list(map(int,input().split()))
Network = UnionFind(N)
for i in range(M):
    X,Y,Z = list(map(int,input().split()))
    Network.union(X-1, Y-1)
print(Network.group_count())

Solution (Python):
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)

    if x == y:
      return

    if self.parents[x] > self.parents[y]:
      x, y = y, x

    self.parents[x] += self.parents[y]
    self.parents[y] = x

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

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

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

  def group_count(self):
    return len(self.roots())

  def all_group_members(self):
    return {r: self.members(r) for r in self.roots()}

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
  
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.group_count())

Solution (Python):
n, m = map(int, input().split())

parent = [i + 1 for i in range(n)]
rank = [0 for i in range(n)]

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

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

for i in range(m):
    x, y, z = map(int, input().split())
    unite(x, y)
ans = n
for i in range(n):
    if find(i + 1) != i + 1:
        ans -= 1
print(ans)

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, M = LI()
    G = collections.defaultdict(list)
    for _ in range(M):
        X, Y, _ = LI_()
        G[X].append(Y)
        G[Y].append(X)

    
    visited = [False] * N
    def dfs(c):
        visited[c] = True
        for n in G[c]:
            if not visited[n]:
                dfs(n)

    ans = [0]
    for i in range(N):
        if not visited[i]:
            dfs(i)
            ans[0] += 1

    print(ans[0])

if __name__ == '__main__':
    resolve()

Solution (Python):
N, M = map(int,input().split())
par = [i for i in range(N+1)]
size = [1 for _ in range(N+1)]

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

def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y
    size[y] += size[x]
    size[x] = 0

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

Ans = 0
for j in size[1:]:
    if j != 0:
        Ans += 1
print(Ans)

Solution (Python):
N, M = map(int,input().split())
par = [i for i in range(N+1)]
size = [1 for _ in range(N+1)]

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

def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 1
    par[x] = y
    size[y] += size[x]
    size[x] = 0

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

Ans = 0
for j in size[1:]:
    if j != 0:
        Ans += 1
print(Ans)

Solution (Python):
N, M = map(int,input().split())
par = [i for i in range(N+1)]
size = [1 for _ in range(N+1)]

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

def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y
    size[y] += size[x]
    size[x] = 0

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

Ans = 0
for j in size[1:]:
    if j != 0:
        Ans +=1
print(Ans)

Solution (Python):
from collections import *
n,m=map(int,input().split())
v=[False for i in range(n)]
t=[[]for i in range(n)]
for i in range(m):
    x,y,z=map(int,input().split())
    x,y=x-1,y-1
    t[x].append(y)
    t[y].append(x)
ans=0
for i in range(n):
    if v[i]:
        continue
    else:
        ans+=1
        for j in t[i]:
            q=deque()
            if v[j]==False:
                q.append(j)
                while q:
                    k=q.popleft()
                    v[k]=True
                    for l in t[k]:
                        if v[l]==False:
                            q.append(l)
print(ans)

Solution (Python):
N, M = map(int,input().split())
par = [i for i in range(N+1)]
size = [1 for _ in range(N+1)]

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

def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y
    size[y] = size[x] + size[y]
    size[x] = 0
    
for i in range(M):
    x, y,  z= map(int,input().split())
    unite(x,y)
    
Ans =0
for j in size[1:]:
    if j != 0:
        Ans +=1
print(Ans)

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.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)
n,m=map(int,input().split())
uf1=UnionFind(n)

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

for i in range(n):uf1.find(i)  
ans=set()
for i in uf1.par:
     ans.add(i)
print(len(ans))

Solution (Python):
N, M = map(int,input().split())
par = [i for i in range(N+1)]
size = [1 for _ in range(N+1)]
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) 
        return par[x]
def same(x,y):
    return find(x) == find(y)
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y
    size[y] = size[x] + size[y]
    size[x] = 0
for i in range(M):
    x, y,  z= map(int,input().split())
    unite(x,y)
Ans =0
for j in size[1:]:
    if j != 0:
        Ans +=1
print(Ans)

Solution (Python):
Cards,Hints = map(int,input().split())
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        '''
        注意：0-idx
        '''
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

uf = UnionFind(Cards)
for i in range(Hints):
    x,y,z = map(int,input().split())
    uf.union(x-1,y-1)
print(uf.group_count())

Solution (Python):
from collections import deque
n, m = map(int, input().split())


edges = [[]*n for _ in range(n)]
for i in range(m):
    x, y, z = map(int, input().split())
    edges[x-1].append(y-1)
    edges[y-1].append(x-1)

d = deque()
id_list = [-1]*n


def dfs(start, id):
    d.append(start)
    id_list[start] = id
    while d:
        p = d.pop()
        for c in edges[p]:
            if id_list[c] != -1:
                continue
            id_list[c] = id
            d.append(c)

id = 1
for i in range(n):
    if id_list[i] == -1:
        dfs(i, id)
        id += 1

print(max(id_list))

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

    def find(self, x):
        if self.root[x-1] < 0:
            return x
        else:
            self.root[x-1] = self.find(self.root[x-1])
            return self.root[x-1]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        elif self.rank[x-1] > self.rank[y-1]:
            self.root[x-1] += self.root[y-1]
            self.root[y-1] = x
            self.n-=1
        else:
            self.n-=1
            self.root[y-1] += self.root[x-1]
            self.root[x-1] = y
            if self.rank[x-1] == self.rank[y-1]:
                self.rank[y-1] += 1

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

    def count(self, x):
        return -self.root[self.find(x)-1]
    def num(self):
        return self.n

N,M=map(int,input().split())
uf=UnionFind(N)
for i in range(M):
    x,y,z=map(int,input().split())
    uf.unite(x,y)
print(uf.num())

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

    def find(self, x):
        if self.root[x-1] < 0:
            return x
        else:
            self.root[x-1] = self.find(self.root[x-1])
            return self.root[x-1]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        elif self.rank[x-1] > self.rank[y-1]:
            self.root[x-1] += self.root[y-1]
            self.root[y-1] = x
        else:
            self.root[y-1] += self.root[x-1]
            self.root[x-1] = y
            if self.rank[x-1] == self.rank[y-1]:
                self.rank[y-1] += 1

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

    def count(self, x):
        return -self.root[self.find(x)-1]

N,M=map(int,input().split())
uf=UnionFind(N)
for i in range(M):
    x,y,z=map(int,input().split())
    uf.unite(x,y)
s=set()
ans=0
for i in range(1,N+1):
    if uf.find(i) not in s:
        s.add(uf.find(i))
        ans+=1
print(ans)

Solution (Python):
class UnionFind:
	def __init__(self, size):
		self.data = [-1] * size

	def merge(self, x, y):
		x = self.root(x)
		y = self.root(y)
		if x == y: return False

		if self.data[x] < self.data[y]:
			x, y = y, x

		self.data[y] += self.data[x]
		self.data[x] = y
		return True

	def root(self, x):
		if self.data[x] < 0:
			return x
		self.data[x] = self.root(self.data[x])
		return self.data[x]

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

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

	cnt = 0
	for i in range(N):
		if uf.root(i) == i:
			cnt += 1

	print(cnt)

if __name__ == '__main__':
	main()

Solution (Python):
class UnionFind:
    """
    size の要素数の UnionFind を管理する
    data 中の負数の要素が根となる
    """

    def __init__(self, size):
        
        self.data = [-1] * size

    def merge(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y: return False

        
        if self.data[x] < self.data[y]:
            x, y = y, x

        
        self.data[y] += self.data[x]
        self.data[x] = y
        return True

    def root(self, x):
        if self.data[x] < 0:
            return x
        self.data[x] = self.root(self.data[x])
        return self.data[x]

    def size(self, x):
        """
        根は負数でデータ数を管理しているのでそれを返す
        """
        return -self.data[self.root(x)]

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

    cnt=0
    for i in range(N):
        if uf.root(i)==i:
            cnt+=1
    print(cnt)


if __name__ == '__main__':
    main()

Solution (Python):
import sys, collections

stdin = sys.stdin
n, m = map(int, stdin.readline().split())

par = [i for i in range(n)]
size = [1] * n  
rank = [1] * n  


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


def unite(x, y):
    x = find(x, par)
    y = find(y, par)

    if x != y:
        
        if rank[x] < rank[y]:
            par[x] = y
            size[y] += size[x]
        else:
            par[y] = x
            size[x] += size[y]
            if rank[x] == rank[y]:
                rank[x] += 1


for _ in range(m):
    x, y, z = map(int, stdin.readline().split())
    unite(x - 1, y - 1)
    
ans = set()
for i in range(n):
    ans.add(find(i, par))
print(len(ans))

Solution (Python):
N, M = map(int, input().split())
edges = []
for _ in range(M):
    x,y,z = map(int, input().split())
    x -= 1
    y -= 1
    edges.append((x, y))

class UnionFind():
    """
    UnionFindTreeのクラス
    
    Attributes:
    n: int: ノード数
    parents: そのノードが属する木の根を格納, 根の場合は-1

    """
    def __init__(self, n):
        """ノード数nで初期化"""
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        """ノードxが属するグループの根を返す"""
        if self.parents[x] < 0:
            return x
        else:
            
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """xが属するグループとyが属するグループを併合"""
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        """xが属するグループの要素数を返す"""
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """x, yが同じグループに属するかどうかを返す"""
        return self.find(x) == self.find(y)

    def members(self, x):
        """xが属するグループ内の要素をリストで返す"""
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        """全ての根に対する要素をリストで返す"""
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        """グループの総数を返す"""
        return len(self.roots())

    def all_group_members(self):
        """{root: [そのグループの要素リスト]}の辞書を返す"""
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        """printデバッグ用. root: [要素リスト]をstrで返す"""
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


uf = UnionFind(N)
for u, v in edges:
    uf.union(u, v)
print(uf.group_count())

Solution (Python):
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
ceil = math.ceil
class unionfind():
    def __init__(self,n):
        self.n = n
        self.par = list(range(n))
        self.size = [1]*n
        self.rank = [0]*n

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

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

    def unite(self,x,y):
        x = self.root(x)
        y = self.root(y)
        if x==y:return
        else:
            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 get_size(self,x):
        x = self.root(x)
        return self.size[x]
    def parent_set(self):
        for x in range(self.n):
            self.root(x)
        s = set()
        for par in self.par:
            s.add(par)
        return s
n,m = ma()
uf = unionfind(n)
for i in range(m):
    x,y,z = ma()
    uf.unite(x-1,y-1)
s = uf.parent_set()
print(len(s))

Solution (Python):
class Union_Find():
    def __init__(self,N):
        """0,1,...,n-1を要素として初期化する.

        n:要素数
        """
        self.n=N
        self.parents=[-1]*N
        self.rank=[0]*N

    def find(self, x):
        """要素xの属している族を調べる.

        x:要素
        """
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """要素x,yを同一視する.

        x,y:要素
        """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x]>self.rank[y]:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
        else:
            self.parents[y] += self.parents[x]
            self.parents[x] = y

            if self.rank[x]==self.rank[y]:
                self.rank[y]+=1

    def size(self, x):
        """要素xの属している要素の数.

        x:要素
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """要素x,yは同一視されているか?

        x,y:要素
        """
        return self.find(x) == self.find(y)

    def members(self, x):
        """要素xが属している族の要素.
        ※族の要素の個数が欲しいときはsizeを使うこと!!

        x:要素
        """
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        """族の名前のリスト
        """
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        """族の個数
        """
        return len(self.roots())

    def all_group_members(self):
        """全ての族の出力
        """
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

print(U.group_count())

Solution (Python):
def abc126_e():
    n, m = map(int, input().split())
    par = [x for x in range(n)]
    rank = [0]*n

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

    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y: return
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]: rank[x] += 1

    for _ in range(m):
        x, y, z = map(int, input().split())
        unite(x-1, y-1)

    for i in range(n):
        _ = find(i)

    ans = len(set(par))
    print(ans)

if __name__ == '__main__':
    abc126_e()

Solution (Python):
N,M=map(int,input().split())
List = []
for i in range (M):
  List.append(list(map(int, input().split())))
List.sort()

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

uf = UnionFind(N)
for i in range(M):
  uf.union(List[i][0]-1, List[i][1]-1)
print(uf.group_count())

Solution (Python):




class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, v):  
        if self.parents[v] < 0:
            return v
        else:
            self.parents[v] = self.find(self.parents[v])
            return self.parents[v]

    def unite(self, u, v):  
        u = self.find(u)
        v = self.find(v)
        if u == v:
            return
        if self.parents[u] > self.parents[v]:  
            u, v = v, u
        self.parents[u] += self.parents[v]
        self.parents[v] = u

    def size(self, v):  
        return -self.parents[self.find(v)]

    def same(self, u, v):  
        return self.find(u) == self.find(v)



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

uf = UnionFind(N)




for _ in range(M):
    a, b, z = map(int, input().split())
    uf.unite(a - 1, b - 1)









root_list = []

for i in range(N):
    root_list.append(uf.find(i))

root_set = set(root_list)

print(len(root_set))

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

flag=list(range(N))
def takeflag(p):
    stock=[]
    while flag[flag[p]]!=flag[p]:
        stock.append(p)
        p=flag[p]
    p=flag[p]
    for i in stock:
        flag[i]=p
    return p

for i in range(M):
    x,y,z = map(int,input().split())
    x,y=x-1,y-1
    x,y = map(takeflag,(x,y))
    x,y = min(x,y),max(x,y)
    flag[x]=y

st=set()
for i in range(N):
    st.add(takeflag(i))

print(len(st))

Solution (Python):
from collections import*
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)
  def find(self, x):
    if(self.root[x] < 0):
      return x
    else:
      self.root[x] = self.find(self.root[x])
      return self.root[x]
  def unite(self, x, y):
    x = self.find(x)
    y = self.find(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 same(self, x, y):
    return self.find(x) == self.find(y)
  def count(self, x):
    return -self.root[self.find(x)]
n,m=map(int,input().split())
uf=UnionFind(n)
for _ in range(m):
  a,b,z=map(int,input().split())
  uf.unite(a,b)
a=dict(Counter([uf.find(i) for i in range(1,n+1)]))
ans=n
for i in a:
  ans-=a[i]-1
print(ans)

Solution (Python):







class Graph():

    def __init__(self):
        self.adjacency_dict = {}
    
    def add_vertex(self, v):
        self.adjacency_dict[v] = []

    def add_edge(self, v1, v2):
        self.adjacency_dict[v1].append(v2)
        self.adjacency_dict[v2].append(v1)

    def remove_edge(self, v1, v2):
        self.adjacency_dict[v1].remove(v2)
        self.adjacency_dict[v2].remove(v1)

    def remove_vertex(self,v):
        while self.adjacency_dict[v] != []:
            adjacency_vertex = self.adjacency_dict[v][-1]
            self.remove_edge(v, adjacency_vertex)
        del adjacency_vertex[v]

    def get_vertexes(self):
        return self.adjacency_dict.keys()

    def get_edges(self, v):
        return self.adjacency_dict[v]

    def print_graph(self):
        print(self.adjacency_dict)


n, m = map(int, input().strip().split())
xyz = [list(map(int, input().strip().split())) for _ in range(m)]

g = Graph()
for i in range(n):
    g.add_vertex(i)
for i in range(m):
    g.add_edge(xyz[i][0]-1, xyz[i][1]-1)

res = 0
reached_nodes = [0 for _ in range(n)]
for i in g.get_vertexes():
    if reached_nodes[i] == 1:
        continue
    res += 1
    reached_nodes[i] = 1
    q = [i]
    while len(q) > 0:
        u = q.pop()
        for v in g.get_edges(u):
            if reached_nodes[v] == 1:
                continue
            q.append(v)
            reached_nodes[v] = 1

print(res)