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:
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10 ** 6)

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

    def find(self, x):
        if self.parent[x] == x:
            return x
        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:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            elif self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.parent[y] = x
            self.size[x] += self.size[y]
            self.components -= 1

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

    def getSize(self, x):
        return self.size(self.find(x))

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

edge = [] * M
uf = UnionFind(N)

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

print(uf.components)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))#親ノード
        self.size = [1]*n #グループの要素数

    def root(self, x): #root(x): xの根ノードを返す．
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x 

    def merge(self, x, y): #merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.size[x] < self.size[y]: 
            self.size[y] += self.size[x] #yの要素数を更新
            self.parent[x] = y #xをyにつなぐ
        else:
            self.size[x] += self.size[y] #xの要素数を更新
            self.parent[y] = x #yをxにつなぐ
        return True

    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def size(self,x): #size(x): xのいるグループの要素数を返す
        return self.size[self.root(x)]


n,m = [int(i) for i in input().split()]
 
T=UnionFind(n)
c=0
for _ in [0]*m:
    x,y,z=[int(i) for i in input().split()]
    if T.merge(x-1,y-1):
        c+=1
 
print(n-c)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))#親ノード
        self.size = [1]*n #グループの要素数

    def root(self, x): #root(x): xの根ノードを返す．
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x 

    def merge(self, x, y): #merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.size[x] < self.size[y]: 
            self.size[y] += self.size[x] #yの要素数を更新
            self.parent[x] = y #xをyにつなぐ
        else:
            self.size[x] += self.size[y] #xの要素数を更新
            self.parent[y] = x #yをxにつなぐ
        return True

    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def size(self,x): #size(x): xのいるグループの要素数を返す
        return self.size[self.root(x)]


n,m = [int(i) for i in input().split()]
 
T=UnionFind(n)
c=0
for _ in [0]*m:
    x,y,z=[int(i) for i in input().split()]
    if not T.issame(x-1,y-1):
        T.merge(x-1,y-1)
        c+=1
 
print(n-c)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))#親ノード
        self.size = [1]*n #グループの要素数

    def root(self, x): #root(x): xの根ノードを返す．
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x 

    def merge(self, x, y): #merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.size[x] < self.size[y]: #xの要素数がyの要素数より「小さい」とき入れ替える
            x,y=y,x
        self.size[x] += self.size[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True

    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def size(self,x): #size(x): xのいるグループの要素数を返す
        return self.size[self.root(x)]


n,m = [int(i) for i in input().split()]
 
T=UnionFind(n)
c=0
for _ in [0]*m:
    x,y,z=[int(i) for i in input().split()]
    if not T.issame(x-1,y-1):
        T.merge(x-1,y-1)
        c+=1
 
print(n-c)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))#親ノード
        self.size = [1]*n #グループの要素数

    def root(self, x): #root(x): xの根ノードを返す．
        if self.parent[x] == x:
            return x
        elif self.parent[self.parent[x]] == x:
            return self.parent[x]
        else:
            self.parent[x] = self.root(self.parent[x]) #xをxの根に直接つなぐ
            return self.parent[x]

    def merge(self, x, y): #merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.size[x] < self.size[y]: #xの要素数がyの要素数より「小さい」とき入れ替える
            x,y=y,x
        self.size[x] += self.size[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True

    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def size(self,x): #size(x): xのいるグループの要素数を返す
        return self.size[self.root(x)]


n,m = [int(i) for i in input().split()]
 
T=UnionFind(n)
c=0
for _ in [0]*m:
    x,y,z=[int(i) for i in input().split()]
    if not T.issame(x-1,y-1):
        T.merge(x-1,y-1)
        c+=1
 
print(n-c)

Submission status: Accepted

Solution code:
N,M= map(int, input().split())
class UnionFind:
    def __init__(self, n):
        self.data = [-1] * n
    def union(self, x, y):
        x,y = self.root(x), self.root(y)
        if x != y :
            if self.data[y] < self.data[x]:
                x,y = y,x
            self.data[x] += self.data[y]
            self.data[y] = x
        return x != y
    def root(self, x):
        if self.data[x] < 0 :
            return x
        self.data[x] = self.root(self.data[x])
        return self.data[x]
    def findSet(self, x, y):
        return self.root(x) == self.root(y)
uf = UnionFind(N)
for _ in range(M):
    x,y,z= map(int, input().split())
    x-=1
    y-=1
    uf.union(x,y)
visited = set()
ans = 0
for v in range(N):
    if uf.root(v) not in visited:
        ans +=1
    visited.add(uf.root(v))
print(ans)

Submission status: Accepted

Solution code:
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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        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(self, x, y):
        return self.find(x) == self.find(y)

n, m = map(int, input().split())
uf = UnionFind(n)
for i in range(m):
    x, y, z = map(int, input().split())
    uf.unite(x-1, y-1)
print(sum(uf.par[i] == i for i in range(n)))

Submission status: Accepted

Solution code:
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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        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(self, x, y):
        return self.find(x) == self.find(y)

n, m = map(int, input().split())
uf = UnionFind(n)
for i in range(m):
    x, y, z = map(int, input().split())
    uf.unite(x-1, y-1)
print(len(set(uf.find(i) for i in range(n))))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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 num_of_group(self):
        g = 0
        for k, v in self.__table.items():
            if k == v:
                g += 1
        return g


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

    ans = uf.num_of_group() + N - len(v)
    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()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
N, M = map(int, input().split())
num_edges = M
edges = [list(map(int, input().split())) for i in range(num_edges)]
adj = [[] for i in range(N+1)]
for ed in edges:
    adj[ed[0]] += [[ed[1], ed[2]]]
    adj[ed[1]] += [[ed[0], ed[2]]]
col_list = [-1 for i in range(N+1)]

def recfun(v, col):
    col_list[v] = col #色を更新
    for ed in adj[v]: #隣接する頂点をみる
        if col_list[ed[0]] == -1: #更新していない場合
            recfun(ed[0], col) #同じ色でその先をみる
count = 0
for i in range(1, N+1):
    if col_list[i] == -1:
        count +=1
        recfun(i, count)
print(count)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**6)

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

