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

rl = sys.stdin.readline


class UnionFind:
    def __init__(self, n: int):
        self.n = n
        self.parents = [-1] * n
    
    def find(self, x: int):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x: int, y: int):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        if self.parents[y] < self.parents[x]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x: int):
        return -self.parents[self.find(x)]
    
    def same(self, x: int, y: int):
        return self.find(x) == self.find(y)
    
    def members(self, x: int):
        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 solve():
    N, M = map(int, rl().split())
    uf = UnionFind(N)
    for _ in range(M):
        x, y, _ = map(lambda z: int(z) - 1, rl().split())
        uf.union(x, y)
    print(uf.group_count())


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys


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

    def find(self, x):
        if self.par[x] != x:
            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 is_same_group(self, x, y):
        return self.find(x) == self.find(y)

    def get_group_num(self):
        return sum([1 if self.par[i] == i else 0 for i in range(len(self.par))])


N, M = map(int, sys.stdin.readline().split())
uf = UnionFind(N)
for _ in range(M):
    x, y, z = map(int, sys.stdin.readline().split())
    x -= 1
    y -= 1
    uf.unite(x, y)

print(uf.get_group_num())

Submission status: Accepted

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

import sys
sys.setrecursionlimit(10**5)

def main():
  n, m = map(int, input().split())
  luf = [-1] * (n+1)
  
  def find(x):
    if luf[x] < 0:
      return x
    else:
      luf[x] = find(luf[x])
      return luf[x]
  
  def union(x, y):
    px, py = find(x), find(y)
    if px == py:
      return
    if px < py:
      px, py = py, px
    luf[px] += luf[py]
    luf[py] = px
  
  for _ in range(m):
    x, y, z = map(int, input().split())
    union(x, y)
#   print(luf)
  print(sum([x<0 for x in luf[1:]]))

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
par = [i for i in range(N)]
rank = [0 for i in range(N)]
def root(x):
  if par[x] == x:
    return x
  else:
    par[x] = root(par[x])
    return par[x]
def unite(x, y):
  x, y = root(x), root(y)
  if x != y:
    if rank[x] < rank[y]:
      par[x] = y
    else:
      par[y] = x
      if rank[x] == rank[y]:
        rank[x] += 1

for i in range(M):
  X, Y, Z = map(int, input().split())
  unite(X-1, Y-1)
for i in range(N):
  root(i)
print(len(set(par)))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
par=[-1]*n
def find(x):
    if par[x]<0:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def union(x,y):
    x,y=find(x),find(y)
    if x!=y:
        if x>y:
            x,y=y,x
        par[x]+=par[y]
        par[y]=x

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

ans=0
for i in range(n):
    if par[i]<0:
        ans+=1
        n+=par[i]
print(ans+n)

Submission status: Accepted

Solution code:
from collections import defaultdict
n, m = map(int, input().split())
friends_of = defaultdict(list)#[[] for _ in range(m)]
for _ in range(m):
    x, y, _ = map(int, input().split())
    friends_of[x - 1].append(y - 1)
    friends_of[y - 1].append(x - 1)
ans = 0
visited = [False] * n
for i in range(n):
    if not visited[i]:
        ans += 1
        stack = [i]
        while len(stack) != 0:
            popped = stack.pop()
            visited[popped] = True
            for friend in friends_of[popped]:
                if not visited[friend]:
                    stack.append(friend)
print(ans)

Submission status: Accepted

Solution code:
# https://www.planeta.tokyo/entry/6193/
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]  # 親
        self.rank = [1] * n  # 木の高さ
        self.size = [1] * n  # size[i] は i を根とするグループのサイズ

    def find(self, x):  # 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, y の属する集合を併合する
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

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

    def group_size(self, x):  # x が属する集合の大きさを返す
        return self.size[self.find(x)]

    def group_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.parent) if i == x]

    def group_count(self):  # 木の数を返す
        return len(self.roots())

    def all_group_members(self):  # すべての木の要素を辞書で返す
        return {r: self.group_members(r) for r in self.roots()}

    def __str__(self):  # print 表示用
        return '\n'.join('{}: {}'.format(r, self.group_members(r)) for r in self.roots())

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

Submission status: Accepted

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

    def root(self, x):
        if x != self.par[x]:
            self.par[x] = self.root(self.par[x])
        return self.par[x]

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

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return

        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
        else:
            self.par[ry] = rx
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    def update_p(self):
        for x in range(self.n):
            self.root(x)

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




def main():
    n, m = [int(i) for i in input().split()]
    uf = UnionFind(n)
    for _ in range(m):
        x, y, _ = [int(i) for i in input().split()]
        uf.unite(x-1, y-1)
    uf.update_p()
    print(len(set(uf.par)))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = [ -1 for _ in range(n) ]
        self._size = n

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            if self.parent[y] < self.parent[x]:
                x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x
            self._size -= 1

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

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

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


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

uf_tree = UnionFind(N)
for _ in range(M):
    X, Y, Z = map(int, input().split())
    X -= 1; Y -= 1;
    uf_tree.unite(X, Y)

