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:
#!/usr/bin/env python3
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


def solve(N: int, M: int, X: "List[int]", Y: "List[int]", Z: "List[int]"):
    uf = UnionFind(N)
    for i in range(M):
        uf.union(X[i]-1, Y[i]-1)
    cnt = 0
    for elem in uf.table:
        if elem < 0:
            cnt += 1
    print(cnt)

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    X = [int()] * (M)  # type: "List[int]" 
    Y = [int()] * (M)  # type: "List[int]" 
    Z = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        X[i] = int(next(tokens))
        Y[i] = int(next(tokens))
        Z[i] = int(next(tokens))
    solve(N, M, X, Y, Z)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
from functools import reduce

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

n,m = get_nums_l()

groups = n
node_groups = [ i for i in range(n)]
group_sizes = [ 1 for _ in range(n)]
group_ranks = [ 0 for _ in range(n)]

edges = []
for i in range(m):
    tmp=input().split(" ")
    edges.append([int(tmp[0])-1, int(tmp[1])-1])


def root(i):
    if node_groups[i] == i:
        #print(i, "is root.")
        return i
    else:
        #_1 = node_groups[i]
        node_groups[i] = root(node_groups[i])
        #_2 = node_groups[i]
        #print ("root: ", _1, _2)
        return node_groups[i]

def same(a, b):
    return root(a) == root(b)

def size(i):
    return group_sizes[root(i)]

def unite(a, b):
    global groups

    a = root(a)
    b = root(b)

    if a == b:
        return
    
    # 合体したらグループ数が減る
    groups -= 1

    if group_ranks[a] < group_ranks[b]:
        group_sizes[b] += size(a)
        node_groups[a] = b
    else:
        group_sizes[a] += size(b)
        node_groups[b] = a
        if group_ranks[a] == group_ranks[b]:
            group_ranks[a] += 1


for i in range(m-1, -1, -1):
    edge = edges[i]
    # print("edge: ",edge)
    #print("node_groups: ", node_groups)
    node_1 = edge[0]
    node_2 = edge[1]

    root_1 = root(node_1)
    root_2 = root(node_2)

    unite(root_1, root_2)
print(groups)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

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)

n,m = getList()
uf = UnionFind(n)
for i in range(m):
    x, y, _ = getList()
    if not uf.same_check(x,y):
        uf.union(x,y)
        
for i in range(n+1):
    uf.find(i)


print(len(list(set(uf.par[1:]))))

Submission status: Accepted

Solution code:
from collections import deque
import sys
import math
sys.setrecursionlimit(10**6)
from collections import defaultdict
from collections import Counter
from collections import deque

n,m=map(int,input().split())
par=[i for i in range(n+1)]

def root(x):
    if x==par[x]:
        return x
    else:
        par[x]=root(par[x])
        return par[x]
def connect(x,y):
    rx=root(x)
    ry=root(y)
    if rx==ry:
        0
    else:
        par[rx]=ry
    return

for i in range(m):
    a,b,z=map(int,input().split())
    connect(a,b)

st=set()
for i in range(1,n+1):
    st.add(root(i))
print(len(st))

Submission status: Accepted

Solution code:
from collections import deque
    
N,M = list(map(int,input().split()))

node_list = [[] for i in range(N)]

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

checked_list = [-1 for i in range(N)]

def BFS(start,color,checked_list,node_list):
    Q=deque([start])
    checked_list[start]=color
    while len(Q)>0:
        v1 = Q.pop()
        for v2 in node_list[v1]:
            if checked_list[v2]==-1:
                checked_list[v2]=color
                Q.appendleft(v2)


count = 0
for i in range(N):
    if checked_list[i]==-1:
        BFS(i,count,checked_list,node_list)
        count+=1
        
print(count)

Submission status: Accepted

