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:
n, m = map(int, input().split())

xy = [i for i in range(n + 1)]


def root(x):
    i = x
    while i != xy[i]:
        i = xy[i]
    xy[x] = i
    return i


for _ in range(m):
    x, y, z = map(int, input().split())
    rx = root(x)
    ry = root(y)
    if rx != ry:
        xy[ry] = rx

ans = -1
for i, v in enumerate(xy):
    if i == v:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
p = [i for i in range(N)]#parent
g = [[i] for i in range(N)]#group
for _ in range(M):
  x,y,z = map(int,input().split())
  x,y = p[x-1],p[y-1]
  if x==y:
    continue
  if len(g[x])<len(g[y]):
    x,y = y,x
  g[x] += g[y]
  for z in g[y]:
    p[z] = x
print(len(set(p)))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
p = [i for i in range(N)]#parent
g = [[i] for i in range(N)]#group
for _ in range(M):
  x,y,z = map(int,input().split())
  x,y = p[x-1],p[y-1]
  if x==y:
    continue
  if len(g[x])<len(g[y]):
    x,y = y,x
  g[x] += g[y]
  for z in g[y]:
    p[z] = x
  g[y] = []
print(len(set(p)))

Submission status: Accepted

Solution code:
from collections import deque


def putid(nodes, edges, group_id, start):
    q = deque([start])

    while q:
        cp = q.popleft()
        if not nodes[cp]:
            nodes[cp] = group_id
            if edges[cp]:
                for edge in edges[cp]:
                    q.append(edge)


def main():
    N, M = map(int, input().split())
    edges = [[] for _ in range(N)]
    nodes = [0] * N

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

    ans = 0

    for i in range(N):
        if not nodes[i]:
            ans += 1
            putid(nodes, edges, ans, i)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 入力
N, M = map(int, input().split())
X, Y, Z = (
    zip(*(map(int, input().split()) for _ in range(M))) if M else
    ((), (), ())
)


# UnionFind木で連結成分の個数を数える
class UnionFindTree:
    def __init__(self, n):
        self.p = [i for i in range(n + 1)]
        self.r = [0 for _ in range(n + 1)]

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

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.r[px] < self.r[py]:
                self.p[px] = py
            else:
                self.p[py] = px
                if self.r[px] == self.r[py]:
                    self.r[px] += 1

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


uft = UnionFindTree(N)
for x, y in zip(X, Y):
    uft.union(x, y)
ans = len({uft.find(i) for i in range(1, N + 1)})

# 出力
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)

class UnionFind():
    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,a,b):
        a1 = self.find(a)
        a2 = self.find(b)
        if a1!= a2:
            if self.table[a1] < self.table[a2]:
                self.table[a1] = a2
            elif self.table[a2] < self.table[a1]:
                self.table[a2] = a1
            else:
                self.table[a1] = a2
                self.table[a2] -= 1
        return
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)
cnt = 0
for i in range(N):
    if uf.table[i] < 0:
        cnt += 1
print(cnt)

Submission status: Accepted

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

def get_par(x):
  if x == par_list[x]:
    return x
  else:
    par_list[x] = get_par(par_list[x])
    return par_list[x]

N,M=map(int,input().split())
par_list = list(range(N))
for i in range(M):
  Xi,Yi,Zi=map(int,input().split())
  par_Xi = get_par(Xi-1)
  par_Yi = get_par(Yi-1)
  if par_Xi != par_Yi:
    par_list[par_Yi] = par_Xi
    
set_uf = set()
for par in par_list:
  set_uf.add(get_par(par))
  
print(len(set_uf))

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 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 = map(int, input().split())
uftree = UnionFind(N)
for i in range(M):
    X, Y, Z = map(int, input().split())
    uftree.union(X, Y)
dict = {}
for i in range(N):
    if uftree.find(i+1) not in dict:
        dict[uftree.find(i+1)] = 0

print(len(dict))

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000


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

# print(tree)
used = [0 for i in range(N)]

def dfs(node,p):
    used[node] = 1
    # print(tree[node])
    for new in tree[node]:
        if new == p or used[new] == 1:continue
        dfs(new,node)

cnt = 0
while sum(used) < len(used):
    for i in range(N):
        if used[i] == 0:
            dfs(i,-1)
            cnt += 1

ans = cnt
print(ans)

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000


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

# print(tree)
used = [0 for i in range(N)]

def dfs(node,p):
    used[node] = 1
    # print(tree[node])
    for new in tree[node]:
        if new == p or used[new] == 1:continue
        dfs(new,node)

cnt = 0
while sum(used) < len(used):
    for i in range(N):
        if used[i] == 0:
            dfs(i,-1)
            cnt += 1

ans = N - (sum(used) - cnt)
print(ans)