print(uf_tree._size)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = [ -1 for _ in range(n) ]
        self._size = n

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            if self.parent[y] < self.parent[x]:
                x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x
            self._size -= 1

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

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

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


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

uf_tree = UnionFind(N)
for _ in range(M):
    X, Y, Z = map(int, input().split())
    X -= 1; Y -= 1;
    uf_tree.unite(X, Y)

print(uf_tree._size)

Submission status: Accepted

Solution code:
import sys

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)

for _ 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:
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())


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

for _ 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:
N, M = map(int, input().split())
par = [i for i in range(N+1)]
h = [1 for _ in range(N+1)]

def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]

def unite(x,y):
    rx = root(x)
    ry = root(y)
    if h[rx] < h[ry]:
        rx, ry = ry, rx
    h[rx] += h[ry]
    par[ry] = rx

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

for i in range(1,N+1):
    par[i] = root(i)

print(len(set(par[1:])))

Submission status: Accepted

Solution code:
# import bisect
# from collections import Counter, deque
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)

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

def main():
    n, m = list(map(int,ipti().split()))
    uf = UnionFind(n)
    grouped_set = set()

    for i in range(m):
        x, y, z = list(map(int,ipti().split()))
        x ,y = x - 1, y - 1
        uf.union(x,y)
        grouped_set.add(x)
        grouped_set.add(y)

    print(uf.group_count())

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.p = [e for e in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    def same(self, u, v):
        return self.find_set(u) == self.find_set(v)

    def unite(self, u, v):
        u = self.find_set(u)
        v = self.find_set(v)

        if u == v:
            return

        if self.rank[u] > self.rank[v]:
            self.p[v] = u
            self.size[u] += self.size[v]
        else:
            self.p[u] = v
            self.size[v] += self.size[u]
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1

    def find_set(self, u):
        if u != self.p[u]:
            self.p[u] = self.find_set(self.p[u])

        return self.p[u]

    def update_p(self):
        for u in range(self.n):
            self.find_set(u)

    def get_size(self, u):
        return self.size[self.find_set(u)]


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

uf = UnionFind(n)

for x, y, _ in xyz:
    x -= 1
    y -= 1
    uf.unite(x, y)

uf.update_p()
ans = len(set(uf.p))
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())  
par=[i for i in range(N)]
rank=[0]*(N)
def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
    return par[x]

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

def union(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return 
  if rank[x]>rank[y]:
    par[y]=x
  else:
    par[x]=y
    if rank[x]==rank[y]:
      rank[y]+=1

for i in range(M):
  a,b,c=map(int,input().split())
  a-=1
  b-=1
  union(a,b)

cnt=0
for i in range(N):
  if i==par[i]:
    cnt+=1
print(cnt)

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
        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.size(x) < self.size(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)]


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.union(x, y)

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

print(len(s))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
par = [i for i in range(n)]
rank = [0 for i in range(n)]

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

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

T = list(set(par))
print(len(T))

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())
    uf.union(X-1, Y-1)

print(uf.group_count())

Submission status: Accepted

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

# scipy version

import sys
from collections import deque
from array import array

import numpy

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components

def input():
    return sys.stdin.readline().rstrip('\n')

##### main

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

#C = [[0]*N for _ in range(N)]
#
#for i in range(M):
#    a,b,c = list(map(int, input().split()))
#    C[a-1][b-1] = c

R = numpy.full(M, 0, dtype=numpy.int32)
C = numpy.full(M, 0, dtype=numpy.int32)
V = numpy.full(M, 0, dtype=numpy.int32)

for i in range(M):
    r,c,v = list(map(int, input().split()))
    R[i] = r-1
    C[i] = c-1
    V[i] = v

matrix = csr_matrix((V,(R,C)), shape=(N,N))

n = connected_components(matrix, directed=False, return_labels=False)

print(n)

Submission status: Accepted

Solution code:
def get_root(s):
    if s != root[s]:
        root[s] = get_root(root[s])
        return root[s]
    return s

def unite(s, t):
    global ans
    root_s = get_root(s)
    root_t = get_root(t)
    if not root_s == root_t:
        ans -= 1
        if rank[s] == rank[t]:
            root[root_t] = root_s
            rank[root_s] += 1
        elif rank[s] > rank[t]:
            root[root_t] = root_s
        else:
            root[root_s] = root_t

n, m = map(int, input().split())
root = [i for i in range(n)]
rank = [1 for _ in range(n)]
ans = n
for _ in range(m):
    x, y, z = map(int, input().split())
    unite(x - 1, y - 1)
print(ans)

Submission status: Accepted

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

    def find(self, x):
        root = x
        while self.parents[root] != root:
            root = self.parents[root]
        while self.parents[x] != root:
            parent = self.parents[x]
            self.parents[x] = root
            x = parent
        return root

    def unite(self, x, y):
        xroot = self.find(x)
        yroot = self.find(y)
        if xroot == yroot:
            return
        xrank = self.rank[xroot]
        yrank = self.rank[yroot]
        if xrank < yrank:
            self.parents[xroot] = yroot
            self.size[yroot] += self.size[xroot]
        elif xrank == yrank:
            self.parents[yroot] = xroot
            self.rank[yroot] += 1
            self.size[xroot] += self.size[yroot]
        else:
            self.parents[yroot] = xroot
            self.size[xroot] += self.size[yroot]

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

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(len([i for i in range(N) if uf.rank[i] == 0]))