Solution code:
# UnionTreeクラス：グループ分けを木構造で管理する
class UnionFind():
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.size = [1] * N
        self.N = N

    # xのrootを返す
    def root(self, x):
        if self.par[x] == x:
            return x
        else: 
            self.par[x] = self.root(self.par[x])
            return self.root(self.par[x])

    # x, yが同じrootの場合true
    def same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry

    # x,yのrootが違った場合、併合
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if self.size[rx] < self.size[ry]:
            self.par[rx] = ry
            self.size[ry] += self.size[rx]
        else:
            self.par[ry] = rx
            self.size[rx] += self.size[ry]
            
import sys
input = sys.stdin.readline

n, m = (int(i) for i in input().split())
xyz = [[int(i)-1 for i in input().split()] for i in range(m)]

uf = UnionFind(n)
for x,y,z in xyz:
    if not uf.same(x,y):
        uf.unite(x,y)

dic = {}
for i in range(n):
    dic[uf.root(i)] = 1

print(len(dic))

Submission status: Accepted

Solution code:
def func(acc, tmp, N):
    for i in range(tmp,N):
        if acc[i]==0:
            return i
    return -1

N,M=[int(x) for x in input().split()]
con=[[] for i in range(N+1)]
acc=[0 for i in range(N+1)]
for m in range(M):
    X,Y,Z=[int(x) for x in input().split()]
    con[X].append(Y)
    con[Y].append(X)
ans=1
acc[0]=1
acc[1]=1
focus=[1]
L=1
tmp=1
while(L<N):
    newfocus=[]
    if len(focus)==0:
        c=func(acc, tmp, N)
        tmp=c+1
        focus=[c]
        acc[c]=1
        ans+=1
        L+=1
    for f in focus:
        for c in con[f]:
            if acc[c]==0:
                newfocus.append(c)
                acc[c]=1
                L+=1
    focus=newfocus[:]
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    import sys
    sys.setrecursionlimit(100000)

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

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

    def unite(self, i, j):
        self.parents[self.root(self.parents[i])] = self.root(j)

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


def solve(N, XYZs):
    uf = UnionFind(N)
    for x, y, z in XYZs:
        uf.unite(x, y)
    return len(set([uf.root(i) for i in range(1, N + 1)]))


if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    XYZs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    print(solve(N, XYZs))

Submission status: Accepted

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

P=[i for i in range(N+1)]
size=[1 for i in range(N+1)]


def find(x):
    if P[x]==x:
        return x
    else:
        return find(P[x])
        
def union(y,z):
    Y=find(y)
    Z=find(z)
    if Y!=Z:
        if size[Y]>=size[Z]:
            P[Z]=P[Y]
            size[Y]+=size[Z]
        else:
            P[Y]=P[Z]
            size[Z]+=size[Y]

for i in range(M):
    x,y,z=map(int,input().split())
    if find(x)!=find(y):
        union(x,y)
#print(P)
ans=0
for i in range(1,N+1):
    if i==P[i]:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:

def main():
    buf = input()
    buflist = list(buf.split())
    N = int(buflist[0])
    M = int(buflist[1])
    edge = dict()
    for i in range(N):
        edge[i] = [] # zero index
    for i in range(M):
        buf = input()
        buflist = list(buf.split())
        X = int(buflist[0])-1 # zero index
        Y = int(buflist[1])-1 # zero index
        Z = int(buflist[2])
        edge[X].append(Y)
        edge[Y].append(X)
    seen = []
    for i in range(N):
        seen.append(False)
    group_num = 0
    for i in range(N):
        if seen[i]:
            continue
        group_num += 1
        seen[i] = True
        stack = []
        for x in edge[i]:
            stack.append(x)
        while stack:
            current = stack.pop()
            if seen[current]:
                continue
            seen[current] = True
            for x in edge[current]:
                if not seen[x]:
                    stack.append(x)
    print(group_num)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind():
    #ｎは頂点数
    def __init__(self, n):
        self.parent = [-1]*n

    #aの属する集合の根を取得
    def root(self,a):
        if self.parent[a] < 0:return a
        self.parent[a] = self.root(self.parent[a])
        return self.parent[a]
    
    #aの属する集合の要素数を取得
    def size(self,a):
        return -self.parent[self.root(a)]

    #aとbをくっつける
    def connect(self,a,b):
        if self.root(a) == self.root(b):return False
        a = self.root(a);b = self.root(b)
        if self.size(a) < self.size(b):a,b = b,a
        self.parent[a] += self.parent[b]
        self.parent[b] = a
        return True

