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


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

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

      
uf = UnionFind(N + 1)

for _ in range(M):
  X, Y, Z = map(int, input().split())
  uf.union(X, Y)
  
  
print(uf.group_count() - 1)

Submission status: Accepted

Solution code:
def find(x):
    if x == par[x]:
        return x
    par[x] = find(par[x])
    return par[x]
 
def union(x,y):
    x,y = find(x),find(y)
    if x == y:
        return
    par[y] = x
 
n,m = map(int,input().split())
par = {i:i for i in range(1,n+1)}
for _ in range(m):
    a,b,c = map(int,input().split())
    union(a,b)
print(sum([1 for i in range(1,n+1) if par[i] == i]))

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# Aでxの根を求める
def find(A,x):
    p = A[x]
    if p == x: return x
    a = find(A,p)
    A[x] = a
    return a
# Aでxとyの属する集合の併合
def union(A, x, y):
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    A[by] = bx # 根をbxに統一

N, M = lr()
V = [x for x in range(N+1)]
for _ in range(M):
    x, y, z = lr()
    if find(V, x) != find(V, y):
        union(V, x, y)

V = [find(V, x) for x in V]
s = set(V[1:])
answer = len(s)
print(answer)
# 55

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    par = [i for i in range(N)]
    rank = [1 for i in range(N)]

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

    def is_same_group(x, y):
        return find_root(x) == find_root(y)

    def unite(x, y):
        x = find_root(x)
        y = find_root(y)
        if x == y:
            return
        if rank[x] < rank[y]:
            x, y = y, x
        rank[x] += rank[y]
        par[y] = x

    def size(x):
        return rank[find_root(x)]

    for i in range(M):
        a, b, _ = (int(i)-1 for i in input().split())
        unite(a, b)
    ans = set()
    for i in range(N):
        ans.add(find_root(i))
    print(len(ans))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N,M=map(int, input().split())

    uf = UnionFindTree(N)
    for _ in range(M):
        x,y,z=map(int, input().split())
        uf.union(x-1,y-1)
    c=set([uf.find(i) for i in range(N)])
    print(len(c))


class UnionFindTree:
    def __init__(self, n):
        self.parent = [-1] * n

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

    def union(self, x, y):
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x

    def same(self, x, y): return self.find(x) == self.find(y)
    def size(self, x): return -self.parent[self.find(x)]


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    def get_root(self, node):
        parent = self.parent[node]
        if parent == -1:
            root = node
        else:
            root = self.get_root(parent)
            self.parent[node] = root  # 同じnodeへの2回目以降のget_rootを高速にするために、直接rootに繋いでおく
        return root

    def in_same_group(self, node1, node2):
        root1 = self.get_root(node1)
        root2 = self.get_root(node2)
        return root1 == root2

    def unite(self, node1, node2):
        if self.in_same_group(node1, node2):
            return
        main_root = self.get_root(node1)
        sub_root = self.get_root(node2)
        if self.rank[main_root] < self.rank[sub_root]:
            main_root, sub_root = sub_root, main_root

        self.parent[sub_root] = main_root
        self.rank[main_root] += self.rank[sub_root]
        self.groups -= 1


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

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

print(uf.groups)

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 k 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:
import sys
input = sys.stdin.readline

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

s = []
visit = [-1]*n
cnt = 0
for i in range(n):
    if visit[i] == -1:
        s.append(i)
        cnt += 1
        visit[i] = cnt
        while s:
            v = s.pop()
            for u in g[v]:
                if visit[u] == -1:
                    visit[u] = visit[v]
                    s.append(u)
print(max(visit))

Submission status: Accepted

Solution code:
class UnionFindTree:
    def __init__(self, n):
        self.par = [-1 for _ in range(n)]
        
    def find(self, x):
        if self.par[x] < 0:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]
        
    def size(self, x):
        return -self.par[self.find(x)]
        
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return 0
        if self.size(x) < self.size(y):
            x, y = y, x
        self.par[x] += self.par[y]
        self.par[y] = x
        return 1
        
n, m = map(int, input().split())
uf = UnionFindTree(n)
ans = n
for _ in range(m):
    x, y, z = map(int, input().split())
    ans -= uf.unite(x-1, y-1)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rnk = [0] * (n + 1)

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

  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if x == y:
      return 
    elif self.rnk[x] > self.rnk[y]:
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y] += 1

  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  def Count(self, x):
    return -self.root[self.Find_Root(x)]
uf = UnionFind(N)

for _ in range(M):
  x, y, z = map(int, input().split())
  uf.Unite(x, y)

roots = set()
for i in range(1, N + 1): roots.add(uf.Find_Root(i))
print(len(roots))

Submission status: Accepted

