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
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
def LILI(n): return [LI() for _ in range(n)]
INF = 10 ** 18
MOD = 10 ** 9 + 7

'''MEMO:
1 or 2 が書かれている。
与えられた x, y, z について,
z が偶数なら A_x + A_y は偶数。つまり (1, 1) or (2, 2)
z が奇数なら上記は奇数。つまり (1, 2) or (2, 1)
最小何枚で確実にすべてわかるか。

結局 union-find して独立なグラフの個数を求める問題か。
'''

import collections
import itertools
import operator

class UnionFind:
    def __init__(self, elems=None):
        class KeyDict(dict):  # dict + キーがないときは dict[key] = key として key を返す。
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()  # キーがなければ孤立点→自身が key（parent[key]=key）
        self.rank = collections.defaultdict(int)  # 木の高さ。デフォルトでは 0。経路圧縮すると本来は rank が下がるが、その効果は無視している。
        self.size_ = collections.defaultdict(lambda: 1)  # 根に属する頂点の個数。根の値しか信用できない。

        if elems is not None:
            for elem in elems:
                _, _ = self.parent[elem], self.rank[elem]

    def find(self, x):  # あるキーの根を探す。O(α(n)). log より高速。
        if self.parent[x] == x:
            return x  # 自身が根なら自身を返す。
        else:
            self.parent[x] = self.find(self.parent[x])  # 再帰的に親を探して、すべて根に付け替える（経路圧縮）。
            return self.parent[x]

    def unite(self, x, y):  # O(α(n)). log より高速。
        x = self.find(x)  # x の根を求める。
        y = self.find(y)  # y の根を求める。
        if x == y:  # もともと同一の木なら何もしない。
            return
        if self.rank[x] < self.rank[y]:  # rank （木の高さ）の低いほうを高いほうに繋げたい。
            x, y = y, x
        self.parent[y] = x  # x の親を y にする。
        self.size_[x] += self.size_[y]
        if self.rank[x] == self.rank[y]:  # 同じ高さの木だったら片方の rank を1つ上げておく。
            self.rank[x] += 1

    def are_same(self, x, y):  # O(α(n)). log より高速。
        return self.find(x) == self.find(y)

    def size(self, x):  # O(α(n)). log より高速。
        return self.size_[self.find(x)]

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield [x for x, _ in group]


def main(): 
    N, M = LI()
    uf = UnionFind()
    for _ in range(M):
        X, Y, Z = LI()
        uf.unite(X, Y)
    for i in range(1, N+1):
        uf.unite(i,i)
    print(len(list(uf.grouper())))

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 roots(self):
   return [i for i, x in enumerate(self.parents) if x < 0]

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

import sys
input = sys.stdin.readline
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:
import numpy as np
from scipy.sparse import csr_matrix, csgraph
N, M = map(int, input().split())
print(csgraph.connected_components(csr_matrix(([1] * M, (np.array([tuple(map(lambda n: int(n) - 1, input().split()[:2])) for _ in range(M)], dtype=np.int32).T)), shape=(N, N), dtype=np.int32), return_labels=False))

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse import csr_matrix, csgraph
N, M = map(int, input().split())
row, column, _ = np.array([tuple(map(lambda n: int(n) - 1, input().split())) for _ in range(M)], dtype=np.int32).T
matrix = csr_matrix(([1] * M, (row, column)), shape=(N, N), dtype=np.int32)
print(csgraph.connected_components(matrix)[0])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
xy=[list(map(int,input().split())) for _ in range(m)]
ans=[1]*n
a=list(range(n))
def find(a, x):
    if a[x] != x:
        a[x] = find(a, a[x])
    return a[x]
 
 
def unite(a, x, y):
    x = find(a, x)
    y = find(a, y)
    if x != y:
        a[x] = min(x, y)
        a[y] = a[x]
 
for i,j ,k in xy:
    unite(a,i-1,j-1)
q=[]
for i in range(n):
    p=find(a,i)
    q.append(p)
print(len(set(q)))

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)


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

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

Submission status: Accepted

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

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

seen = [False] * (N+1)

