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

Submission status: Accepted

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

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


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

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

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

Submission status: Accepted

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


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


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

print(a.count(-1))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# abc126/abc126_e
import sys

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


class UnionFindNode(object):
    def __init__(self, group_id, parent=None, value=None):
        self._group_id = group_id
        self._parent = parent
        self.value = value
        self._rank = 1
    
    def __str__(self):
        template = "UnionFindNode(group_id: {}, \n\tparent: {}, value: {}, size: {})"
        return template.format(self._group_id, self._parent, self.value, self._rank)
    
    def is_root(self):
        return not self._parent
    
    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent._parent
            self._parent = parent
        return parent
    
    def find(self):
        root = self.root()
        return root._group_id
    
    def rank(self):
        root = self.root()
        return root._rank

    def unite(self, unite_node):
        root = self.root()
        unite_root = unite_node.root()

        if root._group_id != unite_root._group_id:
            if root.rank() > unite_root.rank():
                unite_root._parent = root
                root._rank = max(root._rank, unite_root._rank + 1)
            else:
                root._parent = unite_root
                unite_root._rank = max(root._rank + 1, unite_root._rank)

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

main()

Submission status: Accepted

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

class UnionFindVerSize():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる
        self._parent = [n for n in range(0, N)]
        # グループのサイズ（個数）
        self._size = [1] * N

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

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

        # 小さい方を大きい方に併合させる（木の偏りが減るので）
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

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

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


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

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

    Union-Findを使えばよい。

    """
    N, M = list(map(int, input().split()))
    X, Y, Z = [], [], []
    uf = UnionFindVerSize(N)
    for i in range(M):
        x, y, z = list(map(int, input().split()))
        x, y = x-1, y-1
        uf.unite(x, y)
    
    # 答えは、(グループの数) 
    ans = 0
    for i in range(N):
        if uf.find_root(i) == i:
            ans += 1
    
    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

import sys
sys.setrecursionlimit(10000)

class UnionFind:
    def __init__(self, length):
        # 自身を親として初期化 (-1)。正ならサイズを表す
        self.ary = [-1 for i in range(length)]
    
    def get_root(self, x):
        # rootのidxを求める
        if self.ary[x] < 0:
            return x
        else:
            self.ary[x] = self.get_root(self.ary[x])
            return self.ary[x]

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

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


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

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

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

# rootの数を数える＝グラフの数を数える
s = set()
for i in range(N):
    s.add(uf.get_root(i))

print(len(s))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(150000)
def search(i, visited, ns) :
    #print(":", i+1)
    visited[i] = True
    for next, weight in ns[i]:
        if visited[next] == False:
            search(next, visited, ns)


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

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

Submission status: Accepted

Solution code:
# Union-Find木
class UnionFind:
    # 経路圧縮・ランク
    # クエリO(α(N))
    # original: http://at274.hatenablog.com/entry/2018/02/02/173000

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

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


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

Submission status: Accepted

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

    def find(self, x):
        # If x is root
        if self.parent[x] == x:
            return x
        # If x is not root, search again by using x's parent
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        # Make an edge from the root of lower tree to the root of higher tree
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[y] = x
            self.size[x] += self.size[y]
            # If the height of tree the tree is the same, increase one of the heights by 1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

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

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



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

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


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

print(ans)

Submission status: Accepted

Solution code:
#E問題
#UnionFind(normal)
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    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):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        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
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
        
"""
Class呼び出しの際には,UnionFind(Number)とする.関数の引数にはUnite(x,y)やisSameGroup(x,y)とする.
"""
    
if __name__ == "__main__":
  
    N,M = map(int,input().split())
    uf = UnionFind(N+1)
    for i in range(M):
        X,Y,Z = map(int,input().split())
        if not uf.isSameGroup(X,Y):
            uf.Unite(X,Y)
    ans=0
    for j in uf.root[1:N+1]:
        if j < 0:
            ans+=1
    print(ans)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

cnt = 1 # to N
conti = 0
q = [0]
used[0] = True

i = 0

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
c = list(range(n+1))
k = n
a = []
for i in range(n+1):
  a.append([i])
  
#print(a)
for i in range(m):
    x,y,z = map(int,input().split())
    t = c[x]
    s = c[y]
    if t == s:
        continue
    
    if len(a[s]) > len(a[t]):
        t,s = s,t
    a[t] += a[s]
    for z in a[s]:
        c[z] = t
    a[s] = []
    k -= 1
    
print(k)

Submission status: Accepted

Solution code:
from collections import deque
import heapq        

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            if self.same_check(x, y) != True:
                self.size[y] += self.size[x]
                self.size[x] = 0
            self.par[x] = y
        else:
            if self.same_check(x, y) != True:
               self.size[x] += self.size[y]
               self.size[y] = 0
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
               self.rank[x] += 1

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

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

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

D = defaultdict(int)


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

print(len(D))

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq as hq
import itertools as its
import operator as op


# globals
inf = float('inf')
N = 0


def set_inputs():
    global N
    return


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

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


def main():
    setrecursionlimit(100000)
    set_inputs()
    # ----------MAIN----------
    N, M = get_li()
    X, Y, Z = get_data(M, [int, int, int])
    uf = UnionFind(N)
    for x, y, _ in zip(X, Y, Z):
        uf.union(x, y)
    for i in range(N+1):
        uf.find(i)
    print(len(set(uf.par[1:])))
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


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


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


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()

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):
    a,b,c=map(int, input().split())
    uf1.union(a-1,b-1)
for i in range(n):
    uf1.find(i)
print(len(set(uf1.par)))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.data = [-1 for _ in range(size)]
    def find(self, x):
        if self.data[x] < 0:
            return x
        else:
            self.data[x] = self.find(self.data[x])
            return self.data[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(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 same(self, x, y):
        return (self.find(x) == self.find(y))
    def size(self, x):
        return -self.data[self.find(x)]


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

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

s = set()
for i in range(1, N + 1):
    s.add(uf.find(i))

print(len(s))

Submission status: Accepted

Solution code:
read = input
n, m = map(int, read().split())
f = [-1 for i in range(n + 1)] # 1 ~ n
def find(x):
    if f[x]<0:
        return x
    else :
        f[x] = find(f[x])
        return f[x]
for i in range(m):
    x,y,z = map(int, read().split())
    if abs(x) < abs(y): #合并到x上，保证x是大集合
        x,y = y,x
    fx = find(x)
    fy = find(y)
    if fx == fy:continue
    f[fx] = f[fx] - 1
    f[fy] = fx
#     print(x,y,fx,fy,f)

ans = 0
for i in range(1, n+1): # 1~n
    if f[i] < 0:
        ans += 1
print(ans)

Submission status: Accepted

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

l = [[] for _ in range(N)]
for x, y, _ in XYZ:
    l[x-1].append(y-1)
    l[y-1].append(x-1)

visited = [False]*N
count = 0
for i in range(N):
    # 訪れたことがあれば
    if visited[i] == True:
        continue
    visited[i] = True
    q = l[i]
    while q:
        r = []
        for y in q:
            if visited[y] == True:
                continue
            visited[y] = True
            r += l[y]
        q = r
        # print(q)
    count += 1
    # print(i, count, visited)

# print(count, visited)
print(count)

Submission status: Accepted

Solution code:
inpl = lambda: list(map(int,input().split()))
import numpy as np
class ParityTree:
    def __init__(self,N):
        self.parent = [-1]*int(N)
        self.parity = [0]*int(N)

    def root(self, n):
        if self.parent[n] < 0:
            return n, 0
        else:
            m, p = self.root(self.parent[n])
            self.parent[n] = m
            self.parity[n] = (p + self.parity[n]) % 2
            return m, self.parity[n]

    def merge(self, m, n, parity):
        rm, pm = self.root(m)
        rn, pn = self.root(n)
        if rm != rn:
            if -self.parent[rm] < -self.parent[rn]:
                rm, rn = rn, rm
            self.parent[rm] += self.parent[rn]
            self.parent[rn] = rm
            self.parity[rn] = (pm + pn + parity) % 2

    def size(self, n):
        return -self.parent[self.root(n)]
    
    def aresame(self, m, n):
        return self.root(m) == self.root(n)

N, M = inpl()
pt = ParityTree(N)
for i in range(M):
    X, Y, Z = inpl()
    pt.merge(X-1,Y-1,Z)

print(len(np.where(np.array(pt.parent)<0)[0]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
# 連結成分
# UF tree

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

root = list(range(N+1))
depth = [0] * (N+1)

def find_root(x):
  y = root[x]
  if x == y:
    return x
  z = find_root(y)
  root[x] = z
  return z

def merge(x,y):
  global n_component
  xx = find_root(x)
  yy = find_root(y)
  if xx == yy:
    return
  n_component -= 1
  if depth[xx] >= depth[yy]:
    root[yy] = xx
    depth[xx] += 1
  else:
    root[xx] = yy
    depth[yy] += 1
  
for _ in range(M):
  x,y,z = [int(x) for x in input().split()]
  merge(x,y)

answer = n_component
print(answer)

Submission status: Accepted

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


n, m = map(int, raw_input().split(" "))
uf = UnionFind(n)

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

counter = set()
for i in range(0, n):
    a = uf.find(i)
    # print("%d-%d" % (i, a))
    counter.add(uf.find(i))

print(len(counter))

Submission status: Accepted

Solution code:
class uf_tree:
    def __init__(self, n):
        self._size = n
        self.sizes = [1] * n
        self.par = list(range(n))
 
    def find(self, x):
        if x == self.par[x]:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]
 
    def unite(self, x, y):
        self._size -= 1
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.sizes[x] < self.sizes[y]:
            x, y = y, x
        self.par[y] = x
        self.sizes[x] += self.sizes[y]
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def size(self, x):
        return self.sizes[self.find(x)]


n, m = map(int, input().split())
uf = uf_tree(n+1)

for _ in range(m):
    x, y, z = map(int, input().split())
    if uf.same(x, y):
        continue
    uf.unite(x, y)

print(uf._size - 1)

Submission status: Accepted

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    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):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        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
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]



if __name__ == "__main__":

    # unionfindを試す

    N, M = map(int,input().split())
    uf = UnionFind(N+1)
    for i in range(M):
        X,Y,Z = map(int,input().split())
        if not uf.isSameGroup(X,Y):
            uf.Unite(X,Y)
    print(sum([1 for i in uf.root[1:N+1] if i <0]))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
p1 = [i for i in range(n)]
s1 = [1 for _ in range(n)]

def root(i):
  if p1[i] == i:
    return i
  else:
    p1[i] = root(p1[i])
    return p1[i]

def unite(i, j):
  pi = root(i)
  pj = root(j)
  if pi == pj:
    return
  else:
    if s1[pi] < s1[pj]:
      p1[pi] = pj
    elif s1[pj] < s1[pi]:
      p1[pj] = pi
    else:
      if pi < pj:
        p1[pj] = pi
        s1[pi] += 1
      else:
        p1[pi] = pj
        s1[pj] += 1

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2000000)
def func(c,x):
    c[x][0] = 1
    for i in c[x][1:]:
        if c[i][0] == 0:
            func(c,i)
    return c

# 入力
N,M = map(int,input().split())
XYZ = list(list(map(int,input().split()))for i in range(M))
############################################
card = [[0]for i in range(N)]
set = 0
############################################
# グラフを描く
for x,y,z in XYZ:
    card[x-1].append(y-1)
    card[y-1].append(x-1)
############################################
for i in range(N):
    if card[i][0] == 0:
        set += 1
        card = func(card,i)
############################################
print(set)

Submission status: Accepted

Solution code:
class Unionfind():
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        while(self.table[x] >= 0):
            x = self.table[x]
        return x

    def union(self, x, y):
        xp = self.find(x)
        yp = self.find(y)
        if xp != yp:
            if self.table[xp] <= self.table[yp]:
                self.table[xp] += self.table[yp]
                self.table[yp] = xp
            else:
                self.table[yp] += self.table[xp]
                self.table[xp] = yp

n, m = map(int, input().split())
clue = Unionfind(n)
for _ in range(m):
    x, y, _ = map(int, input().split())
    clue.union(x-1, y-1)
roots = set()
for i in range(n):
    roots.add(clue.find(i))
print(len(roots))

Submission status: Accepted

Solution code:
from collections import defaultdict


class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                # 経路圧縮
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

    def unite(self, x, y):
        return self._unite(self.find(x), self.find(y))

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            return x


utf = UnionFindTree()

N, M = map(int, input().split())
for n in range(N):
    utf.make(n + 1)

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

h = defaultdict(int)
for n in range(N):
    x = utf.find(n + 1)
    h[x] += 1

ans = 0
rest = N
for k, v in h.items():
    ans += 1
    rest -= v
print(ans + rest)