Submission status: Accepted

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

    # 検索
    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 groupsize(self):
        self.cnt = 0
        for i,x in enumerate(self.par):
            if x == i:
                self.cnt += 1
        return self.cnt

    # 併合
    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 = map(int,input().split())
XYZ = [list(map(int,input().split())) for _ in range(M)]
uf = UnionFind(N)
for i in range(M):
    uf.union(XYZ[i][0]-1,XYZ[i][1]-1)

print(uf.groupsize())

Submission status: Accepted

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
        else:
            self.p[y] = x

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

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

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

ans = N
uf = UnionFind(N)
for i in range(M):
    X, Y, _ = map(int, input().split())
    if not uf.is_same(X-1, Y-1):
        uf.union(X-1, Y-1)
        ans -= 1

print(ans)

Submission status: Accepted

Solution code:
class Node:
    def __init__(self):
        self.is_parent = True
        self.parent = None

def root(node):
    depth = 0
    while node.parent != None:
        node = node.parent
        depth += 1
    return node, depth

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

roots = [Node() for i in range(N)]
count = N

for i in range(M):
    x, y, z = map(int, input().split())
    x = roots[x-1]
    y = roots[y-1]
    if x.is_parent and y.is_parent:
            y.is_parent = False
            y.parent = x
            count -= 1
    else:
        root_x, depth_x = root(x)
        root_y, depth_y = root(y)
        if root_x != root_y:
            if depth_x >= depth_y:
                root_y.is_parent = False
                root_y.parent = root_x
                count -= 1
            else:
                root_x.is_parent = False
                root_x.parent = root_y
                count -= 1

print(count)

Submission status: Accepted

Solution code:
class Node:
    def __init__(self, val):
        self.num = val
        self.val = val
        self.is_parent = True
        self.parent = None

def root(node):
    depth = 0
    while node.parent != None:
        node = node.parent
        depth += 1
    return node, depth

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

roots = [Node(i) for i in range(N)]
count = N

for i in range(M):
    x, y, z = map(int, input().split())
    x = roots[x-1]
    y = roots[y-1]
    if x.is_parent and y.is_parent:
            y.is_parent = False
            y.parent = x
            count -= 1
    else:
        root_x, depth_x = root(x)
        root_y, depth_y = root(y)
        if root_x != root_y:
            if depth_x >= depth_y:
                root_y.is_parent = False
                root_y.parent = root_x
                count -= 1
            else:
                root_x.is_parent = False
                root_x.parent = root_y
                count -= 1

print(count)

Submission status: Accepted

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

class MergeFind:
    def __init__(self, N):
        self.par = list(range(N))
        self.num_sets = 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]

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return
        else:
            self.par[rx] = ry
            self.num_sets -= 1

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

    def get_num_sets(self):
        return self.num_sets

def solve3():
    N, M = [int(_) for _ in raw_input().split()]
    Tree = MergeFind(N)
    for i in range(M):
        Xi, Yi, Zi = [int(_) for _ in raw_input().split()]
        Xi -= 1
        Yi -= 1
        Tree.unite(Xi, Yi)
    print Tree.get_num_sets()

if __name__ == '__main__':
    solve3()

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10**6)

class UnionFind:
    def __init__(self, N):
        self.par = list(range(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]

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

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

def solve2():
    N, M = [int(_) for _ in raw_input().split()]
    Tree = UnionFind(N)
    for i in range(M):
        Xi, Yi, Zi = [int(_) for _ in raw_input().split()]
        Xi -= 1
        Yi -= 1
        Tree.unite(Xi, Yi)
    UnionSet = set()
    for i in range(N):
        UnionSet.add(Tree.root(i))
    print len(UnionSet)

if __name__ == '__main__':
    solve2()

Submission status: Accepted

Solution code:
import bisect
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
par=[-1]*n
def find(x):
  if par[x]<0:
    return x
  else:
    par[x]=find(par[x])
    return par[x]
def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return False
  else:
    if par[x]>par[y]:
      x,y=y,x
    par[x]+=par[y]
    par[y]=x
    return True
def same(x,y):
  return find(x)==find(y)
def size(x):
  return -par[find(x)]
for i in range(m):
  x,y,z=map(int,input().split())
  unite(x-1,y-1)
par.sort()
print(bisect.bisect_left(par,0))

Submission status: Accepted

Solution code:
import collections
import sys
sys.setrecursionlimit(100000)
def root(X):
	if cards[X]==X:
		return X
	else:
		cards[X]=root(cards[X])
		return cards[X]
def unite(X,Y):
	x=root(X)
	y=root(Y)
	if x==y:
		return
	else:
		cards[x]=y
def same(X,Y):
	return root(X)==root(Y)
def show(x):
	print(cards[x])
		
N,M=[int(i) for i in input().split()]
cards=[i for i in range(N+1)]
for i in range(M):
	X,Y,Z=[int(i) for i in input().split()]
	if same(X,Y):
		pass
	else:
		unite(X,Y)
a=[]
for i in range(1,N+1):
	a.append(root(cards[i]))
print(len(set(a)))

Submission status: Accepted

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

n, m = map(int, input().split())
t = [[] for i in range(n)]
c = [-1 for i in range(n)]
for line in sys.stdin:
    x, y ,z = map(int, line.split())
    x -= 1
    y -= 1
    t[x].append(y)
    t[y].append(x)


def dfs(num, depth):
    if c[num] != -1:
        return
    else:
        c[num] = depth
    for i in t[num]:
        dfs(i, depth)


cnt = 0
for i in range(n):
    if c[i] == -1:
        cnt += 1
        dfs(i, cnt)

print(cnt)

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)]
        self.sizes = [1 for _ in range(size)]

    
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])
    
    def root(self, x):
        if self.parent[x] == x:
            return x
        else:
            root_x = self.root(self.parent[x])
            self.parent[x] = root_x
            return root_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.sizes[y] += self.sizes[x]
        else:
            self.parent[y] = x
            self.sizes[x] += self.sizes[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 size(self, x):
        return self.sizes[self.find(x)]

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

u = UnionFind(N)

for m in range(M):
    xyz = [int(i)-1 for i in input().split()]
    u.unite(xyz[0],xyz[1])

for n in range(N):
    u.root(n)

print(len(list(set(u.parent))))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n)
        self.total = 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 same_check(self, x, y):
        return self.find(x) == self.find(y)
    def unite(self, x, y):
        if self.same_check(x, y):
            return
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.total -= 1
        else:
            self.par[y] = x
            self.total -= 1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
