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:
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

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

    parent = {x:[] for x in range(1,n+1)}

    na_num = 1

    for _ in range(m):
        u,v,w = map(int, input().split())
        parent[u].append(v)
        parent[v].append(u)

    base = [1]

    ans = 0

    for i in range(2,n+1):
        if len(parent[i]) == 0:
            ans += 1

    while True:
        pop_num = base.pop()
        for i in parent[pop_num]:
            parent[i].remove(pop_num)
            base.append(i)
        parent[pop_num] = []
        if len(base) == 0:
            ans += 1
            while len(parent[na_num]) == 0:
                na_num += 1
                if na_num == n+1:
                    print(ans)
                    exit()
            base.append(na_num)

Submission status: Accepted

Solution code:

from collections import defaultdict


def get_dic(dic_data, x):
    while x != dic_data[x]:
        x = dic_data[x]
    return x

def main():
    num, hinto = map(int, input().split())
    data_flg = [-1 for i in range(num + 1)]
    ans = 0
    modoru = 0

    dic_data = {i: i for i in range(num + 1)}

    real_ans = 0

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

        if data_flg[x] == -1 and data_flg[y] == -1:
            data_flg[x] = ans
            data_flg[y] = ans
            ans += 1
            real_ans += 1
        elif data_flg[x] == -1 or data_flg[y] == -1:
            aaa = max(data_flg[x], data_flg[y])
            data_flg[x] = aaa
            data_flg[y] = aaa
        else:
            # print(data_flg[x], data_flg[y])
            nnn = get_dic(dic_data, data_flg[x])
            bbb = get_dic(dic_data, data_flg[y])
            if nnn != bbb:
                dic_data[nnn] = ans
                dic_data[bbb] = ans
                modoru += 1
                ans += 1

    real_ans -= modoru

    for i in range(1, num + 1):
        if data_flg[i] == -1:
            real_ans += 1

    print(real_ans)




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import *



class V:
    def __init__(self,si):
        self.si = si
        self.parent = self
    def isInnovator(self):
        return self.parent == self
    def findInnovator(self):
        re = self
        while True:
            if re.parent == re:
                self.parent = re
                return re
            re = re.parent


N,K = tuple(map(int,input().split()))
vs = [V(vi) for vi in range(N)]

for _ in range(K):
    ui,vi,w = tuple(map(int,input().split()))
    ui-=1
    vi-=1
    u = vs[ui]
    v = vs[vi]
    uInnov = u.findInnovator()
    vInnov = v.findInnovator()
    if uInnov == vInnov:
        continue
    vInnov.parent = uInnov

re = 0
for v in vs:
    if v.isInnovator():
        re += 1

print(re)

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)
        self.count = [1] * (n + 1)

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

    # union
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.count[y] += self.count[x]
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.count[x] += self.count[y]

    # size
    def size(self, x):
        return self.count[self.par[x]]

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

n,m=map(int,input().split())
UF=UnionFind(n)
for i in range(m):
    x,y,z=map(int,input().split())
    UF.union(x,y)
cnt=0
S=set()
for i in range(1,n+1):
    x=UF.find(i)
    if x not in S:
        cnt+=1
        S.add(x)
