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: Time Limit Exceeded

Solution code:
from math import *



N,K = tuple(map(int,input().split()))
groupId_V = [v for v in range(N)]
vs_groupId = {v:[v] for v in range(N)}

for _ in range(K):
    u,v,w = tuple(map(int,input().split()))
    u-=1
    v-=1
    uGroupId = groupId_V[u]
    vGroupId = groupId_V[v]
    if uGroupId==vGroupId:
        continue
    uFriends = vs_groupId[uGroupId]
    vFriends = vs_groupId[vGroupId]
    for vFriend in vFriends:
        groupId_V[vFriend] = uGroupId
    vs_groupId[vGroupId] = []
    vs_groupId[uGroupId] = uFriends+vFriends

re = 0
for vs in vs_groupId.values():
    if len(vs) != 0:
        re += 1

print(re)

Submission status: Time Limit Exceeded

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 = [i]
        while q:
            u = q.pop()
            done.add(u)
            for v in g[u]:
                if v not in done:
                    q.append(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))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def dfs(graph, start, visited):
    stack = [start]
    visited.add(start)
    while stack:
        label = stack.pop(0)
        for node in g[label]:
            if node not in visited:
                visited.add(node)
                stack.append(node)
    return visited


g = {i: [] for i in range(1, N + 1)}
for i in range(M):
    x, y, z = map(int, input().split())
    g[x].append(y)
    g[y].append(x)
ans = 0
for i in range(1, N + 1):
    if i not in v:
        ans += 1
        dfs(g, i, v)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
d={i:[] for i in range(n)}
for i in range(m):
    x,y,z=map(int,input().split())
    d[x-1].append(y-1)
    d[y-1].append(x-1)
cnt=0
c=set()
for i in range(n):
    if i in c:
        continue
    c.add(i)
    q=[i]
    while(q):
        p=q.pop(0)
        l=d[p]
        for x in l:
            if x in c:
                continue
            q.append(x)
            c.add(x)
    cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:

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

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

cnt = 0
unvisited = set(range(N))
while unvisited:
    u0 = next(iter(unvisited))
    unvisited.discard(u0)
    stack = [u0]
    while stack:
        u = stack.pop()
        for v in adj[u]:
            if v in unvisited:
                unvisited.discard(v)
                stack.append(v)
    cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import sys
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


input = sys.stdin.readline
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.union(x, y)
print(uf.group_count())

Submission status: Accepted

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


par = [-1]*(n)
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]
def same(x,y):
    return find(x) == find(y)
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    else:
      if par[x] > par[y]:x,y = y,x
      par[x] += par[y]
      par[y] = x
def size(x):
    return -par[find(x)]


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


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

Submission status: Accepted

Solution code:
def abc126e():
    class UnionFind():
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n

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

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

            if x == y:
                return

            if self.parents[x] > self.parents[y]:
                x, y = y, x

            self.parents[x] += self.parents[y]
            self.parents[y] = x

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

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

        def members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def roots(self):
            return [i for i, x in enumerate(self.parents) if x < 0]

        def group_count(self):
            return len(self.roots())

        def all_group_members(self):
            return {r: self.members(r) for r in self.roots()}

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

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

    print(uft.group_count())
abc126e()

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

      
N,K=map(int,input().split())  
uf = UnionFind(N)
for i in range(K):
  a,b,c=map(int,input().split())
  uf.union(a-1,b-1)
print(uf.group_count())

Submission status: Accepted

Solution code:
from networkx.utils import UnionFind
def main():
    n,m=map(int, input().split())
    uf=UnionFind()
    for i in range(n):
        _=uf[i]
    for _ in range(m):
        x,y,z=map(int, input().split())
        uf.union(x-1,y-1)
    print(len(list(uf.to_sets())))
    
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
xy=[[] for _ in range(n+1)]
for _ in range(m):
    x,y,z=map(int,input().split())
    xy[x].append(y)
    xy[y].append(x)

from collections import deque

visited=[0]*(n+1)
count=0

for i in range(1,n+1):
    if visited[i]==0:
        stack=deque()
        stack.append(i)
        visited[i]+=1
        while stack:
            a=stack.pop()
            for j in xy[a]:
                if visited[j]==0:
                    visited[j]+=1
                    stack.append(j)
        count+=1