Submission status: Accepted

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

    def find(self, x):
        root = x
        while self.parents[root] != root:
            root = self.parents[root]
        while self.parents[x] != root:
            parent = self.parents[x]
            self.parents[x] = root
            x = parent
        return root

    def unite(self, x, y):
        xroot = self.find(x)
        yroot = self.find(y)
        if xroot == yroot:
            return
        xrank = self.rank[xroot]
        yrank = self.rank[yroot]
        if xrank < yrank:
            self.parents[xroot] = yroot
            self.size[yroot] += self.size[xroot]
        elif xrank == yrank:
            self.parents[yroot] = xroot
            self.rank[yroot] += 1
            self.size[xroot] += self.size[yroot]
        else:
            self.parents[yroot] = xroot
            self.size[xroot] += self.size[yroot]

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

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(len(set([uf.find(i) for i in range(N)])))

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
t = [[] for _ in range(N)]
visited = [0] * N
for _ in range(M):
    X, Y, Z = map(int,input().split())
    X -= 1
    Y -= 1
    t[X].append(Y)
    t[Y].append(X)
ans = 0
for i in range(N):
    if visited[i]:
        continue
    ans += 1
    stack = [i]
    while stack:
        s = stack.pop()
        for to in t[s]:
            if visited[to]:
                continue
            visited[to] = 1
            stack.append(to)
print(ans)

Submission status: Accepted

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

def dfs(s):
    if visited[s]:
        return
    visited[s] = 1
    for to in t[s]:
        if visited[to]:
            continue
        dfs(to)
    
N, M = map(int,input().split())
t = [[] for _ in range(N)]
visited = [0] * N
for _ in range(M):
    X, Y, Z = map(int,input().split())
    X -= 1
    Y -= 1
    t[X].append(Y)
    t[Y].append(X)
ans = 0
for i in range(0, N):
    if visited[i]:
        continue
    ans += 1
    dfs(i)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
e = [[] for i in range(n)]
l = [-1]*n
for i in range(m):
    a,b,c = map(int,input().split())
    e[a-1].append(b-1)
    e[b-1].append(a-1)

def dfs(x,count):
    l[x] = count
    q = deque([])
    q.append(x)
    while q:
        bef = q.popleft()
        for nex in e[bef]:
            if l[nex] == -1:
                l[nex] = count
                q.append(nex)
count = 0
for i in range(n):
    if l[i] == -1 and e[i]:
        dfs(i,count)
        count += 1
print(count+l.count(-1))

Submission status: Accepted

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components

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

xs = []
ys = []
for x, y, _ in xyz:
    x -= 1
    y -= 1
    xs.append(x)
    ys.append(y)

graph = csr_matrix(([1] * m, (xs, ys)), shape=(n, n))
num = connected_components(graph, connection="weak", return_labels=False)
print(num)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.p = [e for e in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    def same(self, u, v):
        return self.find_set(u) == self.find_set(v)

    def unite(self, u, v):
        u = self.find_set(u)
        v = self.find_set(v)

        if u == v:
            return

        if self.rank[u] > self.rank[v]:
            self.p[v] = u
            self.size[u] += self.size[v]
        else:
            self.p[u] = v
            self.size[v] += self.size[u]
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1

    def find_set(self, u):
        if u != self.p[u]:
            self.p[u] = self.find_set(self.p[u])

        return self.p[u]

    def update_p(self):
        for u in range(self.n):
            self.find_set(u)

    def get_size(self, u):
        return self.size[self.find_set(u)]


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

uf = UnionFind(n)

for x, y, _ in xyz:
    x -= 1
    y -= 1
    uf.unite(x, y)

uf.update_p()
ans = len(set(uf.p))
print(ans)

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())
tree = UnionFind(n)
for _ in range(m):
    x,y,z=map(int,input().split())
    tree.union(x-1,y-1)
print(tree.group_count())

Submission status: Accepted

Solution code:
class UnionFindBySize():
    def __init__(self, n):
        self.parents = list(range(n+1))
        self.size = [1] * (n+1)

    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    # 根が同一かどうかを判定する
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

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

        if x == y:
            return

        if self.size[x] < self.size[y]:
            self.size[y] += self.size[x]
            self.parents[x] = y
        else:
            self.size[x] += self.size[y]
            self.parents[y] = x

n, m = map(int, input().split())
XY_dict = {x:[] for x in range(1, n+1)}
XYZ = []
UF = UnionFindBySize(n)

for _ in range(m):
    x, y, z = map(int, input().split())
    XY_dict[x].append(y)
    XY_dict[y].append(x)
    XYZ.append([x,y,z])

for ab in XYZ:
    a = ab[0]
    b = ab[1]
    UF.union(a,b)

Parents = UF.parents
ans = 0

for i in range(1, n+1):
    if i == Parents[i]:
        ans += 1
print(ans)

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


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