last_start = -1
counter = 0
while True:
    start = last_start + 1
    while seen[start]:
        start += 1

    if start == N:
        break

    if path[start]:
        stack = [start]
        while stack:
            pos = stack.pop()
            seen[pos] = True
            for next_node in path[pos]:
                if not seen[next_node]:
                    stack.append(next_node)
    else:
        seen[start] = True

    counter += 1
    last_start = start

print(counter)

Submission status: Accepted

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

# # # # unionfind.py # # # #

# usage: uf = Unionfind(n) ; x = uf.root(y); uf.conn(a,b)

class Unionfind:

  def __init__(s,n):
    s.sz = [1] * n
    s.ances = [i for i in range(n)]

  def root(s,x):
    a = []
    y = x
    while s.ances[y] != y:
      a.append(y)
      y = s.ances[y]
    for z in a:
      s.ances[z] = y
    return y

  def conn(s,x,y):
    i = s.root(x)
    j = s.root(y)
    if i==j:
      return
    #k  = [i,j].min
    k  = j if (s.sz[i]<s.sz[j]) else i
    if k==j:
      s.ances[i] = j
    else:
      s.ances[j] = i
    s.sz[k] = s.sz[i] + s.sz[j]

# # # # end unionfind.py # # # #

n,m = inm()
uf = Unionfind(n+1)
for i in range(m):
    x,y,z = inm()
    uf.conn(x,y)
a = [0]*(n+1)
for i in range(1,n+1):
    a[uf.root(i)] = 1
print(sum(a))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.p = [-1]*n
        # union by rank
        self.r = [1]*n
 
    def find(self, x):
        if self.p[x] < 0:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]
 
    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
 
        if rx != ry:
            if self.r[rx] > self.r[ry]:
                rx, ry = ry, rx
            if self.r[rx] == self.r[ry]:
                self.r[ry] += 1
            self.p[ry] += self.p[rx]
            self.p[rx] = ry
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def count_member(self, x):
        return -self.p[self.find(x)]

n,m=map(int,input().split())
uf=UnionFind(n+1)
ans=n
for i in range(m):
  x,y,z=map(int,input().split())
  if not(uf.same(x,y)):
    uf.union(x,y)
    ans-=1
  uf.union(x,y)

print(ans)

Submission status: Accepted

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

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 roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]


def main():
    N, M = map(int, input().split())
    uni = UnionFind(N)
    for _ in range(M):
        X, Y, Z = map(int, input().split())
        X -= 1
        Y -= 1
        uni.union(X,Y)

    print(len(uni.roots()))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict,deque
input = sys.stdin.readline
N,M= map(int,input().split())
XYZ= [list(map(int,input().split())) for i in range(M)]
g = defaultdict(list)

for x,y,z in XYZ:
    g[x].append(y)
    g[y].append(x)

visited = [False] * (N+1)

connect = 0
for i in range(1,N+1):
    if visited[i]:
        continue
    connect += 1
    dq = deque([i])
    while dq:
        v = dq.pop()
        visited[v] = True
        for nv in g[v]:
            if visited[nv]:
                continue
            dq.append(nv)

print(connect)

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を見てくっつける方を決める
      #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())
#1 or 2がN枚
L=[]
uni=UnionFind(N)
for i in range(M):
  x,y,z=map(int, input().split())
  #Ax+Ay+Zが偶数
  #ZとAX+AY偶奇が一致
  uni.Unite(x-1,y-1)
  
root=[]
for i in range(N):
  root.append(uni.Find_Root(i))
  
print(len(set(root)))

Submission status: Accepted

Solution code:
import sys, collections, heapq
def input(): return sys.stdin.readline().strip()