print(count)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
xy=[[] for _ in range(n+1)]
for _ in range(m):
    x,y,z=map(int,input().split())
    xy[x].append(y)
    xy[y].append(x)

from collections import deque

visited=[0]*(n+1)
count=0

for i in range(1,n+1):
    if visited[i]==0:
        stack=deque()
        stack.append(i)
        visited[i]+=1
        while stack:
            a=stack.pop()
            for j in xy[a]:
                if visited[j]==0:
                    visited[j]+=1
                    stack.append(j)
        count+=1
print(count)

Submission status: Accepted

Solution code:
# Reference: https://note.nkmk.me/python-union-find/
class UnionFind:
    # if x is root: self.parents[x] = -(the number of the group nodes)
    # else: self.parents[x] = the parent of x
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # return the parent of x
    def find(self, x):
        history = []
        while self.parents[x] >= 0:
            history.append(x)
            x = self.parents[x]
        for node in history:
            self.parents[node] = x
        return x

    # merge the group of x and the group of y
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    # return the size of the group of x
    def size(self, x):
        return -self.parents[self.find(x)]

    # return whether x and y in a same group
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # return [all roots]
    # O(n)
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    # return the number of groups
    # O(n)
    def group_count(self):
        return len(self.roots())

from sys import stdin
input = stdin.buffer.readline

def main():
    n, m = map(int, input().split())

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

    print(uf.group_count())

main()

Submission status: Accepted

Solution code:
# ABC126 E
f=lambda:map(int,input().split())
N,M=f()

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

    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):
        x = self.find_root(x)
        y = self.find_root(y)
        if(x == y):
            return 
        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
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
                
    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]
    
uf=UnionFind(N)
for _ in [0]*M:
    x,y,z=f()
    uf.unite(x,y)
    
res=0
for i in range(N):
    if uf.root[i+1]<0:
        res+=1
print(res)

Submission status: Accepted

Solution code:
class Union_Find:
  def __init__(self,n=0):
    self.vertices=n
    self.mother=[-1 for i in range(self.vertices)]
    self.size_temp=[1 for i in range(self.vertices)]
  
  def root(self,x):
    normalize_v=[]
    while x!=-1:
      normalize_v.append(x)
      y=x
      x=self.mother[x]
    for i in normalize_v[:-1]:
      self.mother[i]=y
    return y
  
  def union(self,x,y):
    root_x=self.root(x)
    root_y=self.root(y)
    if root_x!=root_y:
      self.mother[root_x]=root_y
      self.size_temp[root_y]+=self.size_temp[root_x]
  
  def find(self,x,y):
    if self.root(x)==self.root(y):
      return True
    else:
      return False
  
  def size(self,x):
    return self.size_temp[self.root(x)]


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

c=0
for i in range(n):
  c+=i==uf.root(i)
print(c)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
tree = [-1 for i in range(N)]

def root(x):
    if tree[x] < 0:
        return x
    tree[x] = root(tree[x])
    return tree[x]
def find(x, y):
    return root(x) == root(y)
def union(x, y):
    x = root(x)
    y = root(y)
    if x != y:
        if tree[x] < tree[y]:
            x, y = y, x
        tree[x] += tree[y]
        tree[y] = x
        return 1
    return 0

cnt = 0
for i in range(M):
    x, y, z = map(int, input().split())
    cnt += union(x - 1, y - 1)
