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):
def e_one_or_two(N, M, Info):
    class UnionFind(object):
        def __init__(self, n):
            self.p = list(range(n))  
            self.rank = [0] * n  
            self.size = [1] * n  

        def union(self, x, y):  
            u, v = self.find(x), self.find(y)
            if u == v:  
                return
            if self.rank[u] < self.rank[v]:
                self.p[u] = v  
                self.size[v] += self.size[u]  
                self.size[u] = 0  
            else:  
                self.p[v] = u
                self.size[u] += self.size[v]
                self.size[v] = 0
                if self.rank[u] == self.rank[v]:
                    self.rank[u] += 1  
            
            self.find(x)
            self.find(y)
            return None

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

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

    uf = UnionFind(N)
    for x, y, z in Info:
        if not uf.is_same(x - 1, y - 1):
            uf.union(x - 1, y - 1)
    return sum([1 for i in range(N) if i == uf.find(i)])

N, M = [int(i) for i in input().split()]
Info = [[int(i) for i in input().split()] for j in range(M)]
print(e_one_or_two(N, M, Info))

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * (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]:
                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)

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

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


for i in range(n):
    a.find(i)

print(len(set(a.par)))

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
        elif x != self.__table[x]:
            self.__table[x] = self.__root(self.__table[x])

        return self.__table[x]

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

    def union(self, x, y):
        x = self.__root(x)
        y = self.__root(y)
        if x != y:
            self.__size[y] += self.__size[x]
            self.__table[x] = y

    def size(self, x):
        return self.__size[self.__root(x)]

    def table(self):
        return self.__table


@mt
def slv(N, M, XYZ):
    uf = UnionFind()
    for x, y, _ in XYZ:
        uf.union(x, y)

    t = uf.table()
    ans = len(set(v for k, v in t.items() if k == v))
    for i in range(1, N+1):
        if i not in t:
            ans += 1
    return ans


def main():
    N, M = read_int_n()
    XYZ = [read_int_n() for _ in range(M)]
    print(slv(N, M, XYZ))


if __name__ == '__main__':
    main()

Solution (Python):
def ketu(x, y):
    gx = get_g(x)
    gy = get_g(y)
    if dep[gy] > dep[gx]:
        gx, gy = gy, gx
    if dep[gy] == dep[gx]:
        dep[gx] += 1
    oya[gy] = gx

def get_g(x):
    oyax = oya[x]
    if oyax == x:
        return x
    re = oya[x] = get_g(oyax)
    return re

n, m = map(int, input().split())
oya = [i for i in range(n + 1)]
dep = [1] * (n + 1)
for _ in range(m):
    x, y, z = map(int, input().split())
    ketu(x,y)
for i in range(1,n+1):
    get_g(i)
print(len(set(oya[1:])))

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x):
	return " ".join(map(str,x))

import collections
import itertools
import operator


