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:
#最大公約数
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

#最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

#エストラテネスの篩
def isPrime():
    MAX = 10**5
    is_prime = [1] * (MAX+1)
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, MAX+1):
        if is_prime[i]:
            for j in range(i*2, MAX+1, i):
                is_prime[j] = 0
    return is_prime

#約数を求める
def makeDivisor(n):
    divisors = []
    for i in range(1, int(n ** 0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

#素因数分解（試し割り法）
def makePrime(n):
    factor = []
    tmp = int(n ** 0.5) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            factor.append(num)

    if n > 1:
        factor.append(n)

    return factor

#繰り返し２乗法
def modPow(a, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        halfP = p // 2
        half = modPow(a, halfP)
        return half * half % mod
    else:
        return a * modPow(a, p-1) % mod

#組み合わせ
def comb(a, b):
    if b > a - b:
        return comb(a, a-b)
    ansMul = 1
    ansDiv = 1
    for i in range(b):
        ansMul *= a - i
        ansDiv *= i + 1
        ansMul %= mod
        ansDiv %= mod

    ans = ansMul * modPow(ansDiv, mod-2) % mod
    return ans

#UnionFind
class UnionFind():

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

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

    def Unite(self, x, y):
        x = self.FindRoot(x)
        y = self.FindRoot(y)

        if x == y:
            return False
        if self.Size(x) < self.Size(y):
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x

        return True

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

    def Size(self, x):
        return -self.root[self.FindRoot(x)]

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

Uni = UnionFind(N)

for i in range(M):
    Uni.Unite(X[i], Y[i])

roots = set()
for i in range(1, N+1):
    roots.add(Uni.FindRoot(i))

print(len(roots))

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n + 1)
    
    def root(self, x):
        if self.par[x] == x:
            return 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 union(self, x, y):
        x = self.root(x)
        y = self.root(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


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

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

ans = 0
for i in range(N+1):
    if uf.par[i] == i:
        ans += 1

print(ans - 1)

Submission status: Accepted

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


class UnionFindNode(object):
    """
    Union-Find構造
    ノードのグループ併合や、所属グループ判定を高速に処理する
    """

    def __init__(self, group_id, parent=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.size_ = 1
        self.rank_ = 1

    def __str__(self):
        template = "UnionFindNode(group_id: {}, \n\tparent: {}, size: {}, rank: {})"
        return template.format(self.group_id_, self.parent_, self.size_,
                               self.rank_)

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        root = self.root()
        return root.group_id_

    def rank(self):
        root = self.root()
        return root.rank_

    def get_size(self):
        root = self.root()
        return root.size_

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

        if root.group_id_ != unite_root.group_id_:
            if root.rank() > unite_root.rank():
                unite_root.parent_ = root
                root.rank_ = max(root.rank_, unite_root.rank_ + 1)
                root.size_ += unite_root.size_

            else:
                root.parent_ = unite_root
                unite_root.rank_ = max(root.rank_ + 1, unite_root.rank_)
                unite_root.size_ += root.size_


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

node_array = [UnionFindNode(i) for i in range(N)]

for i in range(M):
    x, y, z = map(int, input().split())
    node_array[(x - 1)].unite(node_array[(y - 1)])

parent = set()

for node in node_array:
    parent.add(node.find())

print(len(parent))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

#   木の根を求める
	def root(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.root(self.par[x])
			return self.par[x]


#   x を含むグループと y を含むグループをマージする
	def merge(self, x, y):
		x = self.root(x)
		y = self.root(y)
		if x == y:
			return
		self.par[x] = y

if __name__ == '__main__':
	N, M = map(int, input().split())
	uf = UnionFind(N)
	for i in range(M):
		X, Y, Z = map(int, input().split())
		uf.merge(X-1, Y-1)
	
	ans = [ uf.root(i) for i in range(N)]

	print(len(set(ans)))

Submission status: Accepted

Solution code:
import sys


sys.setrecursionlimit(10**5)


class UnionFind(object):
    def __init__(self, N):
        self.parent = [i for i in range(N)]

    def merge(self, a, b):
        pa = self.root(a)
        pb = self.root(b)
        self.parent[pa] = pb
    
    def root(self, x):
        p = self.parent[x]
        if p == x:
            return x
        else:
            r = self.root(p)
            self.parent[x] = r
            return r


def main():
    N, M = map(int, input().split())

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

    print(len(list(filter(lambda x: x == uf.root(x), range(N)))))


main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
edge=[list(map(int,input().split())) for i in range(M)]
c=[[] for i in range(N)]
for i,j,w in edge:
    c[i-1].append(j-1)
    c[j-1].append(i-1)
a=0
v=[0]*N
import sys
sys.setrecursionlimit(10**6)
def dfs(c,v,p):
    v[p]=1
    for n in c[p]:
        if v[n]==0:
            dfs(c,v,n)
for i in range(N):
    if v[i]==1:
        continue
    dfs(c,v,i)
    a+=1
print(a)

Submission status: Accepted

Solution code:
class uf_tree():

    def __init__(self,n):
        self.n = n
        self.par = [i for i in range(n)]

    def indep(self):
        dep =0
        for i in range(self.n):
            if i == self.par[i]:
                dep += 1

        return dep

    def unite(self,child,mas):
        if self.root(child) == self.root(mas):
            return
        else:
            self.par[self.root(child)] = self.root(mas)

    def root(self,i):
        if self.par[i] == i:
            return i
        else:
            self.par[i] = self.root(self.par[i])
            return self.par[i]

    def same(self,x,y):
        if self.root(x) == self.root(y):
            return True
        else:
            return False



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

print(uf.indep()-1)

Submission status: Accepted

Solution code:
# using main() makes code faster from the point of view of "access to variables in global name-space"
# def main():

""" convenient functions
# for i, a in enumerate(iterable)
# q, mod = divmod(a, b)
# divmod(x, y) returns the tuple (x//y, x%y)
# manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
"""

import sys
sys.setrecursionlimit(10**7)
from itertools import accumulate, combinations, permutations, product # https://docs.python.org/ja/3/library/itertools.html
# accumulate() returns iterator! to get list: list(accumulate())
from math import factorial, ceil, floor
def factorize(n):
    """return the factors of the Arg and count of each factor
    
    Args:
        n (long): number to be resolved into factors
    
    Returns:
        list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
    """
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
def combinations_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    # TODO: How should I do when n - r is negative?
    if n < 0 or r < 0:
        raise Exception('combinations_count(n, r) not defined when n or r is negative')
    if n - r < r: r = n - r
    if r < 0: return 0
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combinations_with_replacement_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    if n < 0 or r < 0:
        raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
    elif n == 0:
        return 1
    else:
        return combinations_count(n + r - 1, r)
from bisect import bisect_left, bisect_right
from collections import deque, Counter, defaultdict # https://docs.python.org/ja/3/library/collections.html#collections.deque
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
from operator import itemgetter
# ex1: List.sort(key=itemgetter(1))
# ex2: sorted(tuples, key=itemgetter(1,2))
from functools import reduce
def chmin(x, y):
    """change minimum
    if x > y, x = y and return (x, True).
    convenient when solving problems of dp[i]
    
    Args:
        x (long): current minimum value
        y (long): potential minimum value
    
    Returns:
        (x, bool): (x, True) when updated, else (x, False)
    """
    if x > y:
        x = y
        return (x, True)
    else:
        return (x, False)
def chmax(x, y):
    """change maximum
    if x < y, x = y and return (x, True).
    convenient when solving problems of dp[i]
    
    Args:
        x (long): current maximum value
        y (long): potential maximum value
    
    Returns:
        (x, bool): (x, True) when updated, else (x, False)
    """
    if x < y:
        x = y
        return (x, True)
    else:
        return (x, False)

from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)

# first create factorial_list
# fac_list = mod_factorial_list(n)
INF = 10 ** 18
MOD = 10 ** 9 + 7
modpow = lambda a, n, p = MOD: pow(a, n, p) # Recursive function in python is slow!
def modinv(a, p = MOD):
    # evaluate reciprocal using Fermat's little theorem:
    # a**(p-1) is identical to 1 (mod p) when a and p is coprime
    return modpow(a, p-2, p)
def modinv_list(n, p = MOD):
    if n <= 1:
        return [0,1][:n+1]
    else:
        inv_t = [0,1]
        for i in range(2, n+1):
            inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
        return inv_t
def modfactorial_list(n, p = MOD):
    if n == 0:
        return [1]
    else:
        l = [0] * (n+1)
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l[i] = tmp
        return l
def modcomb(n, k, fac_list = [], p = MOD):
    # fac_list = modfactorial_list(100)
    # print(modcomb(100, 5, modfactorial_list(100)))
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if len(fac_list) <= n:
        a = factorial(n) % p
        b = factorial(k) % p
        c = factorial(n-k) % p
    else:
        a = fac_list[n]
        b = fac_list[k]
        c = fac_list[n-k]
    return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
def modadd(a, b, p = MOD):
    return (a + b) % MOD
def modsub(a, b, p = MOD):
    return (a - b) % p
def modmul(a, b, p = MOD):
    return ((a % p) * (b % p)) % p
def moddiv(a, b, p = MOD):
    return modmul(a, modpow(b, p-2, p))

""" initialize variables and set inputs
# initialize variables
    # to initialize list, use [0] * n
    # to initialize two dimentional array, use [[0] * N for _ in range(N)]
# set inputs
    # open(0).read() is a convenient method:
    # ex) n, m, *x = map(int, open(0).read().split())
    #     min(x[::2]) - max(x[1::2])
    # ex2) *x, = map(int, open(0).read().split())
    #     don't forget to add comma after *x if only one variable is used
# preprocessing
    # transpose = [x for x in zip(*data)]
    # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [(1, 4, 7), (2, 5, 8), (3, 6, 9)]
    # flat = [flatten for inner in data for flatten in inner]
    # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [1, 2, 3, 4, 5, 6, 7, 8, 9]
# calculate and output
    # output pattern
    # ex1) print(*l) => when l = [2, 5, 6], printed 2 5 6
"""

# functions used
r = lambda: sys.stdin.readline().strip()
r_int = lambda: int(r())
R = lambda: list(map(int, r().split()))
Rfloat = lambda: list(map(float, r().split()))
Rtuple = lambda: tuple(map(int, r().split()))
Rmap = lambda: map(int, r().split())

""" how to treat input
# single int: int(r())
# single string: r()
# single float: float(r())
# line int: R()
# line string: r().split()
# line (str, int, int): [j if i == 0 else int(j) for i, j in enumerate(r().split())]
# lines int: [R() for _ in range(n)]
"""

# for test
# sys.stdin = open('sample.txt') 

# main
N, M = R()
Dic = defaultdict(list)
for _ in range(M):
    x, y, _ = R()
    x -= 1
    y -= 1
    Dic[x].append(y)
    Dic[y].append(x)

arrived = [0] * N
task = []
ans = 0
for i in range(N):
    if arrived[i] == 0:
        arrived[i] = 1
        task.extend(Dic[i])
        ans += 1
    while task:
        s = task.pop()
        if arrived[s]:
            continue
        else:
            arrived[s] = 1
            task.extend(Dic[s])
print(ans)

"""memo: how to use defaultdict of list
# initialize
Dic = defaultdict(list)
# append / extend
Dic[x].append(y)
# for
for k, v in Dic.items():
"""

# if __name__ == '__main__':
#     main()

Submission status: Accepted

Solution code:
class UnionFind():
    '''UnionFind木'''

    def __init__(self, n):
        self.data = [-1] * n

    def unite(self, x, y):
        '''x と y を結合'''
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.data[x] < self.data[y]:
            x, y = y, x  # swap
        self.data[x] += self.data[y]
        self.data[y] = x

    def find(self, x):
        '''ノード x の親を返す'''
        if self.data[x] < 0:
            return x
        self.data[x] = self.find(self.data[x])
        return self.data[x]

    def same(self, x, y):
        '''x と y が同じグループに属するか判定'''
        return self.find(x) == self.find(y)

    def size(self, x):
        '''x を含むグループのノード数を返す'''
        return self.data[self.find(x)]
    def indep(self):
        dep = 0
        for i in range(len(self.data)):
            if self.data[i] < 0:
                dep += 1
        return dep


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

print(uf.indep()-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#abc126 e

import sys
sys.setrecursionlimit(1000000)
N,M = list(map(int,input().split()))
XYZ = [list(map(int,input().split())) for _ in range(M)]

G = [[] for _ in range(N)]

for i in XYZ:
    G[i[0]-1].append(i[1])
    G[i[1]-1].append(i[0])

check = [False for _ in range(N)]#各頂点を訪問したかどうか

def DFS(G,s):
    check[s-1] = True
    for i in G[s-1]:
        if not check[i-1]:
            DFS(G,i)
ans = 0
for i in range(N):
    if not check[i]:
        DFS(G,i+1)
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template

# PyPyだと再帰が遅いので注意
# BEGIN CUT HERE
sys.setrecursionlimit(100000)
class UnionFind():
    '''UnionFind木'''
    def __init__(self,n):
        self.data = [-1] * n
    
    def unite(self, x, y):
        '''x と y を結合'''
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.data[x] < self.data[y]:
            x, y = y, x  # swap
        self.data[x] += self.data[y]
        self.data[y] = x
    
    def find(self, x):
        '''ノード x の親を返す'''
        if self.data[x] < 0:
            return x
        self.data[x] = self.find(self.data[x])
        return self.data[x]

    def same(self, x, y):
        '''x と y が同じグループに属するか判定'''
        return self.find(x) == self.find(y)
    
    def size(self, x):
        '''x を含むグループのノード数を返す'''
        return self.data[self.find(x)]
        
# END CUT HERE

def ABC120_D():
    n, m = mi()
    a = [0] * m
    b = [0] * m
    for i in range(m):
        a[i], b[i] = mi()
        
    uf = UnionFind(n)
    ans = [0] * (m + 1)
    ans[m] = n * (n - 1) // 2

    for i in range(m - 1, -1, -1):
        a[i] -= 1
        b[i] -= 1
        ans[i] = ans[i + 1]
        if uf.same(a[i], b[i]):
            continue
        
        x = uf.size(a[i])
        y = uf.size(b[i])
        ans[i] -= x * y
        
        uf.unite(a[i],b[i])
    
    for i in range(1, m + 1):
        print(ans[i])

# verified on 2019/06/23
# Python3:616ms https://atcoder.jp/contests/abc120/submissions/6094323

def ABC126_E():
    N, M = mi()
    uf = UnionFind(N)
    for i in range(M):
        _X, _Y, _Z = mi()
        uf.unite(_X - 1, _Y - 1)
    ans = 0
    for i in range(N):
        if uf.find(i) == i:
            ans += 1
    print(ans)


if __name__ == '__main__':
    # ABC120_D()
    ABC126_E()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,size):
        self.par = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]
        
    def find(self,x):
        if self.par[x]==x:
            return x
        else:
            self.par[x]=self.find(self.par[x])
            return self.par[x]
    
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x]>self.rank[y]:
            self.par[y]=x
        else:
            self.par[x]=y
            if self.rank[x]==self.rank[y]:
                self.rank[y]+=1
    
    def same(self,x,y):
        x = self.find(x)
        y = self.find(y)
        return x==y
    
n,m = map(int,input().split())
tree = UnionFind(n)
for i in range(m):
    x,y,z = map(int,input().split())
    x -= 1
    y -= 1
    tree.union(x,y)

tmp = [tree.find(i) for i in range(n)]
print(len(set(tmp)))

Submission status: Accepted

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


def dsMakeSet(ds, x):
    ds[x] = x


def dsFind(ds, x):
    if ds[x] == x:
        return x

    x0 = x
    while ds[x] != x:
        x = ds[x]

    ds[x0] = x
    return x


def dsUnion(ds, x, y):
    xRoot = dsFind(ds, x)
    yRoot = dsFind(ds, y)
    
    if xRoot != yRoot:
        ds[yRoot] = xRoot
        return True

    return False


def main():
    N, M = map(int, input().split())
    ds = {}

    for i in range(N):
        dsMakeSet(ds, i+1)

    n = 0
    for i in range(M):
        X,Y,Z = map(int, input().split())
        if dsUnion(ds, X, Y):
            n += 1
        
    print(N - n)
        

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import bisect
from collections import defaultdict
import math

def main():
    N, M = map(int, input().split())

    clusters = []
    index = {}
    for _ in range(M):
        x, y, z = map(int, input().split())
        if x in index and y in index:
            cx = index[x]
            cy = index[y]
            if cx != cy:
                for a in clusters[cy]:
                    index[a] = cx
                    clusters[cx].add(a)
                clusters[cy] = None
        else:
            for a, b in [(x, y), (y, x)]:
                if a in index:
                    c = index[a]
                    index[b] = c
                    clusters[c].add(b)

            if not x in index and not y in index:
                new_c = len(clusters)
                for a in [x, y]:
                    index[a] = new_c
                clusters.append(set([x, y]))

    num = N - len(index) + len([c for c in clusters if c])
    print(num)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
root=[-1]*N
def find(i):
    global root
    if root[i]>=0:
        root[i]=find(root[i])
        return root[i]
    return i
for i in range(M):
    X,Y,Z=map(int,input().split())
    rx=find(X-1)
    ry=find(Y-1)
    if rx==ry:
        continue
    elif root[rx]<=root[ry]:
        root[rx]+=root[ry]
        root[ry]=rx
    elif root[rx]>root[ry]:
        root[ry]+=root[rx]
        root[rx]=ry
ans=0
for r in root:
    if r<0:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:

from collections import deque

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

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

vertices = [False] * N

count = 0
d = deque()
for i in range(N):
    if vertices[i] == False:
        vertices[i] = True
        count += 1
        d.append(i)
        while len(d) > 0:
            v = d.popleft()
            for p in edges[v]:
                if vertices[p] == False:
                    d.append(p)
                    vertices[p] = True
                

print(count)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.v = [-1 for _ in range(n)]  # 根(負): 連結頂点数 * (-1) / 子(正): 根の頂点番号(0-indexed)

    def find(self, x):  # xを含む木における根の頂点番号を返す
        if self.v[x] < 0:  # (負)は根
            return x
        else:  # 根の頂点番号
            self.v[x] = self.find(self.v[x])  # uniteでは, 旧根に属する頂点の根が旧根のままなので更新
            return self.v[x]

    def unite(self, x, y):  # 違う根に属していたらrankが低くなるように連結
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if -self.v[x] < -self.v[y]:  # size比較, 　(-1) * (連結頂点数 * (-1)), (正)同士の大小比較
            x, y = y, x  # 連結頂点数が少ない方をyにすると, findでの更新回数が減る？
        self.v[x] += self.v[y]  # 連結頂点数の和を取る, 連結頂点数 * (-1)
        self.v[y] = x  # 連結頂点数が少ないy(引数yの根の頂点番号)の根をx(引数xの根の頂点番号)にする

    def root(self, x):
        return self.v[x] < 0  # (負)は根

    def same(self, x, y):
        return self.find(x) == self.find(y)  # 同じ根に属するか

    def size(self, x):
        return -self.v[self.find(x)]  # 連結頂点数を返す


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

ans = sum(1 for i in range(N) if uf.root(i))
print(ans)

Submission status: Accepted

Solution code:
import sys
inputs = sys.stdin.readline
N, M = map(int,inputs().split())
K = [None]*M
for t in range(M):
	x, y, z = map(int,inputs().split())
	K[t] = (x, y)
c = 0

U = [0]*(N+1)

for k in K:
	if U[k[0]] and U[k[1]]:
		a = U[k[0]]
		b = U[k[1]]
		while(U[a] != a ):
			a = U[a]
		while(U[b] != b ):
			c = b
			b = U[b]
			U[c] = a
		U[b] = a
	elif U[k[1]]:
		U[k[0]] = U[k[1]]
	elif U[k[0]]:
		U[k[1]] = U[k[0]]
	else:
		U[k[0]] = k[0]
		U[k[1]] = k[0]

ans = 0
c = 0
group = set()
for n in range(1,N+1):
	if U[n] == 0:
		ans += 1
		continue
	elif n == U[n]:
		ans += 1
		group.add(U[n])
	elif U[n] in group:
		continue
	else:
		while(n != U[n] and U[n] not in group):
			group.add(U[n])
			n = U[n]
		group.add(U[n])
print(ans)

Submission status: Accepted

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

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

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

n,m=map(int,input().split())
xyz=[list(map(int,input().split())) for _ in range(m)]
uf=UnionFind(n)
for x,y,z in xyz:
    x,y=x-1,y-1
    uf.union(x,y)

# print(uf.parent)
for i in range(n):
    uf.find(i)
print(len(set(uf.parent)))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N,M = map(int,input().split())
lst = [i for i in range(N)]

def root(n):
    if n == lst[n]:
        return n
    lst[n] = root(lst[n])
    return lst[n]

def union(x,y):
    rootX, rootY = root(x), root(y)
    if rootX != rootY:
        if rootX > rootY:
            lst[rootX] = rootY
        if rootY > rootX:
            lst[rootY] = rootX

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

ans = len([i for i in range(N) if root(i) == i])
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

class UnionFind:
    def __init__(self, num):
        self.p = [x for x in range(num)]
    def root(self, x):
        if self.p[x] == x:
            return x
        else:
            self.p[x] = self.root(self.p[x])
            return self.p[x]
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry:
            self.p[ry] = rx

def main():
    N, M = (int(x) for x in input().split())
    u = UnionFind(N)

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

    rlist = set()
    for i in range(N):
        rlist.add(u.root(i))

    print(len(rlist))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFindNode(object):

    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.rank_ = 1

    def __str__(self):
        template = "UnionFindNode(group_id: {}, \n\tparent: {}, value: {}, size: {})"
        return template.format(self.group_id_, self.parent_, self.value, self.rank_)

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        root = self.root()
        return root.group_id_

    def rank(self):
        root = self.root()
        return root.rank_

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

        if root.group_id_ != unite_root.group_id_:
            if root.rank() > unite_root.rank():
                unite_root.parent_ = root
                root.rank_ = max(root.rank_, unite_root.rank_ + 1)
            else:
                root.parent_ = unite_root
                unite_root.rank_ = max(root.rank_ + 1, unite_root.rank_)
                
if __name__ == "__main__":
    P,Q=map(int,input().split())
    node_list = [UnionFindNode(i) for i in range(1,P+1)]
    root_num=P
    for i in range(Q):
        a,b,c=map(int,input().split())
        if node_list[a-1].root()!= node_list[b-1].root():
            node_list[a-1].unite(node_list[b-1])
            root_num=root_num-1
    print(root_num)

Submission status: Accepted

Solution code:
from collections import deque
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
    x,y,z=map(int,input().split())
    x,y=x-1,y-1
    G[x].append(y)
    G[y].append(x)
ans=0
t=0
k=0
reached=[0]*N
stack=deque()
while(t!=N):
    for i in range(k,N):
        if  reached[i]==0:
            reached[i]=1
            t+=1
            stack=deque(G[i])
            k=i+1
            break
    while(stack):
        g=stack.pop()
        if reached[g]==0:
            reached[g]=1
            t+=1
        for i in G[g]:
            if reached[i]:
                continue
            stack.append(i)
    #print(reached)
    #print(t)
    ans+=1
print(ans)