print(N - cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(3*10**5)

N, M = map(int,input().split())
adj = [[] for i in range(N+1)]
for i in range(M):
	u, v, w = map(int,input().split())
	adj[u].append(v)
	adj[v].append(u)

vis = [False for i in range(N+1)]
def bfs(s):
	frontier = [s]
	ptr = 0
	while ptr < len(frontier):
		u = frontier[ptr]
		if not vis[u]:
			vis[u] = True
			for v in adj[u]:
				if not vis[v]:
					frontier.append(v)
		ptr += 1
ans = 0
for u in range(1,N+1):
	if not vis[u]:
		ans += 1
		bfs(u)

print(ans)

Submission status: Accepted

Solution code:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

N, M = rl()
Q = []
for i in range(M):
	x, y, z = rl()
	x, y = x-1, y-1
	Q.append((x, y, z))

ids = [i for i in range(N)]
def find(x):
	if x != ids[x]:
		p = find(ids[x])
		ids[x] = p
	return ids[x]

def unite(x, y):
	x = find(x)
	y = find(y)
	ids[x] = y

for x, y, z in Q:
	unite(x,y)
for i in range(N):
	find(i)
print(len(Counter(ids)))

Submission status: Accepted

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

import sys
sys.setrecursionlimit(10**9) #再帰の上限をあげる

root=[-1 for i in range(n+1)] #自分が親ならグループの人数のマイナス倍を、そうでないなら（元）親の番号を示す
dep=[1]*(n+1)
def r(x):   #親は誰？
    if root[x]<0:
        return x
    else:
        root[x]=r(root[x])
        return root[x]

def unite(x,y):
    x=r(x)
    y=r(y)
    if x==y:
        return
    if dep[x]==dep[y]:
        dep[x]+=1
    if dep[x]<dep[y]:
        x,y=y,x
    root[x]+=root[y]
    root[y]=x

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


g=[0]*(n+1)
for i in range(1,n+1):
    g[r(i)]+=1
ans=0
for i in range(n+1):
    if g[i]>0:
        ans+=1
print(ans)

Submission status: Accepted

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

import sys
sys.setrecursionlimit(10**9) #再帰の上限をあげる

root=[-1 for i in range(n+1)] #自分が親ならグループの人数のマイナス倍を、そうでないなら（元）親の番号を示す
dep=[1]*(n+1)
def r(x):   #親は誰？
    if root[x]<0:
        return x
    else:
        return r(root[x])

def unite(x,y):
    x=r(x)
    y=r(y)
    if x==y:
        return
    if dep[x]==dep[y]:
        dep[x]+=1
    if dep[x]<dep[y]:
        x,y=y,x
    root[x]+=root[y]
    root[y]=x

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


g=[0]*(n+1)
for i in range(1,n+1):
    g[r(i)]+=1
ans=0
for i in range(n+1):
    if g[i]>0:
        ans+=1
print(ans)

Submission status: Accepted

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

import sys
sys.setrecursionlimit(10**9) #再帰の上限をあげる

root=[-1 for i in range(n+1)] #自分が親ならグループの人数のマイナス倍を、そうでないなら（元）親の番号を示す

def r(x):   #親は誰？
    if root[x]<0:
        return x
    else:
        
        return r(root[x])

def unite(x,y):
    x=r(x)
    y=r(y)
    if x==y:
        return
    if root[x]>root[y]:
        x,y=y,x
    root[x]+=root[y]
    root[y]=x

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


g=[0]*(n+1)
for i in range(1,n+1):
    g[r(i)]+=1
ans=0
for i in range(n+1):
    if g[i]>0:
        ans+=1
print(ans)

Submission status: Accepted

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

import sys
sys.setrecursionlimit(10**9) #再帰の上限をあげる

root=[-1 for i in range(n+1)] #自分が親ならグループの人数のマイナス倍を、そうでないなら（元）親の番号を示す

def r(x):   #親は誰？
    if root[x]<0:
        return x
    else:
        root[x]=r(root[x])
        return root[x]

def unite(x,y):
    x=r(x)
    y=r(y)
    if x==y:
        return
    if root[x]<root[y]:
        x,y=y,x
    root[x]+=root[y]
    root[y]=x

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


g=[0]*(n+1)
for i in range(1,n+1):
    g[r(i)]+=1
ans=0
for i in range(n+1):
    if g[i]>0:
        ans+=1
print(ans)

Submission status: Accepted

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

import sys
sys.setrecursionlimit(10**9) #再帰の上限をあげる

root=[-1 for i in range(n+1)] #自分が親ならグループの人数のマイナス倍を、そうでないなら（元）親の番号を示す

def r(x):   #親は誰？
    if root[x]<0:
        return x
    else:
        root[x]=r(root[x])
        return root[x]

def unite(x,y):
    x=r(x)
    y=r(y)
    if x==y:
        return
    if root[x]>root[y]:
        x,y=y,x
    root[x]+=root[y]
    root[y]=x

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


g=[0]*(n+1)
for i in range(1,n+1):
    g[r(i)]+=1
ans=0
for i in range(n+1):
    if g[i]>0:
        ans+=1
print(ans)

Submission status: Accepted

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

import sys
sys.setrecursionlimit(10**9) #再帰の上限をあげる

root=[i for i in range(n+1)] #自分が親なら自身の番号を、そうでないなら（元）親の番号を示す

def r(x):   #親は誰？
    if root[x]==x:
        return x
    else:
        root[x]=r(root[x])
        return root[x]

def unite(x,y):
    x=r(x)
    y=r(y)
    if x==y:
        return
    if x>y:
        x,y=y,x
    root[y]=x

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

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

Submission status: Accepted

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

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

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

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return
        if self.parent[root_x] > self.parent[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_x] += self.parent[root_y]
        self.parent[root_y] = root_x

    def get_size(self, x):
        return -self.parent[self.find(x)]

    def get_root(self):
        return [i for i, root in enumerate(self.parent) if root < 0]


def main():
    n, m = map(int, input().split())
    uf = UnionFind(n)
    for _ in range(m):
        x, y, _ = map(lambda x: int(x) - 1, input().split())
        uf.union(x, y)
    print(len(uf.get_root()))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline()


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [-1] * n

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

        if self.par[x] > self.par[y]:
            x, y = y, x

        self.par[x] += self.par[y]
        self.par[y] = x


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

for _ in range(m):
    a, b, z = map(int, input().split())
    uf.unite(a - 1, b - 1)

cnt = 0
for x in uf.par:
    cnt += 1 if x < 0 else 0
print(cnt)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline()


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [-1] * n

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

        if self.par[x] > self.par[y]:
            x, y = y, x

        self.par[x] += self.par[y]
        self.par[y] = x


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

for _ in range(m):
    a, b, z = map(int, input().split())
    uf.unite(a - 1, b - 1)

res = [x for x in uf.par if x < 0]
print(len(res))

Submission status: Accepted

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

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

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

        self.par[x]=self.find(self.par[x])
        return self.par[x]

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

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

        self.grp-=1
        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 group_num(self):
        return self.grp



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

Submission status: Accepted

Solution code:
# UnionFind: https://note.nkmk.me/python-union-find/
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1] * (n + 1)
        
    def find(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.root[x] > self.root[y]:
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x
        
    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return -self.root[self.find(x)]

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

Submission status: Accepted

Solution code:
# UnionFind: https://note.nkmk.me/python-union-find/
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1] * (n + 1)
        
    def find(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.root[x] > self.root[y]:
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x
        
    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return -self.root[self.find(x)]

n, m = map(int, input().split())
cards = UnionFind(n)
for i in range(m):
    x, y, z = map(int, input().split())
    cards.unite(x, y)
print(len({i + 1 for i in range(n) if cards.root[i + 1] < 0}))

Submission status: Accepted

Solution code:
N,M=list(map(int,input().split()))
root=[i for i in range(N)]
height=[0]*N
def find(a):
   f=a
   if a==root[a]:
      return a
   while a!=root[a]:
      a=root[a]
   root[f]=a
   return a
def union(a,b):
   A=find(a)
   B=find(b)
   if A==B:
      return
   if height[A]>height[B]:
      root[B]=root[A]
   else:
      root[A]=root[B]
      if height[A]==height[B]:
         height[B]+=1

for i in range(M):
   a,b,c=map(int,input().split())
   a-=1;b-=1
   union(a,b)
l=[0]*N
for j in range(N):
   l[find(j)]+=1
print(N-l.count(0))

Submission status: Accepted

Solution code:
class UnionFind1:

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

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

    def unite(self, x, y):
        if self.same(x, y):
            return
        x = self.root(x)
        y = self.root(y)
        if self.par[x] > self.par[y]:
            x, y = y, x
        self.par[x] += self.par[y]
        self.par[y] = x

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

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


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

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

cost = 0
for i in range(1, n+1):
    if uf.root(i) == i:
        cost += 1

print(cost)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

for _ in range(M):
    x, y, z = map(int, input().split())
    Network.union(x-1, y-1)

print(Network.group_count())

Submission status: Accepted

Solution code:
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0]*size    
    def find(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def unite(self, x, y):
        x, y = self.find(x), 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())
uf = UnionFind(N)
for _ in range(M):
    x,y,z = map(int,input().split())
    uf.unite(x-1,y-1)
for i in range(N):
    uf.find(i-1)
s = set(uf.parent)
print(len(s))