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



Sample input:
3 1
1 2 1


Sample output:
2

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    

    class UnionFindTree:
        def __init__(self, num_of_elm):
            self.n = num_of_elm
            self.table = [i for i in range(self.n)]
            self.rank = [0] * self.n
            self.group_size = [1] * self.n
        
        def _find_set(self, x):
            parent = self.table[x]
            if x == parent:
                return x
            else:
                root = self._find_set(parent)
                # 経路圧縮
                self.table[x] = root
                return root
        
        def is_same(self, x, y):
            return self._find_set(x) == self._find_set(y)

        def union(self, x, y):
            shallow_root = self._find_set(x)
            deep_root = self._find_set(y)
            if self.rank[shallow_root] > self.rank[deep_root]:
                shallow_root, deep_root = deep_root, shallow_root
            # そもそも同一グループだった時
            if shallow_root == deep_root:
                return False
            # グループが異なるので union
            else:
                self.table[shallow_root] = deep_root
                self.group_size[deep_root] += self.group_size[shallow_root]
                # 深さが等しかったときはつけ加えられた側の rank をインクリメントする
                if self.rank[shallow_root] == self.rank[deep_root]:
                    self.rank[deep_root] += 1
                return True

        def akin_num(self, x):
            x_root = self._find_set(x)
            return self.group_size[x_root]

        def print_group_id(self):
            print([self._find_set(x) for x in self.table])    
    

    n, m = mi()
    uf = UnionFindTree(n)
    groups = n
    for _ in range(m):
        x, y, _ = mi()
        x -= 1
        y -= 1
        if uf.union(x, y):
            groups -= 1
    print(groups)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import setrecursionlimit, exit
setrecursionlimit(1000000000)

from collections import Counter

def main():
    n, m = map(int, input().split())
    par = [i for i in range(n)]
    size = [1] * n

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

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

    def unite(x, y):
        x = root(x)
        y = root(y)
        if x == y:
            return
        par[x] = y
        size[y] += size[x]
    
    for _ in range(m):
        x, y, z = map(int, input().split())
        unite(x - 1, y - 1)
    for i in range(n):
        root(i)
    print(len(Counter(par)))

main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

#初期値が0の辞書
from collections import defaultdict
xyz = defaultdict(lambda: set([]))
for _ in range(m):
    x,y,z=map(int,input().split())
    xyz[x].add(y)
    xyz[y].add(x)

no_checked=[0]*n

def DFS(x):
    global no_checked
    global xyz
    no_checked[x-1]=1
    for item in xyz[x]:
        if no_checked[item-1]==0:
            DFS(item)

cnt=0
for i in range(1,n+1):
    if no_checked[i-1]==0:
        cnt+=1
        DFS(i)

    #print(i,no_checked)
print(cnt)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


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())


def main():
    N, M = [int(x) for x in input().split()]
    XYZ = [[int(x) for x in input().split()] for _ in range(M)]

    u = UnionFind(N)

    for x, y, z in XYZ:
        u.union(x - 1, y - 1)

    print(u.group_count())


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


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())


def main():
    N, M = [int(x) for x in input().split()]
    XYZ = [[int(x) for x in input().split()] for _ in range(M)]

    u = UnionFind(N + 2)

    f = True
    for x, y, z in XYZ:
        x += 1
        y += 1
        if z % 2 == 0:
            u.union(x, y)
        else:
            if f:
                f = False
                u.union(x, 0)
                u.union(y, 1)
            if u.same(x, 0):
                u.union(y, 1)
            if u.same(x, 1):
                u.union(y, 0)
            if u.same(y, 0):
                u.union(x, 1)
            if u.same(y, 1):
                u.union(x, 0)

    for x, y, z in XYZ:
        x += 1
        y += 1
        if z % 2 == 1:
            u.union(x, y)
        else:
            if f:
                f = False
                u.union(x, 0)
                u.union(y, 1)
            if u.same(x, 0):
                u.union(y, 1)
            if u.same(x, 1):
                u.union(y, 0)
            if u.same(y, 0):
                u.union(x, 1)
            if u.same(y, 1):
                u.union(x, 0)

    print(u.group_count())


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = [-1] * n
        self.rank = [1] * n
        self.count = [1] * n

    def get_root(self, i):
        while self.parent[i] != -1:
            i = self.parent[i]
        return i

    def is_same_tree(self, i, j):
        return self.get_root(i) == self.get_root(j)

    def merge(self, i, j):
        i = self.get_root(i)
        j = self.get_root(j)
        if i == j:
            return

        if self.rank[i] > self.rank[j]:
            self.parent[j] = i
            self.rank[i] = max(self.rank[i], self.rank[j] + 1)
            self.count[i] += self.count[j]
        else:
            self.parent[i] = j
            self.rank[j] = max(self.rank[j], self.rank[i] + 1)
            self.count[j] += self.count[i]