Solution code:
class UnionFind :
    def __init__(self, size) :
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        if self.parent[index] == index :  # 根の場合
            return index
        rootIndex = self.root(self.parent[index])  # 葉の場合親の根を取得
        self.parent[index] = rootIndex  # 親の付け直し
        return rootIndex

    def union(self, index1, index2) :  # 結合
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  # 連結されている場合
            return

        self.component -= 1  # 連結成分を減らす

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  # root2に結合
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  # root1に結合
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        return self.size[self.root(index)]

    def getComponent(self) :
        return self.component

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

for _ in range(M):
    fr, to, _ = map(int, input().split())
    tree.union(fr - 1, to - 1)

print(tree.getComponent())

Submission status: Accepted

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

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self._size = [1] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self._size[ra] < self._size[rb]: ra,rb = rb,ra
        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        self.count += 1
    def size(self,a):
        return self._size[self.root(a)]
uf = UnionFind(N)
for x,y,_ in XYZ:
    x,y = x-1,y-1
    if uf.is_same(x,y): continue
    uf.unite(x,y)
print(N - uf.count)

Submission status: Accepted

Solution code:
import sys

class UFT: #Union-find tree class
    def __init__(self, N): 
        self.tree = [int(i) for i in range(N)] 
        self.rank = [0 for i in range(N)]

    def find(self, a):
        if self.tree[a] == a: return a
        else:
            self.tree[a] = self.find(self.tree[a])
            return self.tree[a]

    def unite(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b: return
        if self.rank[a] < self.rank[b]: self.tree[a] = b
        else:
            self.tree[b] = a
            if self.rank[a] == self.rank[b]: self.rank[a] += 1

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    parent = UFT(N)
    for i in range(M):
        x, y, z = map(int, input().split())
        parent.unite(x-1, y-1)
    for i in range(N):
        parent.find(i)

    print(len(set(parent.tree)))
    
    return 0

if __name__ == "__main__":
    solve()

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


n, m = map(int, input().split())
uni = UnionFind(n)
cnt = 0

for i in range(m):
    x, y, _ = map(int, input().split())
    if not uni.isSameGroup(x, y):
        cnt += 1
        uni.Unite(x, y)

print(n - cnt)

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int,input().split())
E = [[] for _ in range(N+1)]
for i in range(M):
    x,y,z = map(int,input().split())
    E[x].append(y)
    E[y].append(x)

d = [-1]*(N+1)

def dfs(start,num):
    q = deque([start])
    d[start] = num
    while(q):
        v = q.pop()
        for s in E[v]:
            if(d[s] == -1):
                d[s] = num
                q.append(s)

group_num = 0
for i in range(1,N+1):
    if(d[i] == -1):
        group_num += 1
        dfs(i,group_num)

print(group_num)

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
tree=[[] for _ in range(N)]
colornum=[-1]*N
for i in range(M):
    x,y,z=map(int,input().split())
    tree[x-1].append(y-1)
    tree[y - 1].append(x - 1)
#print(tree)
for i in range(N):
    d=deque()
    if colornum[i]==-1:
        d.append(i)
        colorid = i
    else:
        colorid=colornum[i]
    while len(d)>0:
        v=d.popleft()
        colornum[v]=colorid
        for j in tree[v]:
            if colornum[j]==-1:
                d.append(j)