counter = 0
c = [-1 for i in range(n)]
p = [[] for n in range(n)]

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

def dfs(num, depth):
    if c[num] != -1:
        return
    else:
        c[num] = depth
    for i in p[num]:
        dfs(i, depth)

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

print(max(c))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

N, M = [int(x) for x in input().split()]

# Union Find
# N = 100
PARENT = list(range(N))

def root(n):
    if PARENT[n] == n:
        return n
    else:
        ret = root(PARENT[n])
        PARENT[n] = ret
        return ret

def same(n1, n2):
    return root(n1) == root(n2)

def unite(n1, n2):
    n1 = root(n1)
    n2 = root(n2)
    if n1 == n2:
        return
    PARENT[n1] = n2

used = set()

for i in range(M):
    x, y, z = [int(x) for x in input().split()]
    x -= 1
    y -= 1
    unite(x, y)
    used.add(x)
    used.add(y)

s = {root(u) for u in used}

cnt = len(s) + N - len(used)

print(cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

N, M = [int(x) for x in input().split()]

# Union Find
# N = 100
PARENT = list(range(N))

def root(n):
    if PARENT[n] == n:
        return n
    else:
        ret = root(PARENT[n])
        PARENT[n] = ret
        return ret

def same(n1, n2):
    return root(n1) == root(n2)

def unite(n1, n2):
    n1 = root(n1)
    n2 = root(n2)
    if n1 == n2:
        return
    PARENT[n1] = n2

used = set()

for i in range(M):
    x, y, z = [int(x) for x in input().split()]
    x -= 1
    y -= 1
    unite(x, y)

cnt = 0
for i,p in enumerate(PARENT):
    if root(p) == i:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
# unionfind


class UnionFind(object):

    def __init__(self, n):
        self.n = n
        self.parent = list(range(self.n))
        self.rank = [0]*n

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

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


N, M = map(int, input().split())
uf = UnionFind(N+1)

for _ in range(M):
    xx, yy, zz = map(int, input().split())
    uf.unite(xx, yy)

res = [0] * (N + 1)
res_c = 0
for i in range(1, N + 1):
    j = uf.find_parent(i)
    if res[j] == 0:
        res_c += 1
    res[j] += 1

print(N - (sum(res) - res_c))

Submission status: Accepted

Solution code:
def e_one_or_two(N, M, Info):
    class UnionFind(object):
        def __init__(self, n):
            self.p = list(range(n))  # i番の頂点の親(parent)はi番とする
            self.rank = [0] * n  # 全頂点はランク0(繋がりなし)とする
            self.size = [1] * n  # 全頂点の連結成分の大きさ1とする

        def union(self, x, y):  # x, yを同じ連結成分に属させる
            u, v = self.find(x), self.find(y)
            if u == v:  # x, yは既に同じ連結成分に属していた
                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  # 根の分だけ1個「ずれる」
            # 経路圧縮を行い、連結成分の代表を更新
            self.find(x)
            self.find(y)
            return None

        def find(self, x):  # 頂点xが属する連結成分の代表(根の番号)を求める
            if self.p[x] != x:  # 頂点xの代表は他の頂点だった
                self.p[x] = self.find(self.p[x])  # 経路圧縮(xを代表につなぐ)
            return self.p[x]

        def is_same(self, x, y):  # 頂点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))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
###############################################################################

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-

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

Submission status: Accepted

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

# idxなどを振る
id_left = [i + 1 for i in range(M)]

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

    # ともにIDが振られていないとき
    if node2set_id[x] + node2set_id[y] == 0:
        id = id_left.pop()
        # x,yが所属するグループIDを振る
        node2set_id[x] = id
        node2set_id[y] = id

        # グループIDに対するセットを追加
        set_id2nodes[id] |= {x, y}

    # どちらか一方にのみIDが振られているとき(片方が0になる)
    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:
        # 同じIDならそもそも考える必要がない
        if node2set_id[x] - node2set_id[y] == 0:
            continue

        # 異なるグループのときにはマージする
        id = node2set_id[x]
        prev_y = node2set_id[y]

        # yが所属するグループIDをすべてxのものに置き換える
        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)