n,m = map(int, input().split())
union = UnionFind(n)
for i in range(m):
    x,y,z = map(int, input().split())
    union.unite(x-1, y-1)
print(union.total)

Submission status: Accepted

Solution code:
def c_show(graph,x):
    seen = set()
    nodes = set([x])
    while nodes:
        cur = nodes.pop()
        seen.add(cur)
        nodes |= set(graph[cur]) - seen
    return seen

def c_cnt(graph,n): 
    done = set()
    cnt = 0
    for x in range(n):
        if x not in done:
            done |= c_show(graph,x)
            cnt += 1
    return cnt
  
n,m = map(int, input().split())
g = [list() for _ in range(n)]
for _ in range(m):
    x,y,z = map(int, input().split())
    g[x-1].append(y-1)
    g[y-1].append(x-1)
print(c_cnt(g,n))

Submission status: Accepted

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

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


def dfs(num, depth):
    if c[num] != -1:
        return
    else:
        c[num] = depth
    for i in t[num]:
        dfs(i, depth)


cnt = 0
for i in range(n):
    if c[i] == -1:
        cnt += 1
        dfs(i, cnt)

print(max(c))

Submission status: Accepted

Solution code:
n, m = map(int,input().split())

par = [i for i in range(n+1)]
rank = [0] * (n+1)

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

def unite(x,y):
  root_x = find(x)
  root_y = find(y)
  if rank[root_x] != rank[root_y]:
    par[min(root_x,root_y)] = max(root_x,root_y)
  else:
    par[root_y] = root_x
    rank[root_x] += 1


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

for i in range(n):
  roo.append(find(i+1))

print(len(set(roo))-1)

Submission status: Accepted

Solution code:
from collections import deque

def solve():
    N, M = [int(_) for _ in raw_input().split()]
    to = [ [] for i in range(N) ]
    for i in range(M):
        Xi, Yi, Zi = [int(_) for _ in raw_input().split()]
        Xi -= 1
        Yi -= 1
        to[Xi].append(Yi)
        to[Yi].append(Xi)
    union = [None] * N
    que = deque()
    union_cnt = 0
    for i in range(N):
        if union[i] is not None:
            continue
        union_cnt += 1
        # BFS
        que.append(i)
        while len(que) > 0:
            vi = que.popleft()
            union[vi] = union_cnt
            for j in range(len(to[vi])):
                fri = to[vi][j]
                if union[fri] is not None:
                    continue
                union[fri] = union_cnt
                que.append(fri)
    print str(union_cnt)

if __name__ == '__main__':
    solve()

Submission status: Accepted

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


def root(x):
    if c[x] == x:
        return x
    else:
        c[x] = root(c[x])
        return c[x]


def uni(x,y):
    rx = root(x)
    ry = root(y)
    c[ry] = rx


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

for i in range(n):
    root(i)

