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:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

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()
uf = UnionFind(n) # 初期化

for i in range(m):
    x, y, z = MAP1()
    uf.union(x, y) # グループを併合

print(uf.group_count())

Submission status: Accepted

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

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            return self.find(self.parents[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]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1


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

ct = 0
for i in range(N):
    if uf.parents[i] < 0:
        ct += 1
print(ct)

Submission status: Accepted

Solution code:
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


import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline

n, m = map(int, input().split())
u = UnionFind(n)
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    u.Unite(a, b)
print(len(set(u.Find_Root(i) for i in range(n))))

Submission status: Accepted

Solution code:
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
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353


class UnionFind():
    # 要素0=n-1
    # parentsには親番号．根の場合は-(グループの要素数)
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # xの属するグループの根
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # xの属するグループとyの属するグループを併合
    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

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

    # x,yが同じグループに属するか否か
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # xの属するグループの要素からなるリスト
    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()}

    # {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書（print用）
    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()))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

    # A_XtoA_Yは片方が決まればもう片方も決まる よって連結成分数が答え
    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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:


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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
#z:oddなら a_x, a_y の一方が1、もう一方が２
#z:evenなら a_x, a_yがどちらも２またはどちらも１
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))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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

        # y の方がデータ数を多く
        if self.data[x] < self.data[y]:
            x, y = y, x

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

Submission status: Accepted

Solution code:
import sys, collections

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

par = [i for i in range(n)]
size = [1] * n  # size of tree
rank = [1] * n  # distance from parent


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:
        # 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))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

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

Submission status: Accepted

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