n, m = [int(i) for i in input().split()]
uf = UnionFind(n)
for _ in range(m):
    x, y, _ = [int(i) - 1 for i in input().split()]
    uf.merge(x, y)
print(uf.parent.count(-1))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
XYZ=[]
for i in range(M):
  x,y,z=map(int,input().split())
  XYZ.append([x,y,z])
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 count(self,x):
    return -self.root[self.find(x)]
uf=UnionFind(N)
for i in range(M):
  uf.unite(XYZ[i][0],XYZ[i][1])
ans=-1
for i in range(len(uf.root)):
  if uf.root[i]<0:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
class UnionFindTree:
    __slots__ = ('__tree', '__current')

    def __init__(self, n):
        self.__tree = [-1] * n
        self.__current = iter(self.__tree)

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

    def union(self, x, y):
        t = self.__tree
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if t[x] > t[y]:
            x, y = y, x
        t[x] += t[y]
        t[y] = x
        return True

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

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

    def __next__(self):
        try:
            return next(self.__current)
        except StopIteration:
            self.__current = iter(self.__tree)
            raise StopIteration()

    def __iter__(self):
        return self


def spline(func_=int, iter_=None):
    if iter_ is None:
        iter_ = input().split()
    return map(func_, iter_)


def main():
    n, m = spline()
    tree = UnionFindTree(n)
    for i in range(1, m + 1):
        x, y, _ = spline(func_=lambda x: int(x) - 1)
        tree.union(x, y)
    ans = 0
    for i in tree:
        if i < 0:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class UnionFindTree:
    __slots__ = ('__tree', '__current')

    def __init__(self, n):
        self.__tree = [-1] * n
        self.__current = iter(self.__tree)

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

    def union(self, x, y):
        t = self.__tree
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if t[x] > t[y]:
            x, y = y, x
        t[x] += t[y]
        t[y] = x
        return True

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

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

    def __next__(self):
        try:
            return next(self.__current)
        except StopIteration:
            self.__current = iter(self.__tree)
            raise StopIteration()

    def __iter__(self):
        return self


def spline(func_=int, iter_=None):
    if iter_ is None:
        iter_ = input().split()
    return map(func_, iter_)


def main():
    n, m = spline()
    tree = UnionFindTree(n)
    for i in range(1, m + 1):
        x, y, _ = spline()
        x -= 1
        y -= 1
        tree.union(x, y)
    ans = 0
    for i in tree:
        if i < 0:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# E

class UnionFind():
    def __init__(self, n):
        # 根なら-size, 子なら親のIDを持つ配列
        # 最初は全て根(size:-1)として初期化する
        self.par = [-1]*n

    # 親のIDを検索する再帰関数
    def Find(self, x):
        # 親の場合、IDを返す
        if self.par[x] < 0:
            return x
        # 子の場合、その親IDで再帰呼出しする
        # 経路縮約のため、呼び出した結果で辺を張り直す
        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): 
            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 isSameGroup(self, x, y):
        return self.Find(x)==self.Find(y)
    
    def Size(self, x):
        return self.par[self.Find(x)]*-1

    def Show(self):
        return self.par

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

uf = UnionFind(n)

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

ans = 0
for i in uf.Show():
    if i<0:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import math
import operator as op
from functools import reduce
from fractions import Fraction as frac

def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer / denom
def rd(p):
    if(p==0):
        return input()
    if(p==1):
        return int(input())
    if(p==2):
        return map(int,input().split())
    if(p==3):
        return list(map(int,input().split()))