print(len(set(colornum)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

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

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

visited = [False for _ in range(n)]


def dfs(v, p):
    for u in tree[v]:
        if u == p:
            continue
        elif visited[u]:
            continue
        else:
            visited[u] = True
            dfs(u, v)


res = 0
for i in range(n):
    if not visited[i]:
        visited[i] = True
        dfs(i, -1)
        res += 1

print(res)

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 __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 i in range(M):
    X, Y, _ = list(map(int, input().split()))
    uf.union(X-1,Y-1)
print(uf.group_count())

Submission status: Accepted

Solution code:
#Union Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
      
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

import sys
input = sys.stdin.readline 
n,m = [int(i) for i in input().split()]
par = [-1]*n
for i in range(m):
  x,y,z = [int(i)-1 for i in input().split()]
  unite(x,y)
   
import collections
chk = []
chk = collections.deque(chk)
for i in range(n):
  chk_append = chk.append
  chk_append(find(i))
  
chk = set(chk)
print(len(chk))

Submission status: Accepted

Solution code:
#Union Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
      
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

n,m = [int(i) for i in input().split()]
par = [-1]*n
for i in range(m):
  x,y,z = [int(i)-1 for i in input().split()]
  unite(x,y)
  
chk = []
for i in range(n):
  chk_append = chk.append
  chk_append(find(i))
  
chk = set(chk)
print(len(chk))

Submission status: Accepted

Solution code:
import queue
import sys
sys.setrecursionlimit(10**6)

N, M = map(int, input().split())
XYZ = []
for _ in range(M):
    XYZ.append(tuple(map(int, input().split())))

G=[[] for _ in range(N+1)]
for el in XYZ:
    G[el[0]].append(el[1])
    G[el[1]].append(el[0])
#print(G)

seen=[False]*(N+1)
todo=queue.Queue()
def bfs(n):
    seen[n]=True
    for nxt in G[n]:
        if seen[nxt]==False:
            bfs(nxt)


cnt=0
for check in range(1, N+1):
    if seen[check]==False:
        cnt+=1
        bfs(check)
print(cnt)

Submission status: Accepted

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

par = [-1]*(N+1)


def find(x):
    if par[x] < 0:
        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 False
    else:
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True


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


def size(x):
    return -par[find(x)]

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

ans = 0
counted = [False] * (N+1)
for i in range(1,N+1):
    root = find(i)
    if not counted[root]:
        ans += 1
        counted[root] = True
print(ans)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left, bisect_right

def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iip_ord():
    return [ord(i) - ord("a") for i in input()]


def main():
    ans = solve()
    if ans is not None:
        print(ans)


class union_find():
    def __init__(self, id):
        self.parent = None
        self.id = id

    def root(self):
        if not self.parent:
            return self
        else:
            return self.parent.root()

    def union(self, target):
        sr = self.root().id
        tr = target.root().id
        if sr == tr:
            return
        elif sr > tr:
            self.root().parent = target.root()
        else:
            target.root().parent = self.root()


def solve():
    N, M = iip(False)

    uf = [union_find(i) for i in range(N)]

    for i in range(M):
        x, y, _ = iip(True)
        uf[x-1].union(uf[y-1])

    uf = set([i.root().id for i in uf])
    #print(uf)
    print(len(uf))

#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)

    if x == y:
      return

    if self.parents[x] > self.parents[y]:
            x, y = y, x

    self.parents[x] += self.parents[y]
    self.parents[y] = x

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

uf = UnionFind(N)

for _ in range(M):
  x,y,z = map(int, input().split())
  uf.union(x-1,y-1)
  
ans = len(uf.roots())
  
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

def f(j):
  nodes[j]=1
  for k in links[j]:
    if nodes[k]==0:
      f(k)

N, M=map(int, input().split())
XYZ=[list(map(int, input().split())) for _ in range(M)]
links=[[] for _ in range(N+1)]
for i in range(M):
  links[XYZ[i][0]].append(XYZ[i][1])
  links[XYZ[i][1]].append(XYZ[i][0])
  
nodes=[0]*(N+1)
ans=0
for i in range(1, N+1):
  if nodes[i]==0:
    ans+=1
    nodes[i]=1
    for j in links[i]:
      f(j)
      
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        '木の初期化をする'
        self.p = [-1] * n
        self.rank = [1]*n
        self.root = n
    def find(self, x):
        'x の親を返す'
        if self.p[x] == -1:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def unite(self, x, y):
        'rankの低い親を高い方のの親にする'
        if not self.same(x,y):
            x = self.find(x)
            y = self.find(y)
            if self.rank[x] > self.rank[y]:
                x,y = y,x
            elif self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.p[x] = y
            self.root -= 1
            return True
        else:
            return False

    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(uf.root)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

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

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

ans = set()
for i in range(N):
    ans.add(uf.find(i))

print(len(ans))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
UF = [-1] * (N+1)
def find(x):
    global UF
    if UF[x] == -1:
        return x
    else:
        UF[x] = find(UF[x])
        return UF[x]
def union(x,y):
    global UF
    xx = find(x)
    yy = find(y)
    if UF[x] == UF[y] == -1:
        UF[y] = xx
        return
    elif xx == yy:
        return 
    else:
        UF[yy] = xx
        return 
    
for _ in range(M):
    x, y, z = map(int, input().split())
    union(x,y)
    
print(sum([i < 0 for i in UF[1:]]))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ans = [-1] * N

def find(x):
    global ans
    if ans[x] == -1:
        return x
    else:
        ans[x] = find(ans[x])
        return ans[x]
    
for _ in range(M):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    xx = find(x)
    yy = find(y)
    if ans[x] == ans[y] == -1:
        ans[y] = x
    elif xx == yy:
        continue
    else:
        ans[yy] = xx

n = 0
for i in ans:
    if i == -1:
        n += 1

print(n)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


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, readline().split())
xyz = [list(map(int, readline().split())) for i in range(m)]
uf = UnionFind(n)
ans = 0
for x, y, z in xyz:
    uf.union(x - 1, y - 1)
for i in range(n):
    if uf.find(i) == i:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    x, y, z = map(int, input().split())
    x, y = x-1, y-1
    edge[x].append(y)
    edge[y].append(x)

visited = [0] * N
def dfs(v):
    if visited[v] == 1:
        return
    visited[v] = 1
    for nv in edge[v]:
        dfs(nv)
ans = 0
for i in range(N):
    if visited[i] == 1:
        continue
    ans += 1
    dfs(i)

print(ans)