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:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
import networkx as nx
from networkx.utils import union_find
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
XYZ = [LIST() for _ in range(M)]

uf = union_find.UnionFind(range(1, N+1))

for X, Y, Z in XYZ:
	uf.union(X, Y)

print(len(list(uf.to_sets())))

Submission status: Accepted

Solution code:
from collections import deque
n , m = map(int,input().split())
route = [[] for i in range(n+1)]
for i in range(m):
    x , y , z = map(int,input().split())
    route[x].append(y)
    route[y].append(x)
    
visit = [0 for i in range(n+1)]
ans = 0
for i in range(1,n+1):
    if visit[i] == 0:
        ans += 1
        visit[i] = ans
        d = deque()
        d.append(i)
        while d:
            now = d.popleft()
            for j in route[now]:
                if visit[j] == 0:
                    visit[j] = ans
                    d.append(j)
print(max(visit))

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) # n: 頂点数

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

    uf.union(x-1, y-1)

print(uf.group_count())

Submission status: Accepted

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(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())

n,m=mp()
uf = UnionFind(n)
for i in range(m):
    X,Y,Z=mp()
    uf.union(X-1,Y-1)
print(len(uf.roots()))

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        # 正==子: 根の頂点番号 / 負==根: 連結頂点数
        self.n = n
        self.parents = [-1] * n
 
    def find(self, x):
        #要素xが属するグループの根を返す
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
 
    def union(self, x, y):
        #要素xが属するグループと要素yが属するグループとを併合する
        x = self.find(x)
        y = self.find(y)
 
        if x == y:
            return
 
        if self.parents[x] > self.parents[y]:
            x, y = y, x
 
        self.parents[x] += self.parents[y]
        self.parents[y] = x
 
    def size(self, x):
        # 要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]
 
    def same(self, x, y):
        # 要素x, yが同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)
 
    def members(self, x):
        # 要素xが属するグループに属する要素をリストで返す
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
 
    def roots(self):
        # すべての根の要素をリストで返す
        return [i for i, x in enumerate(self.parents) if x < 0]
 
    def group_count(self):
        # グループの数を返す
        return len(self.roots())
 
    def all_group_members(self):
        # {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
        return {r: self.members(r) for r in self.roots()}
 
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

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

ans = u.group_count()
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
class UnionFind:
    #def   -> foo=UnionFind(n,1)  <- 1-based index, default is 0
    #method -> foo.hoge(huga)
    __slots__ = ["_size", "_first_idx", "_parents"]
    def __init__(self, size: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [-1] * (size + first_index)
    def find(self, x: int) -> int:
        if self._parents[x] < 0:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]
    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)
    def unite(self, x: int, y: int) -> bool:
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        if self._parents[x] > self._parents[y]:
            x, y = y, x
        self._parents[x] += self._parents[y]
        self._parents[y] = x
        return True
    def size(self, x: int) -> int:
        return -self._parents[self.find(x)]
    def group_count(self) ->int:
        return sum([1 for i in  self._parents if i<0])-self._first_idx
    def connected(self) ->bool:
        return self._parents[self.find(self._first_idx)]==-self._size

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

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

n, m = map(int, input().split())
XYZ = [list(map(int, input().split())) for _ in range(m)]

uf = uf = UnionFind(n)

for x, y, z in XYZ:
  x -= 1
  y -= 1
  uf.union(x, y)
  
print(uf.group_count())

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

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

uf = UnionFind(N)

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


print(uf.group_count())

Submission status: Accepted

Solution code:
from collections import deque

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

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

visited = [False] * N

ans = 0
for i in range(N):
    if visited[i]:
        continue
    else:
        ans += 1

    q = deque([i])
    while q:
        cur = q.popleft()
        visited[cur] = True

        for next in edge[cur]:
            if visited[next]:
                continue
            visited[next] = True
            q.append(next)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

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

visited = [False] * N

ans = 0
for i in range(N):
    if visited[i]:
        continue
    else:
        ans += 1

    q = deque([i])
    while q:
        cur = q.pop()
        visited[cur] = True

        for next in edge[cur]:
            if visited[next]:
                continue
            visited[next] = True
            q.append(next)

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5+1)

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

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

visited = [False] * N

ans = 0
def dfs(x):
    global ans
    if not visited[x]:
        ans += 1
    visited[x] = True

    for x_next in edge[x]:
        if visited[x_next]:
           continue 
        visited[x_next] = True
        dfs(x_next)

for i in range(N):
    dfs(i)

print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    '''
    cited from https://note.nkmk.me/python-union-find/
    '''
    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 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())

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

u = UnionFind(N)
for i in range(M):
    x, y, z = map(int, input().split())
    u.union(x-1,y-1)
    