class UnionFind:
    def __init__(self, x):
        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 x is not None:
            for elem in range(x+1):
                _, _, _ = 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 not self.are_same(x,y):
            xx = self.size[x]
            yy = self.size[y]
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += xx
            else:
                self.parent[y] = x
                self.size[x] += yy
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

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

    def are_same(self, x, y):
        '''print(x,y,self.find(x),self.find(y),self.find(x) == self.find(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]

n,g = m()

u = UnionFind(n-1)
co = 0
for i in range(g):
	z,x,v = m()
	u.unite(z-1,x-1)

k = list(u.grouper())

print(len(k))

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

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

    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 unite(self, u, v):
        ru = self.root(u)
        rv = self.root(v)
        if self.rank[ru] < self.rank[rv]:
            self.par[ru] = rv
        else:
            self.par[rv] = ru
            if self.rank[ru] == self.rank[rv]:
                self.rank[ru] += 1

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

    def num(self):
        mem = set()
        for i in range(1, self.n+1):
            if not self.root(i) in mem:
                mem.add(self.root(i))
        return len(mem)

u = UnionFind(N)

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

print(u.num())

Solution (Python):


from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

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

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

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if rooti < rootj:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

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





def main():
    n, m = intin()
    xyzlist = intinl(m)

    u = UnionFind(n)
    for x, y, z in xyzlist:
        u.unite(x - 1, y - 1)

    ansset = set()
    for i in range(n):
        ansset.add(u.root(i))

    print(len(ansset))



if __name__ == '__main__':
    main()

Solution (Python):


def readInts():
  return [int(s) for s in input().split(" ")]

def root(groups, n):
  i = n
  while groups[i] != i:
    i = groups[i]
  groups[n] = i
  return i

def union(groups, x, y):
  rx = root(groups, x)
  ry = root(groups, y)
  if rx != ry:
    groups[ry] = rx

def main():
  N, M = readInts()
  groups = [i for i in range(N)]

  for i in range(M):
    X, Y, Z = readInts()
    union(groups, X-1, Y-1)

  knowns = set()
  for n in range(N):
    knowns.add(root(groups, n))
  print(len(knowns))

if __name__ == "__main__":
  main()

Solution (Python):
N,M = map(int,input().split())
XYZ = [[int(x) for x in input().split()] for _ in range(M)]

par = [i for i in range(N)]
rank = [0]*N


def root(x):
    tmp = x
    while par[tmp]!=tmp:
        tmp = par[tmp]
    return tmp

def unite(x,y):
    rx = root(x)
    ry = root(y)
    if rx==ry:
        return
    if rank[rx] < rank[ry]:
        rx,ry = ry,rx
    if rank[rx] == rank[ry]:
        rank[rx] += 1
    par[ry] = rx

for x,y,z in XYZ:
    unite(x-1,y-1)

ans = 0
for i in range(N):
    if par[i] == i:
        ans += 1
print(ans)

Solution (Python):


class UnionFindVerDepth():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        
        self._parent = [n for n in range(0, N)]
        
        self._depth = [1] * N

    def find_root(self, x):
        """ xの木の根(xがどのグループか)を求める """
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x]) 
        return self._parent[x]

    def unite(self, x, y):
        """ xとyの属する集合を併合する """
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        
        if self._depth[gx] < self._depth[gy]:
            self._parent[gx] = gy
        else:
            self._parent[gy] = gx
            if self._depth[gx] == self._depth[gy]: self._depth[gx] += 1

    def get_depth(self, x):
        """ xが属するグループの深さを返す """
        return self._depth(self.find_root(x))

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x) == self.find_root(y)


def solve():
    """戦略
    □ □ □ □ □ □ □ □ □ □ □ □ □ □ □
    |_| |_| |_|     |_| | |_|_|_|
                    |___|
     1   2   3  4 5   6      7   

    上みたいなものを考えたらわかるが、答えはグループの数(=7)。

    Union-Findを使えばよい。

    """
    N, M = list(map(int, input().split()))
    X, Y, Z = [], [], []
    uf = UnionFindVerDepth(N)
    for i in range(M):
        x, y, z = list(map(int, input().split()))
        x, y = x-1, y-1
        uf.unite(x, y)
    
    
    ans = 0
    for i in range(N):
        if uf.find_root(i) == i:
            ans += 1
    
    print(ans)


if __name__ == "__main__":
    solve()

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

N, M = list(map(int, input().split()))
node2set_id = defaultdict(int)
set_id2nodes = defaultdict(set)


id_left = [i + 1 for i in range(M)]

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

    
    if node2set_id[x] + node2set_id[y] == 0:
        id = id_left.pop()
        
        node2set_id[x] = id
        node2set_id[y] = id

        
        set_id2nodes[id] |= {x, y}

    
    elif node2set_id[x] * node2set_id[y] == 0:
        id = node2set_id[x] + node2set_id[y]
        node2set_id[x] = id
        node2set_id[y] = id
        set_id2nodes[id] |= {x, y}

    
    else:
        
        if node2set_id[x] - node2set_id[y] == 0:
            continue

        
        id = node2set_id[x]
        prev_y = node2set_id[y]

        
        for y_idx in set_id2nodes[node2set_id[y]]:
            node2set_id[y_idx] = id
            set_id2nodes[id] |= {y_idx}

        del set_id2nodes[prev_y]


num = sum([len(m)-1 for m in set_id2nodes.values()])

print(N - num)

Solution (Python):
N,M=map(int,input().split())
root=[-1]*N
def search(i):
    if root[i]>=0:
        root[i]=search(root[i])
        return root[i]
    return i
for i in range(M):
    x,y,z=map(int,input().split())
    x-=1
    y-=1
    rx=search(x)
    ry=search(y)
    if rx==ry:
        continue
    elif root[rx]<=root[ry]:
        root[ry]+=root[rx]
        root[rx]=ry
    else:
        root[rx]+=root[ry]
        root[ry]=rx
ans=0
for i in range(N):
    if root[i]<0:
        ans+=1
print(ans)

Solution (Python):
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)


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

hints = []
for i in range(M):
    hints += [list(map(int, input().split()))]

union = UnionFind(N)
for hint in hints:
    x = hint[0]
    y = hint[1]
    union.union(x, y)
for i in range(N+1):
    union.find(i)
print(len(set(union.par[1:])))

Solution (Python):
def inset(a, x):
    prev = x
    while a[prev] != -1:
        prev = a[prev]
    return prev


def putset(a, in1, x, in2, y):
    if in1 == in2:
        if a[x] == -1:
            a[y] = in1
        elif a[y] == -1:
            a[x] = in2
        else:
            a[x] = in1
            a[y] = in1
    else:
        a[in2] = in1
        a[y] = in1
        if a[x] != -1:
            a[x] = in1


N, M = map(int, input().split())
a = [-1] * N
for _ in range(M):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    in1 = inset(a, x)
    in2 = inset(a, y)
    putset(a, in1, x, in2, y)

print(a.count(-1))

Solution (Python):


import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))


class UnionFindNode(object):
    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)

def main():
    N, M = i2nn()
    A = [UnionFindNode(x, value=x) for x in range(N)]
    s = 0
    for i in range(M):
        x, y, z = i2nn()
        A[x-1].unite(A[y-1])
    for a in A:
        s += int(a.is_root())
    print(s)
    return

main()

Solution (Python):


class UnionFindVerSize():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        
        self._parent = [n for n in range(0, N)]
        
        self._size = [1] * N

    def find_root(self, x):
        """ xの木の根(xがどのグループか)を求める """
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x]) 
        return self._parent[x]

    def unite(self, x, y):
        """ xとyの属する集合を併合する """
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        """ xが属するグループのサイズ（個数）を返す """
        return self._size(self.find_root(x))

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x) == self.find_root(y)


def solve():
    """戦略
    □ □ □ □ □ □ □ □ □ □ □ □ □ □ □
    |_| |_| |_|     |_| | |_|_|_|
                    |___|
     1   2   3  4 5   6      7   

    上みたいなものを考えたらわかるが、答えはグループの数(=7)。

    Union-Findを使えばよい。

    """
    N, M = list(map(int, input().split()))
    X, Y, Z = [], [], []
    uf = UnionFindVerSize(N)
    for i in range(M):
        x, y, z = list(map(int, input().split()))
        x, y = x-1, y-1
        uf.unite(x, y)
    
    
    ans = 0
    for i in range(N):
        if uf.find_root(i) == i:
            ans += 1
    
    print(ans)


if __name__ == "__main__":
    solve()

Solution (Python):


import sys
sys.setrecursionlimit(10000)

class UnionFind:
    def __init__(self, length):
        
        self.ary = [-1 for i in range(length)]
    
    def get_root(self, x):
        
        if self.ary[x] < 0:
            return x
        else:
            self.ary[x] = self.get_root(self.ary[x])
            return self.ary[x]

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

    def unite(self, x, y):
        x = self.get_root(x)
        y = self.get_root(y)
        if x==y:
            return False
        else:
            if self.ary[x] > self.ary[y]:
                x,y = y,x
            self.ary[x] += self.ary[y]
            self.ary[y] = x
            return True


N, M = map(int, input().split())
X, Y, Z = [0]*M ,[0]*M, [0]*M
uf = UnionFind(N)

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

for i in range(M):
    uf.unite(X[i], Y[i])


s = set()
for i in range(N):
    s.add(uf.get_root(i))

print(len(s))

Solution (Python):
import sys
sys.setrecursionlimit(150000)
def search(i, visited, ns) :
    
    visited[i] = True
    for next, weight in ns[i]:
        if visited[next] == False:
            search(next, visited, ns)


def dfs(ns):
    visited = [False] * len(ns)
    ans = 0
    for i in range(len(ns)):
        if not visited[i]:
            
            ans += 1
            search(i, visited, ns)
    return ans

def main():
    n,m = map(int,input().split())
    ns = [[] for _ in range(n)]
    for _ in range(m):
        (st,end,weight) = map(int,input().split())
        ns[st-1].append((end - 1,weight))
        ns[end-1].append((st-1,weight))
    ans = dfs(ns)
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):

class UnionFind:
    
    
    

    def __init__(self, n):
        self.n = 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 is_same(self, x, y):
        return self.find(x) == self.find(y)

    def groups(self):
        ret = set()
        for i in range(1, self.n+1):
            ret.add(self.find(i))
        return len(ret)


n, m = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(m)]
uf = UnionFind(n)
for x, y, _ in data:
    uf.union(x, y)
print(uf.groups())

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

    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 union(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 check_same(self, x, y):
        return self.find(x) == self.find(y)

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

    def merge(self, x, y):
        """
        "データ構造をマージする一般的なテク"
        """
        x = self.find(x)
        y = self.find(y)
        if len(self.group[x]) < len(self.group[y]):
            x, y = y, x
        self.group[x].extend(self.group[y])
        self.group[y] = []
        self.parent[y] = x



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

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


se = set()
ans = 0
for i in range(1, N+1):
    tmp = uf.find(i)
    if tmp in se:
        continue
    else:
        ans += 1
        se.add(tmp)

print(ans)

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)]
        
"""
Class呼び出しの際には,UnionFind(Number)とする.関数の引数にはUnite(x,y)やisSameGroup(x,y)とする.
"""
    
if __name__ == "__main__":
  
    N,M = map(int,input().split())
    uf = UnionFind(N+1)
    for i in range(M):
        X,Y,Z = map(int,input().split())
        if not uf.isSameGroup(X,Y):
            uf.Unite(X,Y)
    ans=0
    for j in uf.root[1:N+1]:
        if j < 0:
            ans+=1
    print(ans)

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

a = [[] for i in range(n)]

for i in range(m):
    x,y,z = map(int, input().split())
    x-=1
    y-=1
    a[x].append(y)
    a[y].append(x)
b = [0 for i in range(n)]
ans = 0

for j in range(n):
    if b[j]==1:
        continue
    else:
        b[j]=1
        ans += 1
        stack = [j]
    while stack:
        p = stack.pop()
        for i in range(len(a[p])):
            if b[a[p][i]]==0:
                b[a[p][i]]=1
                stack.append(a[p][i])
print(ans)

Solution (Python):
N,M = map(int ,input().split())
 
used = [False]*N
tolist = [[] for i in range(N)]
 
for i in range(M):
    x,y,z = map(int,input().split())
    x -= 1; y -= 1
    tolist[x].append(y)
    tolist[y].append(x)

cnt = 1 
conti = 0
q = [0]
used[0] = True

i = 0

while q != [] or cnt < N:
    if q == []:
        conti += 1
        found = False
        while i < N:
            if not used[i]:
                found = True
                used[i] = True
                q = [i]
                cnt += 1
                break
            i += 1
    v = q.pop(0)
    for w in tolist[v]:
        if not used[w]:
            used[w] = True
            q.append(w)
            cnt += 1
print(conti+1)

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):
from collections import deque
import heapq        

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

ans = 0
visited = [False]*N
for i in range(N):
    if visited[i]:
        continue
    stack = [i]
    while stack:
        v = stack.pop()
        for u in edges[v]:
            if not visited[u]:
                visited[u] = True
                stack.append(u)
    ans += 1
print(ans)

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)
        self.size = [1] * (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 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 self.rank[x] < self.rank[y]:
            if self.same_check(x, y) != True:
                self.size[y] += self.size[x]
                self.size[x] = 0
            self.par[x] = y
        else:
            if self.same_check(x, y) != True:
               self.size[x] += self.size[y]
               self.size[y] = 0
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
               self.rank[x] += 1

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

def getlist():
    return list(map(int, input().split()))

N, M = getlist()
U = UnionFind(N)
for i in range(M):
    X, Y, Z = getlist()
    U.union(X, Y)

D = defaultdict(int)


for i in range(1, N + 1):
    n = U.find(i)
    D[n] += 1

print(len(D))

Solution (Python):
N,M = map(int,input().split())
XYZ = [[int(x) for x in input().split()] for _ in range(M)]

par = [i for i in range(N)]
rank = [0]*N


def root(x):
    tmp = x
    while par[tmp]!=tmp:
        tmp = par[tmp]
    return tmp

def unite(x,y):
    rx = root(x)
    ry = root(y)
    if rx==ry:
        return
    if rank[rx] < rank[ry]:
        rx,ry = ry,rx
    if rank[rx] == rank[ry]:
        rank[rx] += 1
    par[ry] = rx

for x,y,z in XYZ:
    unite(x-1,y-1)

ans = 0
for i in range(N):
    if par[i] == i:
        ans += 1
print(ans)