print(len(set(c)))

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, N):
        #頂点0からNまでを扱う
        self.table = [-1] * (N+1)      #頂点から繋がる先のtable, -1が根を表す
        self.sizetable = [1] * (N+1) #根から繋がる要素数, 根以外は0
    def root(self, x): # 根を探す
        while self.table[x] >= 0: #繋がる先を辿っていく
            x = self.table[x]
        return x
    def unite(self, x, y): #頂点x, yをまとめる
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry: #根が同じならまとめなくていい
            #多い方にまとめる
            if self.sizetable[rx] < self.sizetable[ry]:
                rx, ry = ry, rx
            self.sizetable[rx] += self.sizetable[ry] #要素数を移す
            self.sizetable[ry] = 0 #小さい方の根のフラグを消す
            self.table[ry] = rx      #小さい方の根だったものを大きい方につなぐ
        return
    def same(self, x, y): #同じ木にいるか
        return self.root(x) == self.root(y)
    def size(self, x): #頂点xが所属する木の要素数
        return self.sizetable[self.root(x)]
    
#####
N, M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
    ui, vi, wi = map(int, input().split())
    uf.unite(ui, vi)
print(sum([t > 0 for t in uf.sizetable[1:]]))

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,size):
        self.table=[-1]*size
    def root(self,x):
        while self.table[x]>=0:
            x=self.table[x]
        return x
    def unite(self,x,y):
        s1=self.root(x)
        s2=self.root(y)
        if s1!=s2:
            if self.table[s1]>self.table[s2]:
                s1,s2=s2,s1
            self.table[s1]+=self.table[s2]
            self.table[s2]=s1
        return
    def same(self,x,y):
        return self.root(x)==self.root(y)
    def size(self,x):
        return -self.table[self.root(x)]
    
#####
N, M = map(int, input().split())
uf = UnionFind(N+1)
for i in range(M):
    ui, vi, wi = map(int, input().split())
    uf.unite(ui, vi)
print(sum([t < 0 for t in uf.table[1:]]))

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

    def ans(self):
        print(len(set(self.par))-1)

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

for i in range(m):
    a,b,c=map(int,input().split())
    uf.union(a,b)

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

Submission status: Accepted

Solution code:
class UnionFindTree:  # 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 = map(int, input().split())

tree = UnionFindTree(N)

for i in range(1, M+1):
    x, y, w = map(int, input().split())
    tree.union(x, y)

root_list = []

for i in range(1, N+1):
    root_list.append(tree.find(i))

root_list = list(set(root_list))

print(len(root_list))

Submission status: Accepted

Solution code:
class DisjointSet:
    def __init__(self):
        self.rank = {}
        self.p = {}

    def makeSet(self, x):
        self.p[x] = x
        self.rank[x] = 0

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

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if x == y:
            return
        if(self.rank[x] > self.rank[y]):
            self.p[y] = x
        else:
            self.p[x] = y
            if(self.rank[x] == self.rank[y]):
                self.rank[y] += 1

    def findSet(self, x):
        if(x != self.p[x]):
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]



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

ds = DisjointSet()
for i in range(N):
    ds.makeSet(i+1)

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

ans = set()

for i in range(1, N+1):
    a = ds.findSet(i)
    ans.add(a)

print(len(ans))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        
    def find_root(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find_root(self.par[x])
        return self.par[x]
    
    def union(self, x, y):
        x_root = self.find_root(x)
        y_root = self.find_root(y)
        if x_root != y_root:
            if self.rank[x_root] < self.rank[y_root]:
                x_root, y_root = y_root, x_root
            if self.rank[x_root] == self.rank[y_root]:
                self.rank[x_root] += 1
            self.par[y_root] = x_root
            
    def is_same(self, x, y):
        x_root = self.find_root(x)
        y_root = self.find_root(y)
        return x_root == y_root
    def num(self):
        c=set()
        for i in range(len(u.par)):
            c.add(self.find_root(i))
        return len(c)
    
n,m=map(int,input().split())
xyz=[list(map(int,input().split())) for _ in range(m)]
xy=[[x-1,y-1] for x,y,z in xyz]
u=UnionFind(n)
for x,y in xy:
    u.union(x,y)
print(u.num())

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        
    def find_root(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find_root(self.par[x])
        return self.par[x]
    
    def union(self, x, y):
        x_root = self.find_root(x)
        y_root = self.find_root(y)
        if x_root != y_root:
            if self.rank[x_root] < self.rank[y_root]:
                x_root, y_root = y_root, x_root
            if self.rank[x_root] == self.rank[y_root]:
                self.rank[x_root] += 1
            self.par[y_root] = x_root
            
    def is_same(self, x, y):
        x_root = self.find_root(x)
        y_root = self.find_root(y)
        return x_root == y_root
    
n,m=map(int,input().split())
xyz=[list(map(int,input().split())) for _ in range(m)]
xy=[[x-1,y-1] for x,y,z in xyz]
u=UnionFind(n)
for x,y in xy:
    u.union(x,y)
res=[]
for i in range(n):
    res.append(u.find_root(i))
print(len(set(res)))