n,m = map(int,input().split())
uni = UnionFind(n)
for i in range(m):
    x,y,z = map(int,input().split())
    x -= 1
    y -= 1
    uni.connect(x,y)
ans = 0
for i in uni.parent:
    if i < 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
n,m = map(int,input().split())
 
#Union Find
par = [] #親
rank = [] #木の深さ
 
#初期化
for i in range(n):
    #par[i]:i rank[i]:0
    par.append(i)
    rank.append(0)
 
#木の根を求める
def find(x,par):
    if par[x] == x:
        return x
    else:
        return find(par[x],par)
 
#xとyの属する集合の併合
def unite(x,y,par,rank):
    x = find(x,par)
    y = find(y,par)
    
    if x != y:
        #xとyの属している集合が異なる時
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x]==rank[y]:
                rank[x] += 1
 
#xとyが同じ集合に属するかの判定
def same(x,y,par):
    return find(x,par) == find(y,par)
 
for i in range(m):
    X,Y,Z = map(int,input().split())
    unite(X-1,Y-1,par,rank)
 
tank = []
for i in range(n):
    p = find(i,par)
    tank.append(p)
print(len(set(tank)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)

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

visited = [False for i in range(N)]
v_to = [[] for i in range(N)]

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

def dfs(i):
  if visited[i]:
    return 0

  visited[i] = True
  for to in v_to[i]:
    dfs(to)

  return 1

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

print(ans)

Submission status: Accepted

Solution code:
class UnionFind():

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

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

  def union(self, x, y):
    xroot, yroot = self.find(x), self.find(y)
    if xroot == yroot:
      return False
    elif self.rank[xroot] < self.rank[yroot]:
      self.par[xroot] = yroot
    elif self.rank[xroot] > self.rank[yroot]:
      self.par[yroot] = xroot
    else:
      self.par[yroot] = xroot
      self.rank[xroot] += 1
    return True

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

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

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools, random
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right; sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

n, m = wi()
#XYZ
w = mi(m)

class UnionFind2(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]


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


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

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)
u = UnionFind2(n)
for i in range(m):
    u.union(w[i][0] - 1, w[i][1] - 1)

se = set()
for i in range(n):
    se.add(u.find(i))


print(len(se))

Submission status: Accepted

Solution code:
class UnionFind (object):
	def __init__(self, N):
		self.parent = [-1] * N

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

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

	def unite(self, x, y):
		x, y = self.root(x), self.root(y)
		
		if x == y:
			return False
		
		if -self.parent[x] < -self.parent[y]:
			x, y = y, x
		self.parent[x] += self.parent[y]
		self.parent[y] = x
		return True


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

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

print(sum(p < 0 for p in uf.parent))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

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

graph = [[] for _ in range(n)]
for i in range(m):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    graph[x].append(y)
    graph[y].append(x)

memo = [-1] * n

def dfs(v, memo):
    memo[v] = 1
    for nv in graph[v]:
        if memo[nv] != -1:
            continue
        dfs(nv, memo)

ans = 0

for i in range(n):
    if memo[i] != -1:
        continue
    dfs(i, memo)
    ans += 1

print(ans)

Submission status: Accepted

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


    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(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
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)
n, m = map(int, input().split())
U=UnionFind(n)
for i in range(m):
    x, y, z = map(int, input().split())
    U.unite(x-1, y-1)
cnt=0
for i in range(n):
    if U.find(i)==i:
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
import sys
# input = sys.stdin.readline
inf = 10 ** 18

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

# https://qiita.com/maron8676/items/6010128f4ef5c268f719
class UFnode(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 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_)

nodes = [UFnode(i) for i in range(N)]