global par
par=[-1 for i in range(100001)]
# t=rd(1)
def find(u):
    if(par[u]<0):
        return u
    else:
        return find(par[u])
def uni(x,y):
    u=find(x)
    v=find(y)
    if u==v:
        return
    if(par[u]<par[v]):
        par[u]+=par[v]
        par[v]=u
    else:    
        par[v]+=par[u]
        par[u]=v
t=1
for term in range(1,t+1):
    n,m=rd(2)
    for i in range(m):
        x,y,z=rd(2)
        uni(x,y)
        # print(par[1:n+1])
    ans=0
    for i in range(1,n+1):
        if(par[i]<0):
            ans+=1
    
    print(ans)

Submission status: Accepted

Solution code:
N,M = 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):
        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):
  x,y,z=map(int,input().split())
  uf.union(x-1,y-1)
print(uf.group_count())

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
tree = [[] for i in range(n)]

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

already = [False]*n
ans = 0
for i in range(n):
  if already[i]:
    continue
  ans += 1
  not_yet = deque(tree[i])
  for value in tree[i]:
    already[value] = True
  while not_yet:
    key = not_yet.popleft()
    for value in tree[key]:
      if already[value]:
        continue
      already[value] = True
      not_yet.append(value)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(1000000)

def main():
    n, m = map(int, input().split())
    parents = [i for i in range(n)]
    for i in range(m):
        x, y, z = map(int, sys.stdin.readline().split())
        unite(x - 1, y - 1, parents)
    uniq = {find(i, parents) for i in range(n)}
    print(len(uniq))

def unite(x, y, parents):
    px = find(x, parents)
    py = find(y, parents)
    parents[py] = px

def find(x, parents):
    if parents[x] == x:
        return x
    fx = find(parents[x], parents)
    parents[x] = fx
    return fx

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(1000000)

def main():
    n, m = map(int, input().split())
    parents = [i for i in range(n)]
    for i in range(m):
        x, y, z = map(int, input().split())
        unite(x - 1, y - 1, parents)
    uniq = {find(i, parents) for i in range(n)}
    print(len(uniq))

def unite(x, y, parents):
    px = find(x, parents)
    py = find(y, parents)
    parents[py] = px

def find(x, parents):
    if parents[x] == x:
        return x
    fx = find(parents[x], parents)
    parents[x] = fx
    return fx

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
    
root=[int(i) for i in range(n)] 
rank=[0]*n    
def find(x):
    if root[x]==x:
        return x 
    else:
        return find(root[x])

for i in range(m):
    x,y,z=map(int,input().split())
    fx=find(x-1)
    fy=find(y-1)
    if rank[fx]>=rank[fy]:
        root[fy]=fx
        if rank[fx]==rank[fy]:
            rank[fx]+=1
    else:
        root[fx]=fy 
a=[]
for i in range(n):
    a.append(find(i)) 
print(len(set(a)))

Submission status: Accepted

Solution code:
n,m = 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):
        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+1)
for i in range(m):
  x,y,z = map(int, input().split())
  uf.union(x-1,y-1)
print(uf.group_count()-1)

Submission status: Accepted

Solution code:
N, M = list(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)
for j in range(M):
    x, y, z = list(map(int, input().split()))
    if not uf.is_same(x-1, y-1):
        uf.union(x-1, y-1)

# rootの個数
ans = 0
for i in range(N):
    if i == uf.par[i]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, numV):
        self.pars = list(range(numV))
        self.ranks = [0] * numV
    def getRoot(self, x):
        par = self.pars[x]
        if par != x:
            self.pars[x] = par = self.getRoot(par)
        return par
    def merge(self, x, y):
        x, y = self.getRoot(x), self.getRoot(y)
        if x == y: return
        if self.ranks[x] < self.ranks[y]:
            self.pars[x] = y
        else:
            self.pars[y] = x
            if self.ranks[x] == self.ranks[y]:
                self.ranks[x] += 1
    def isSame(self, x, y):
        return self.getRoot(x) == self.getRoot(y)
    def updatePars(self):
        for v in range(len(self.pars)):
            self.getRoot(v)

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

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

UF.updatePars()