print(u.group_count())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    from scipy.sparse.csgraph import connected_components  # https://note.nkmk.me/python-scipy-connected-components/
    from scipy.sparse import csr_matrix
    
    N, M = map(int, input().split())  # 頂点数、辺数
    A, B, C = [0] * M, [0] * M, [1] * M  # A[i]からB[i]へコストC[i]の有向辺。
    # ただし、connected_components()では有向グラフも無向グラフとして扱われる
    for i in range(M):
        A[i], B[i] ,_= map(int, input().split())
        A[i] -= 1  # indexを調整
        B[i] -= 1
    
    csr = csr_matrix((C, (A, B)), shape=(N, N))
    # nは連結成分の個数。labelは各頂点が属する連結成分のラベル
    n, labels = connected_components(csr)
    print(n)

    
resolve()

Submission status: Accepted

Solution code:
# Union Find 木
from sys import setrecursionlimit


def find(parent, i):
    t = parent[i]
    if t < 0:
        return i
    t = find(parent, t)
    parent[i] = t
    return t


def unite(parent, i, j):
    i = find(parent, i)
    j = find(parent, j)
    if i == j:
        return
    parent[j] += parent[i]
    parent[i] = j


setrecursionlimit(10 ** 6)

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

parent = [-1] * N
for _ in range(M):
    X, Y, Z = map(int, input().split())
    unite(parent, X - 1, Y - 1)