print(cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 19 22:22:33 2019

@author: Yamazaki Kenichi
"""

N,M = map(int,input().split())
xyz = [list(map(int,input().split())) for i in range(M)]

import sys
sys.setrecursionlimit(10**6)

class UnionFind(object):

    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

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

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        else:
            return False

uf = UnionFind(N+1)
for c in xyz:
    uf.union(c[0],c[1])
ans = -1
for u in uf.table:
    if u<0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
graph = [[] for i in range(N)]
for i in range(M):
    x, y, z = map(int, input().split())
    x, y = x-1, y-1
    graph[x].append(y)
    graph[y].append(x)
visited = [False for i in range(N)]
def bfs(v):
    Q = []
    visited[v] = True
    Q.append(v)
    while len(Q) > 0:
        v = Q.pop(0)
        for u in graph[v]:
            if not visited[u]:
                visited[u] = True
                Q.append(u)

count = 0
for i in range(N):
    if not visited[i]:
        bfs(i)
        count += 1
print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, XYZ):
    g = defaultdict(dict)
    for x, y, z in XYZ:
        g[x][y] = z % 2
        g[y][x] = z % 2

    ans = 0
    done = set()
    for i in range(1, N+1):
        if i in done:
            continue
        ans += 1
        q = deque([i])
        while q:
            u = q.popleft()
            done.add(u)
            for v in g[u]:
                if v not in done:
                    q.append(v)
                    done.add(v)
    return ans


def main():
    # N = read_int()
    N, M = read_int_n()
    XYZ = [read_int_n() for _ in range(M)]
    print(slv(N, M, XYZ))

    # N = 10**5
    # XYZ = [random.randint()]


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, math, collections, heapq, itertools
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0: a, b = b, a % b
    return b
 
def find(a, L):
    if L[a] == a: return a
    else: 
        L[a] = find(L[a], L)
        return L[a]
 
def unite(a, b, L, R):
    a = find(a, L)
    b = find(b, L)
    if a == b: return
    if R[a] < R[b]:
        L[a] = b
    else:
        L[b] = a
        if R[a] == R[b]: R[a] += 1
    
  
def solve():
    N, M = map(int, line_input())
    parent = [int(i) for i in range(N)]
    edge = [[] for i in range(N)]
    rank = [0] * N
    for i in range(M):
        x, y, z = map(int, line_input())
        unite(x-1, y-1, parent, rank)
    for i in range(N):
        parent[i] = find(i, parent)
    print(len(set(parent)))
    return 0
  
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from collections import defaultdict


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

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(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 same_check(self, x, y):
        return self.find(x) == self.find(y)


class Solution:
    def main(self):
        N, M = map(int, input().split())
        ufind = UnionFind(N)
        for _ in range(M):
            X, Y, Z = map(int, input().split())
            ufind.union(X-1, Y-1)
        print(len(set([ufind.find(i) for i in range(N)])))


if __name__ == '__main__':
    Solution().main()

Submission status: Accepted

Solution code:
class Element:
	val = 0
	parent = None
	height = 0
	size = 1
	def __init__(self, val, parent=None, height=0, size=1):
		self.val = val
		if parent is None:
			self.parent = self
		else:
			self.parent = parent
		self.height = height
		self.size = size

class UnionFindTree:
	elemnts = []

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

	def root(self, x:int) -> Element:
		if self.elemnts[x].parent is self.elemnts[x]:
			return self.elemnts[x]
		return self.root(self.elemnts[x].parent.val)

	def same(self, x:int, y:int) -> bool:
		rx = self.root(x)
		ry = self.root(y)
		return rx is ry

	def unite(self, x:int, y:int):
		rx = self.root(x)
		ry = self.root(y)
		if rx == ry:
			return
		if rx.height < ry.height:
			rx.parent = ry
			ry.size += ry.height
		else:
			ry.parent = rx
			rx.size += ry.size
			if rx.height == ry.height:
				rx.height += 1

def main():
	N, M = map(int, input().split())
	uionfind = UnionFindTree(N)
	for i in range(M):
		u, v, z = map(int, input().split())
		uionfind.unite(u-1, v-1)
	ans_set = set()

	ans = 0
	for i in range(N):
		this_root = uionfind.root(i).val
		if not this_root in ans_set:
			ans += 1
			ans_set.add(this_root)
	print(ans)


if __name__ == '__main__':
	main()

Submission status: Accepted

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


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

    def union(self, i, j):
        i = self.root(i)
        j = self.root(j)
        if i == j:
            return
        if self.rank[i] < self.rank[j]:
            self.parent[i] = j
        else:
            if self.rank[i] == self.rank[j]:
                self.rank[j] += 1
            self.parent[j] = i

    def same(self, i, j):
        return self.root(i) == self.root(j)

    def root(self, i):
        if self.parent[i] != i:
            self.parent[i] = self.root(self.parent[i])
        return self.parent[i]


uf = UnionFind(N)

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

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)] 
        
uf = UnionFind(N)
for m in range(M):
    a,b,c = map(int, input().split())
    uf.Unite(a-1, b-1)
ls = []
for n in range(N):
    ls.append(uf.Find_Root(n))
print (len(set(ls)))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
w=[i for i in range(n+1)]
s=[1]*(n+1)
def root(x):
    if w[x]==x:
        return x
    x=w[x]
    return root(w[x])
def unite(x,y):
    x=root(x)
    y=root(y)
    if x!=y:
        if s[x]<s[y]:
            w[x]=y
            s[y]+=1
        else:
            w[y]=x
            s[x]+=1
for i in range(m):
    x,y=list(map(int,input().split()))[:2]
    unite(x,y)
go=set()
for i in range(1,n+1):
    go.add(root(i))
print(len(go))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
import collections
import itertools
import operator

class UnionFind:
  def __init__(self, elems=None):
    class KeyDict(dict):
      def __missing__(self, key):
        self[key] = key
        return key

    self.parent = KeyDict()
    self.rank = collections.defaultdict(int)
    self.size_ = collections.defaultdict(lambda: 1)

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

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

  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 size(self,x):
    return self.size_[self.find(x)]

g = UnionFind()
n,m = na()

for i in range(m):
    x,y,z = na()
    g.unite(x,y)

f = list(g.grouper())

a = 0
b = 0
for i in f:
    a+=len(i)
    b+=1

print(b+n-a)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

D = defaultdict(list) 
S = [0 for i in range(N)] #S[i-1]で探索済判定
for i in range(M):
    x,y,z = map(int,input().split())
    D[x].append(y)
    D[y].append(x)
    
ans = 0
for i in range(N):
    if S[i]>0:continue
    T = [i+1]
    S[i] = 1
    ans += 1
    while T:
        n = T.pop()
        for d in D[n]:
            if S[d-1]>0:continue
            else: S[d-1] = 1
            T.append(d)
        
print(ans)

Submission status: Accepted

Solution code:
class uf_tree:
    def __init__(self, n):
        self._size = n
        self.sizes = [1] * n
        self.par = list(range(n))
 
    def find(self, x):
        if x == self.par[x]:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]
 
    def unite(self, x, y):
        self._size -= 1
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.sizes[x] < self.sizes[y]:
            x, y = y, x
        self.par[y] = x
        self.sizes[x] += self.sizes[y]
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def size(self, x):
        return self.sizes[self.find(x)]


n, m = map(int, input().split())
uf = uf_tree(n+1)

for _ in range(m):
    x, y, z = map(int, input().split())
    if uf.same(x, y):
        continue
    uf.unite(x, y)
    #print("x, y", uf._size)

ans = uf._size - 1
print(ans)

Submission status: Accepted

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
import math



class UnionFind():
  def __init__(self, size):
    self.par = [-1]*size
      
  def root(self,x):
    if self.par[x] < 0:
      return x
    else:
      return self.root(self.par[x])
      
  def issame(self,x,y):
    if self.root(x)==self.root(y):
      return True
    else:
      return False
  
  def merge(self,x,y):
    x, y = [self.root(x), self.root(y)]
    if x == y:
      return False
    if self.par[x] > self.par[y]:
      x, y = y, x
    self.par[x] += self.par[y]
    self.par[y] = x
    return True

  def get_list(self):
    return self.par


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

  ret = 0
  for p in list(uf.get_list()):
    if p < 0:
      ret += 1
  return ret


if __name__ == "__main__":
  print(main())

Submission status: Accepted

Solution code:
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
    def find(self, x):
        if self.par[x] == x:
          return x
        else:
          self.par[x] = self.find(self.par[x])
          return self.find(self.par[x])
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    def tree_num(self):
        return len([i for i in range(n) if self.par[i] == i])

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

Submission status: Accepted

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
        
n,m=map(int,input().split())
t=UnionFind(n)
for i in range(m):
    x,y,z=map(int,input().split())
    t.Unite(x,y)
s=set()
for i in range(1,n+1):
    s.add(t.Find_Root(i))
print(len(s))

Submission status: Accepted

Solution code:
from collections import defaultdict

def dfs(u):
    st = [u]
    while st:
        u = st.pop()
        if cv[u]: continue
        cv[u] = 1
        for nxt in adj[u]:
            st.append(nxt)

n, m = [int(item) for item in input().split()]
data = []
ans = [-1] * n
adj = defaultdict(set)
for _ in range(m):
    x, y, z = [int(item) for item in input().split()]
    x -= 1
    y -= 1
    adj[x].add(y)
    adj[y].add(x)


cost = 0
cv = [0] * n
for i in range(n):
    if not cv[i]:
        cost += 1
        dfs(i)

print(cost)

Submission status: Accepted

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

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

    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__":
    N,M = map(int,input().split())
    ans = N
    node_list = [UnionFindNode(i) for i in range(N)]
    for i in range(M):
        X,Y,Z = map(int,input().split())
        X -= 1
        Y -= 1
        if node_list[X].root() != node_list[Y].root():
            ans -= 1
        node_list[X].unite(node_list[Y])
    print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
xyz=[list(map(int,input().split())) for i in range(m)]
ans=[0 for i in range(n+1)]
h=[[] for i in range(n+1)]
for i in xyz:
  x,y,z=i
  h[x].append(y)
  h[y].append(x)
fa=0
i=1
while(i<=n):
  if(ans[i]==0):
    q=[i]
    ans[i]=1
    fa+=1
    while(len(q)>0):
      t=q.pop()
      for j in h[t]:
        if(ans[j]==0):
          q.append(j)
          ans[j]=1
    i+=1 
  else:
    i+=1
print(fa)

Submission status: Accepted

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

class Unionfind:

    __slots__ = ['nodes','size']

    def __init__(self, n):
        self.nodes = list(range(n))
        self.size = [1]*n

    def root(self, x):
        if self.nodes[x] == x:
            return x
        else:
            root_x = self.root(self.nodes[x])
            self.nodes[x] = root_x
            return root_x

    def unite(self, x, y):
        x = self.root(x); y = self.root(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.size[x] += self.size[y]
        self.nodes[y] = x

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

N,M = map(int,input().split())
info = [list(map(int,input().split())) for _ in range(M)]

uf = Unionfind(N)

for x,y,z in info:
    x -= 1
    y -= 1
    uf.unite(x,y)

for i in range(N):
    uf.root(i)

ans = len(list(set(uf.nodes)))
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

def Find(x):    #xの根を返す
    global table

    if table[x] == x:
        return x
    else:
        table[x] = Find(table[x])    #親の更新(根を直接親にして参照距離を短く)
        size[x] = size[table[x]]
        return table[x]

def Unite(x,y):    #xとyを繋げる
    global size
    global rank
    x = Find(x)
    y = Find(y)
    sx = Size(x)
    sy = Size(y)

    if x == y:
        return

    if rank[x] > rank[y]:
        table[y] = x
        size[x] = sx + sy
    else:
        table[x] = y
        size[y] = sx + sy
        if rank[x] == rank[y]:
            rank[y] += 1

def Check(x,y):
    if Find(x) == Find(y):
        return True
    else:
        return False

def Size(x):
    return size[Find(x)]

N,M = inpl()

table = [i for i in range(N)]    #木の親 table[x] == x なら根
rank  = [1 for i in range(N)]    #木の長さ
size  = [1 for i in range(N)]    #集合のサイズ

for i in range(M):
    x,y,z = inpl()
    x -= 1
    y -= 1
    if not Check(x,y):
        Unite(x,y)

cnt = [0]*N
for x in table:
    cnt[Find(x)] = 1
print(sum(cnt))

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.rank = 0


class DisjointSet:
    def __init__(self, nodes):
        self.nodes = nodes

    def find_set(self, key):
        pivot = self.nodes[key]
        while pivot.key != pivot.parent.key:
            pivot = pivot.parent
        self.nodes[key].parent = pivot
        return pivot.key

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

    def unite(self, x, y):
        y_root = self.find_set(y)
        x_root = self.find_set(x)
        if self.nodes[x].rank > self.nodes[y].rank:
            self.nodes[y_root].parent = self.nodes[x_root]
        elif self.nodes[x].rank < self.nodes[y].rank:
            self.nodes[x_root].parent = self.nodes[y_root]
        else:
            self.nodes[x_root].parent = self.nodes[y_root]
            self.nodes[y_root].rank = self.nodes[y_root].rank + 1


N, M = [int(i) for i in input().split()]
nodes = [Node(i) for i in range(N)]
for node in nodes:
    node.parent = node
ds = DisjointSet(nodes)

for _ in range(M):
    x, y, z = [int(i) for i in input().split()]
    x -= 1
    y -= 1
    if ds.same(x, y):
        pass
    else:
        ds.unite(x, y)
ans = len(set([ds.find_set(i) for i in range(N)]))
print(ans)

Submission status: Accepted

Solution code:
N, M =map(int,input().split())
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        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 と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]
uf = UnionFind(N)
cnt = 0
for i in range(M):
  x, y, z = map(int, input().split())
  if not uf.is_same(x-1, y-1):
    cnt += 1
    uf.union(x-1,y-1)
    
print(N-cnt)

Submission status: Accepted

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

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

class UnionFind():
    def __init__(self, N):
        self.rank = [0] * N
        self.par = [i for i in range(N)]
        self.counter = [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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            z = self.counter[x] + self.counter[y]
            self.counter[x], self.counter[y] = z, z
        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 size(self, x):
        x = self.find(x)
        return self.counter[x]

    def same(self, x, y):
        return self.find(x) == self.find(y)
UF = UnionFind(n)
ans = n
for i in range(m):
    x,y,z = map(int,input().split())
    if  UF.same(x-1,y-1):
        continue
    else:
        UF.unite(x-1,y-1)
        ans -=1
print(ans)