ans = len(set(UF.pars))
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter


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):
        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
            self.size[x] += self.size[y]

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

    def get_size(self, x):
        x = self.find(x)
        return self.size[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-1, y-1)

c = Counter([uf.find(i) for i in range(n)])
print(len(c))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n=0):
        self.d = [-1]*n
        self.u = n

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

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

        self.u -= 1

        if x > y:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x

        return True

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

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

    def num_union(self):
        return self.u


N, M, *X = map(int, open(0).read().split())
X = tuple(zip(*[iter(X)]*3))

uf = UnionFind(N)
for x, y, z in X:
    uf.unite(x-1, y-1)

print(uf.num_union())

Submission status: Accepted

Solution code:
import sys

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

root = list(range(n))
height = [0] * n
size = [1] * n

def find_root(u):
  if root[u] == u: return u
  root[u] = find_root(root[u])
  return root[u]

def unite(u, v):
  ru = find_root(u)
  rv = find_root(v)
  if ru == rv: return
  if height[ru] >= height[rv]:
    root[rv] = ru
    size[ru] += size[rv]
    height[ru] = max(height[ru], height[rv] + 1)
  else:
    root[ru] = rv
    size[rv] += size[ru]

def main():
  for _ in range(m):
    x, y, z = map(int, sys.stdin.readline().split())
    unite(x-1, y-1)
  
  for i in range(n): find_root(i)
  print(len(set(root)))
  
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import collections, math, bisect

local = False
if local:
    file = open("input.txt", "r")
    import time

def inp():
    if local:
        return file.readline().rstrip()
    else:
        return input().rstrip()

def ints():
    return [int(_) for _ in inp().split()]


if local:
    start=time.time()

N,M = ints()

connection = [dict() for i in range(N)]

for i in range(1, M+1):
    x,y,z = ints()

    connection[x-1][y-1] = True
    connection[y-1][x-1] = True

ans = 0
visited = set()

for i in range(N):
    if i in visited:
        continue

    ans+=1
    stck = [i]
    visited.add(i)

    while len(stck)>0:
        vertex = stck.pop(-1)

        for nextVertex in connection[vertex]:
            if nextVertex not in visited:
                visited.add(nextVertex)
                stck.append(nextVertex)

print(ans)


if local:
    fin = (time.time()-start)*1000
    print("{:.2f}".format(fin) + "ms")

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parent=list(range(n+1))
        self.size=[1]*(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 unite(self,x,y):
    #二つのグループをつなげる
    #大きいほうに小さいほうをつなげる。
        x=self.find(x)
        y=self.find(y)
        if x==y:
            return
        else:
            if self.size[x]>=self.size[y]:
                self.parent[y]=x
                self.size[x]+=self.size[y]
            else:
                self.parent[x]=y
                self.size[y]+=self.size[x]
    def cnt(self,x):
    #サイズの取得
        return self.size[self.find(x)]

def main():
    n,m=map(int,input().split())
    u=UnionFind(n)
    for i in range(m):
        x,y,z=map(int,input().split())
        u.unite(x,y)
    ans=[0]*(n+1)
    for i in range(1,n+1):
        x=u.find(i)
        ans[x]=1
    print(sum(ans[1:]))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# Union-Find -- START --
class UnionFind():
  def __init__(self,sz):
    self.sz=sz
    self.data=[-1]*sz

  def unite(self,x,y):
    x=self.find(x)
    y=self.find(y)
    if x==y:
      return False
    if self.data[x]>self.data[y]:
      x,y=y,x
    self.data[x]+=self.data[y]
    self.data[y]=x
    return True

  def find(self,k):
    if self.data[k]<0:
      return k
    self.data[k]=self.find(self.data[k])
    return self.data[k]

  def size(self,k):
    return -self.data[self.find(k)]
# Union-Find --- END ---

def main():
  n,m=LI()
  uf=UnionFind(n)
  for _ in range(m):
    a,b,c=LI()
    a-=1
    b-=1
    uf.unite(a,b)

  checked=[False]*n
  ans=0
  for i in range(n):
    a=uf.find(i)
    if checked[a]==False:
      checked[a]=True
      ans+=1

  return ans

# main()
print(main())