class UnionFind():
    """
    https://note.nkmk.me/python-union-find/
    DFSの上位互換と考えて良い
    ２要素x, yがpath-connectedかどうかをlogオーダーで判定する（螺旋本の14.1節参照）
    さらに連結成分の要素数がO(1)で取得可能なように改造してある
    """
    def __init__(self, n):
        """
        要素数をnとして、各ノードを0,1,...,(n-1)の番号で管理する
        parentsは各ノードの属する木の根を表す
        ただし根ノードのparentには(その木のノード数)*(-1)を格納する
        """
        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のそれぞれ属する木Tx, Tyの根同士を繋ぐ
        このとき木の要素数が小さい方を大きい方に繋ぐ（rankではなくsizeを用いる）
        """
        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の属する木の要素数を返す
        根の親を要素数の(-1)倍で定めておいたおかげでO(1)で取得可能
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """
        xとyがpath-connectedかを判定する
        """
        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())



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

    """
    xが分かればyも分かるので、それを「頂点xと頂点yの間に辺がある」と解釈すれば
    求めるのはグラフの連結成分そのもの。よってUnionFindTreeで終わり。
    """

    tree = UnionFind(N)
    for x, y in hint:
        tree.union(x, y)
    print(tree.group_count())


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
tree=[[]for i in range(N)]
ischecked=[0]*N
ans=0
for i in range(M):
    X,Y,Z=map(int,input().split())
    tree[X-1].append(Y-1)
    tree[Y-1].append(X-1)
for i in range(N):
    if ischecked[i]==1:
        continue
    ischecked[i]=1
    q=tree[i]
    while q:
        a=q.pop()
        if ischecked[a]==1:
            continue
        ischecked[a]=1
        q.extend(tree[a])
    ans=ans+1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind(): #集合の取り扱い、辺に重み、階層を意識するときは使えない
    def __init__(self,n):
        self.n=n
        self.par = [-1]*n
    def find(self,x):
        if self.par[x] <0: #負なら親、要素数
            return x
        else: #正なら親の番号
            self.par[x]=self.find(self.par[x]) #一回調べたら根を繋ぎ変える、経路圧縮
            return self.par[x]
    def union(self,x,y):
        x=self.find(x) #x,yの親
        y=self.find(y)

        if x==y: #親が同じなら何もしない
            return 
        if self.par[x]>self.par[y]: #要素数が大きい方をxにする
            x,y=y,x
        self.par[x]+=self.par[y] #xがある集合にyが入った集合をくっつける
        self.par[y]=x

    def size(self,x):
        return -self.par[self.find(x)] #親のサイズ
    
    def same(self,x,y): #親が同じ、すなわち同じ集合か
        return self.find(x)==self.find(y)

    def member(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.par) if x<0]
    
    def group_count(self): #集合の数、木の数
        return len(self.roots())

    def all_member(self): #辞書型で返す
        return {r: self.member(r) for r in self.roots()}
    def __str__(self):
        return "\n".join('{}:{}'.format(r,self.member(r)) for r in self.roots)
n,m=map(int,input().split())
xyz = [list(map(int, input().split())) for _ in range(m)]
x, y ,z= [list(i) for i in zip(*xyz)]
uf = UnionFind(n)
for i in range(m):
    uf.union(x[i]-1,y[i]-1)
print(uf.group_count())

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

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

    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 find(self, x):          #親を出力
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def same(self, x, y):       #xとyが同じグループかどうか
        return self.find(x) == self.find(y)

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

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

################

def main():
    N, M = map(int, input().split())
    uf = UnionFind(N)
    rel = [list(map(int,input().split())) for i in range(M)]
    for i in rel:
        uf.union(i[0]-1, i[1]-1)

    print(uf.group_count())


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
#setrecursionlimit(10**5)
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納
        # par[x]=xの時そのノードは根　
        self.par = [i for i in range(n)]
        # rank
        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 check(self, x, y):
        # x,yが同じ集合に属するかどうか調べる
        return self.find(x) == self.find(y)


    def union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        # rankの小さいものを大きいほうにくっつける
        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 count_group(self):
        return len({self.find(x) for x in range(n)})

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

Submission status: Accepted

Solution code:
class UnionFind:
    N = 0
    cost = 0
    par = []
    group = 0
    
    def init(N):
        UnionFind.N = N
        UnionFind.group = N
        UnionFind.par = [i for i in range(N)]

    def find(v):
        c = 0
        u = v
        while v != UnionFind.par[v]:
            v = UnionFind.par[v]
            c += 1

        if c > 10:
            while u != v: u, UnionFind.par[u] = UnionFind.par[u], v

        return v

    def union(v, u, c=0):
        vr = UnionFind.find(v)
        ur = UnionFind.find(u)

        if vr == ur: return True

        UnionFind.par[ur] = vr
        UnionFind.cost += c
        UnionFind.group -= 1
        
        return False
            
    def get_cost():
        return UnionFind.cost

    def get_group():
        return UnionFind.group

    def same(v, u):
        return UnionFind.find(v) == UnionFind.find(u)

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

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

    UnionFind.union(x, y)

print(UnionFind.get_group())

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


class UF:
    def __init__(self, N):
        self.parent = [i for i in range(N)]
    
    def get_parent(self, a):
        p = self.parent[a]
        if a == p:
            return a
        
        q = self.get_parent(p)
        self.parent[a] = q
        return q

    def make_pair(self, a, b):
        pa = self.get_parent(a)
        pb = self.get_parent(b)
        if pa == pb:
            return
        
        self.parent[pa] = pb
        self.parent[a] = pb
    
    def is_pair(self, a, b):
        return self.get_parent(a) == self.get_parent(b)

    def num_group(self):
        return sum(1 for i, j in enumerate(self.parent) if i == j)


def main():
    N, M = read_values()
    uf = UF(N)
    
    for _ in range(M):
        X, Y, _ = read_index()
        uf.make_pair(X, Y)

    print(uf.num_group())


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

uf = UnionFind(N)
for i in range(M):
    X, Y, Z = map(int, input().split())
    uf.union(X-1, Y-1)
print(len(uf.roots()))

Submission status: Accepted

Solution code:
import copy
N,M = map(int,(input().split()))
x = [0]*M
y = [0]*M
z = [0]*M
line = [[] for _ in range(N+1)]
dot = []

for i in range(M):
    x[i],y[i],z[i] = map(int,(input().split()))
    line[x[i]].append(y[i])
    dot.append(x[i])
    dot.append(y[i])

class UnionFind:

    def __init__(self, n):
        self.par =  [-1] * n
        self.rank = [0] * n
    
    def root(self,x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

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

        if x == y:
            return
        else:
            if self.rank[x] <self.rank[y]:
                self.par[y] += self.par[x] # 負+負でsize管理 
                self.par[x] = y
            else:
                self.par[x] += self.par[y]
                self.par[y] = x
                if self.rank[x] == self.rank[y]: # 負+負でsize管理 
                    self.rank[x] += 1
    
    def is_same(self, x, y):
        return self.root(x) == self.root(y)

    def size(self, x):
        return -self.par[self.root(x)]

Tree = UnionFind(N)

for i in range(N):
    for j in line[i]:
        Tree.union(i-1,j-1)

nohint = 0
hint = []
for i in range(N):
    if Tree.size(i) == 1:
        nohint += 1
    else:
        hint.append(Tree.root(i))

print(nohint + len(set(hint)))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    #mod = 10**9 + 7

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

    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)]
    
    #全ての根の要素を返す
    def roots():
        return [i for i, x in enumerate(par) if x < 0]
    
    par = [-1]*n

    for x,y,z in xyz:
        if same(x-1, y-1):
            continue
        unite(x-1, y-1)

    res = len(roots())
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

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

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

    def get_n_groups(self):
        return len(self.get_parent_list())


def main():
    N, M = map(int, input().split())
    tree = UnionFind(N)
    for _ in range(M):
        x, y, z = map(int, input().split())
        x -= 1
        y -= 1
        tree.unite(x, y)
    n_groups = tree.get_n_groups()
    print(n_groups)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict


def input():
    return sys.stdin.readline().strip()


class UnionFind:
    def __init__(self, n_nodes):
        self.n_nodes = n_nodes
        self.parent = [i for i in range(n_nodes)]
        self.rank = [1] * n_nodes
        self.size = [1] * n_nodes

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] > self.rank[y]:
            self.parent[y] = x
            self.size[x] += self.size[y]
        else:
            self.parent[x] = y
            self.size[y] += self.size[x]
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

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

    def get_parent_list(self):
        return [i for i in range(self.n_nodes) if self.find(i) == i]

    def get_n_groups(self):
        return len(self.get_parent_list())

    def get_members(self, x):
        parent = self.find(x)
        return [i for i in range(self.n_nodes) if self.find(i) == parent]

    def get_members_dict(self):
        return {par: self.get_members(par) for par in self.get_parent_list()}


def main():
    N, M = map(int, input().split())
    UF = UnionFind(N)
    for _ in range(M):
        X, Y, Z = map(int, input().split())
        UF.unite(X - 1, Y - 1)
    print(UF.get_n_groups())


if __name__ == "__main__":
    main()