print(len([x for x in parent if x < 0]))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,N):
        self.root = list(range(N))
        self.size = [1] * (N)
        
    def find_root(self,x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x
    
    def merge(self,x,y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        sx,sy = self.size[x],self.size[y]
        if sx < sy:
            self.root[x] = y
            self.size[y] += sx
        else:
            self.root[y] = x
            self.size[x] += sy


n, m = map(int, input().split())
xyz = []
for i in range(m):
    xyz.append(list(map(int,input().split())))
    

uf = UnionFind(n)

answer = []
find_root = uf.find_root
merge = uf.merge
for i in range(m):
    x, y, z = xyz[i][0]-1, xyz[i][1]-1, xyz[i][2]
    merge(x,y)
s = set([])
for i in range(n):
    s.add(uf.find_root(i))
print(len(s))

Submission status: Accepted

Solution code:
import queue

n, m = list(map(int, input().split()))
dic = {}  
count = 0
q = queue.Queue()

for i in range(m):
  a, b, c = list(map(int, input().split()))
  if not a-1 in dic:
    dic[a-1]=[b-1]
  else:
    dic[a-1].append(b-1)
  
  if not b-1 in dic:
    dic[b-1]=[a-1]
  else:
    dic[b-1].append(a-1)

dp = [0]*n

#print(dic)

for i in range(n):
  if dp[i]==0:
    count += 1
    dp[i]=count
    if i in dic:
      for j in dic[i]:
        dp[j]=count
        q.put(j)
    #print(dp)
    while not q.empty():
      temp = q.get()
      #print(temp)
      if temp in dic:
        for j in dic[temp]:
          if dp[j] == 0:
            dp[j]=count
            q.put(j)
#print(dp)
print(count)

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


class UnionFind:
    def __init__(self, n):
        """
        コンストラクタ
        :要素数 n:
        """
        self.n = n
        # 添字x: 値yとすると・・
        #   root以外の場合： 要素xは集合yに所属する。
        #   rootの場合　　　： 集合xの要素数はy個である。(負数で保持する)
        self.parents = [-1] * n

    def getroot(self, x):
        """
        所属する集合(ルートの番号)を取得する。
        :調査する要素 x:
        """
        # 値が負数 = ルートに到達したので、ルート木の番号を返す。
        if self.parents[x] < 0:
            return x
        else:
            # 値が正数 = ルートに到達していない場合、さらに親の情報を確認する。
            # 下の行は経路圧縮の処理。
            self.parents[x] = self.getroot(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """
        2つの要素が所属する集合をを同じ集合に結合する。
        :結合する要素(1つ目) x:
        :結合する要素(2つ目) y:
        """
        # 既に同じ集合に存在するなら何もせず終了。
        x = self.getroot(x)
        y = self.getroot(y)
        if x == y:
            return

        # 集合を結合する。
        # ※ここ、「要素数の大きい集合に、少ない集合を結合」しているが、こうすることで以後の「処理量を削減」するテクニックである。
        if self.parents[x] > self.parents[y]:
            x, y = y, x

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

    def size(self, x):
        """
        指定した集合に属する要素数を取得する。
        :調査する集合 x:
        """
        # 添え字[root]には、要素数が負数で格納されている。そのため、取得する際は-反転する。
        return -self.parents[self.getroot(x)]

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

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

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

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

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

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


# 実装を行う関数
def resolve(test_def_name=""):
    # 数値取得サンプル
    #   1行1項目 n = int(input())
    #   1行2項目 x, y = map(int, input().split())
    #   1行N項目 x = [list(map(int, input().split()))]
    #   N行1項目 x = [int(input()) for i in range(n)]
    #   N行N項目 x = [list(map(int, input().split())) for i in range(n)]

    # 文字取得サンプル
    #   1行1項目 x = input()
    #   1行1項目(1文字ずつリストに入れる場合) x = list(input())
    n, m = map(int, input().split())

    rules = [list(map(int, input().split())) for i in range(m)]

    # uf 作成(要素数を+1しているのは添え字と人番号を合わせるため)
    uf = UnionFind(n + 1)
    # UnionFindにて集合を明確にする。
    for rule in rules:
        uf.union(rule[0], rule[1])

    # グループ数を出力(添字[0]はどこにもつながらないダミーの添え字。これを除くため-1した結果を出力
    print(uf.group_count() - 1)


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3 1
1 2 1"""
        output = """2"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """6 5
1 2 1
2 3 2
1 3 3
4 5 4
5 6 5"""
        output = """2"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """100000 1
1 100000 100"""
        output = """99999"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

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


class UnionFind():
    def __init__(self, N):
        self._parent = [n for n in range(0, N)]
        self._size = [1] * N

    def find_root(self, 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):
        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):
        return self._size[self.find_root(x)]

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

    def calc_group_num(self):
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()

def main():
    N,M = mi()
    U = UnionFind(2*N+1)

    for i in range(1,N+1):
        U.unite(i,N+i)

    minus = 0
    for i in range(M):
        x,y,z = mi()
        U.unite(x,y)

    print(U.calc_group_num() - 1)




if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
Clear = [-1]*N
T = [[] for _ in range(N)]
ans = 0
for i in range(M):
    X, Y, Z = map(int, input().split())
    X -= 1
    Y -= 1
    T[X].append(Y)
    T[Y].append(X)

for i in range(N):
    if Clear[i] == -1:
        ans += 1
        Clear[i] = 1
        P = deque([i])
        while(len(P) > 0):
            t = P.popleft()
            for j in T[t]:
                if Clear[j] == -1:
                    Clear[j] = 1
                    P.append(j)
print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


class UnionFind:
    # Reference: https://note.nkmk.me/python-union-find/
    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 main():
    N, M, *XYZ = map(int, read().split())
    uf = UnionFind(N)
    for x, y, z in zip(XYZ[::3], XYZ[1::3], XYZ[2::3]):
        uf.union(x - 1, y - 1)

    print(uf.group_count())
    return


if __name__ == '__main__':
    main()

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

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

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

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

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

print(uf.group_count())

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc126/tasks/abc126_e

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

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

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

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

    def count(self, x):
        return -self.root[self.find(x)]

if __name__ == '__main__':
    n, m = map(int, input().split())
    uf = UnionFind(n)

    for _ in range(m):
        xi, yi, zi = map(int, input().split())
        xi -= 1
        yi -= 1
        uf.unite(xi, yi)

    count = 0
    for i in range(n):
        if uf.root[i] < 0:
            count += 1
    print(count)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


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

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

visited = [False for _ in range(N)]
def dfs(v):
    if visited[v]:
        return False
    visited[v] = True
    for u in adj[v]:
        dfs(u)
    return True


ans = 0
for i in range(N):
    if dfs(i):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



n,m = map(int, input().split())
from collections import defaultdict
ns = defaultdict(set)
for i in range(m):
    x,y,z = map(int, input().split())
    x -= 1
    y -= 1
    ns[x].add(y)
    ns[y].add(x)
    
seen = [False]*n
ans = 0
for start in range(n):
    if seen[start]:
        continue
    q = [(start, -1)]
    seen[start] = True
    val = None
    while q:
        u, prev = q.pop()
        for v in ns[u]:
            if v==prev:
                continue
            if seen[v]:
                val = 1
            else:
                seen[v] = True
                q.append((v, u))
    if val is None:
        val = 1
    ans += val
print(ans)

Submission status: Accepted

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

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n)
        self.size = [1] * (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:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)

uf = UnionFind(n)

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

root = set([])

for i in range(n):
    root.add(uf.find(i))

print(len(root))

Submission status: Accepted

Solution code:
from collections import Counter

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

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n)
        self.size = [1] * (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:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)

uf = UnionFind(n)

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

root = set([])

for i in range(n):
    root.add(uf.find(i))

print(len(root))