for i, (Xi, Yi, Zi) in enumerate(XYZ):
    nodes[Xi - 1].unite(nodes[Yi - 1])

print(len(set([nodes[i].find() for i in range(N)])))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
# 連結成分
# UF tree

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

root = list(range(N+1))
depth = [0] * (N+1)

def find_root(x):
  y = root[x]
  if x == y:
    return x
  z = find_root(y)
  root[x] = z
  return z

def merge(x,y):
  global n_component
  xx = find_root(x)
  yy = find_root(y)
  if xx == yy:
    return
  n_component -= 1
  if depth[xx] >= depth[yy]:
    root[yy] = xx
    depth[xx] += 1
  else:
    root[xx] = yy
    depth[yy] += 1
  
for _ in range(M):
  x,y,z = [int(x) for x in input().split()]
  merge(x,y)

answer = n_component
print(answer)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

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

class UnionFind:
    def __init__(self,n):
        self.par = [i for i in range(n)] #親
        self.rank = [1]*n #深さ
        self.size = [1]*n #size[i]:=iを根とするグループのサイズ
    
    def find(self,x):
        if self.par[x] == x:
            return x
        else:
            return self.find(self.par[x])
            
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.par[x] = y
                self.size[y] += self.size[x]
            else:
                self.par[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1
                    
    def same(self,x,y):
        return self.find(x) == self.find(y)
        
    def group_size(self,x):
        return self.size[self.find(x)]
        
uf = UnionFind(N)
for x, y, z in xyz:
    x, y = x-1, y-1
    uf.unite(x,y)
ans = 0
for i in range(N):
    if i == uf.find(i):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
  def __init__(self):
    self.ht = {}

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

  def unite(self, x, y):
    nx = self.ht[x]
    ny = self.ht[y]
    if self.same(x, y):
      return
    xr = nx.root()
    yr = ny.root()
    xr.set_parent(yr)

  def add(self, x):
    n = Node(x)
    n.set_parent(None)
    self.ht[x] = n

  def show(self):
    roots = {}
    for n in self.ht.values():
      nr = n.root()
      if nr in roots:
        roots[nr].append(n.val)
      else:
        roots[nr] = [n.val]
    for s in roots.values():
      print(s)

  def get_set(self):
    roots = {}
    for n in self.ht.values():
      nr = n.root()
      if nr in roots:
        roots[nr].append(n.val)
      else:
        roots[nr] = [n.val]
    return roots.values()

class Node:
  def __init__(self, val):
    self.val = val

  def root(self):
    n = self
    chain = []
    while n.parent != None:
      chain.append(n)
      n = n.parent
    root = n
    for n in chain:
      n.set_parent(root)
    return root

  def set_parent(self, x):
    self.parent = x


## main

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

for i in range(1, n+1):
  uf.add(i)

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

cnt = len(uf.get_set())

print(cnt)

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

def main():
    N, M = [int(n) for n in input().split()]
    node_list = [UnionFindNode(i) for i in range(N)]
    for i in range(M):
        X, Y, Z = [int(n) for n in input().split()]
        node_list[X-1].unite(node_list[Y-1])
    gs = set()
    for node in node_list:
        gid = node.find()
        gs.add(gid)
    print(len(gs))
main()

Submission status: Accepted

Solution code:
def unite(rt, x, y):
	tx = x
	ty = y
	if tx > ty:
		tx, ty = ty, tx
	rt[ty] = tx
def find(rt, x):
	if rt[x] == -1 or rt[x] == x:
		return x
	else:
		rt[x] = find(rt, rt[x])
		return rt[x]
def main():
	n, m = map(int, input().split())
	rt = [-1]*(n+1)
	ans = n
	for i in range(m):
		x, y, z = map(int, input().split())
		root_x = find(rt, x)
		root_y = find(rt, y)
		if root_x == -1 or root_y == -1:
			pass
		elif root_x == root_y:
			continue
		ans -= 1
		unite(rt, root_x, root_y)
	print(ans)
main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import Counter

def main():
    N, M = LI()
    edges = [[] for _ in range(N)]
    for _ in range(M):
        x, y, xxx = LI_()
        edges[x].append(y)
        edges[y].append(x)
    ans = 0
    visited = [0] * N
    def connect(k):
        visited[k] = 1
        for e in edges[k]:
            if visited[e] == 0:
                connect(e)
    for i in range(N):
        if visited[i] == 0:
            ans += 1
            connect(i)
    return ans

print(main())

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


class UnionFind(object):
    """重み付きUnionFind木
    """

    def __init__(self, N, unity=0):
        self.tree = list(range(N))
        self.rank = [0] * N
        self.diff_weight = [unity]*N

    def root(self, i):
        if self.tree[i] == i:
            return i
        else:
            r = self.root(self.tree[i])
            self.diff_weight[i] += self.diff_weight[self.tree[i]]
            self.tree[i] = r
            return r

    def weight(self, i):
        self.root(i)
        return self.diff_weight[i]

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

    def unite(self, x, y, w):
        w += self.weight(x)
        w -= self.weight(y)
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.rank[x] < self.rank[y]:
            x, y = y, x
            w = -w
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.tree[y] = x
        self.diff_weight[y] = w
        return True

    def diff(self, x, y):
        return self.weight(x) - self.weight(y)


def solve(N: int, M: int, X: "List[int]", Y: "List[int]", Z: "List[int]"):
    uf = UnionFind(N)
    for x, y, z in zip(X, Y, Z):
        uf.unite(x-1, y-1, z)

    print(len(set([uf.root(i) for i in range(N)])))

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    X = [int()] * (M)  # type: "List[int]"
    Y = [int()] * (M)  # type: "List[int]"
    Z = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        X[i] = int(next(tokens))
        Y[i] = int(next(tokens))
        Z[i] = int(next(tokens))
    solve(N, M, X, Y, Z)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Group=[i for i in range(N+1)]#グループ分け.Group[i]=jのときiとjは同じグループ

def find(x):#find(a)=find(b)のとき同じグループ
    while Group[x] != x:
        x=Group[x]
    return x

def Union(x,y):  # xとyが同じグループになるよう更新
    if find(x) != find(y):
        Group[find(y)]=Group[find(x)]=min(find(y),find(x))

for x,y,z in XYZ:
    Union(x,y)

ANS=[find(i) for i in range(1,N+1)]
print(len(set(ANS)))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
R = [i for i in range(N)]
def root(x):
  if R[x] == x:
    return x
  else:
    R[x] = root(R[x])
    return R[x]
def union(x, y):
  rx = root(x)
  ry = root(y)
  if rx < ry:
    R[ry] = rx
  else:
    R[rx] = ry
for i in range(M):
  x, y, z = map(int, input().split())
  union(x - 1, y - 1)
for i in range(N):
  root(i)
print(len(set(R)))

Submission status: Accepted

Solution code:
# Union-Findデータ構造
class UnionFind:
    def __init__(self, numV):
        self.pars = list(range(numV))
        self.ranks = [0] * numV
    def find(self, x):
        if self.pars[x] == x: return x
        else:
            self.pars[x] = self.find(self.pars[x])
            return self.pars[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        if self.ranks[x] < self.ranks[y]:
            self.pars[x] = y
        else:
            self.pars[y] = x
            if self.ranks[x] == self.ranks[y]:
                self.ranks[x] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)


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)

for i in range(N):
    UF.find(i)

parents = UF.pars
print(len(set(parents)))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
edges = [[] for _ in range(N)]
for _ in range(M):
    x,y,z = map(int,input().split())
    edges[x-1].append(y-1)
    edges[y-1].append(x-1)
from collections import deque
queue = deque()
ans = 0
index = 0
checked = [False for _ in range(N)]
while index < N:
    if checked[index]:
        index += 1
        continue
    ans += 1
    queue.append(index)
    checked[index] = True
    while len(queue) > 0:
        v = queue.popleft()
        for w in edges[v]:
            if checked[w]:
                continue
            queue.append(w)
            checked[w] = True
    index += 1
print(ans)