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

Solution (Python):



""" convenient functions




"""

import sys
sys.setrecursionlimit(10**7)
from itertools import accumulate, combinations, permutations, product 

from math import factorial, ceil, floor
def factorize(n):
    """return the factors of the Arg and count of each factor
    
    Args:
        n (long): number to be resolved into factors
    
    Returns:
        list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
    """
    fct = []  
    b, e = 2, 0  
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
def combinations_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    
    if n < 0 or r < 0:
        raise Exception('combinations_count(n, r) not defined when n or r is negative')
    if n - r < r: r = n - r
    if r < 0: return 0
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combinations_with_replacement_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    if n < 0 or r < 0:
        raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
    elif n == 0:
        return 1
    else:
        return combinations_count(n + r - 1, r)
from bisect import bisect_left, bisect_right
from collections import deque, Counter, defaultdict 
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest 
from copy import deepcopy, copy 
from operator import itemgetter


from functools import reduce
def chmin(x, y):
    """change minimum
    if x > y, x = y and return (x, True).
    convenient when solving problems of dp[i]
    
    Args:
        x (long): current minimum value
        y (long): potential minimum value
    
    Returns:
        (x, bool): (x, True) when updated, else (x, False)
    """
    if x > y:
        x = y
        return (x, True)
    else:
        return (x, False)
def chmax(x, y):
    """change maximum
    if x < y, x = y and return (x, True).
    convenient when solving problems of dp[i]
    
    Args:
        x (long): current maximum value
        y (long): potential maximum value
    
    Returns:
        (x, bool): (x, True) when updated, else (x, False)
    """
    if x < y:
        x = y
        return (x, True)
    else:
        return (x, False)

from fractions import gcd 
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)



INF = 10 ** 18
MOD = 10 ** 9 + 7
modpow = lambda a, n, p = MOD: pow(a, n, p) 
def modinv(a, p = MOD):
    
    
    return modpow(a, p-2, p)
def modinv_list(n, p = MOD):
    if n <= 1:
        return [0,1][:n+1]
    else:
        inv_t = [0,1]
        for i in range(2, n+1):
            inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
        return inv_t
def modfactorial_list(n, p = MOD):
    if n == 0:
        return [1]
    else:
        l = [0] * (n+1)
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l[i] = tmp
        return l
def modcomb(n, k, fac_list = [], p = MOD):
    
    
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if len(fac_list) <= n:
        a = factorial(n) % p
        b = factorial(k) % p
        c = factorial(n-k) % p
    else:
        a = fac_list[n]
        b = fac_list[k]
        c = fac_list[n-k]
    return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
def modadd(a, b, p = MOD):
    return (a + b) % MOD
def modsub(a, b, p = MOD):
    return (a - b) % p
def modmul(a, b, p = MOD):
    return ((a % p) * (b % p)) % p
def moddiv(a, b, p = MOD):
    return modmul(a, modpow(b, p-2, p))

""" initialize variables and set inputs

    
    

    
    
    
    
    

    
    
    
    

    
    
"""


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

""" how to treat input







"""





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

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

"""memo: how to use defaultdict of list

Dic = defaultdict(list)

Dic[x].append(y)

for k, v in Dic.items():
"""

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

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

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

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

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

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


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

print(uf.indep()-1)

Solution (Python):



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

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

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

check = [False for _ in range(N)]

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

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




sys.setrecursionlimit(100000)
class UnionFind():
    '''UnionFind木'''
    def __init__(self,n):
        self.data = [-1] * n
    
    def unite(self, x, y):
        '''x と y を結合'''
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.data[x] < self.data[y]:
            x, y = y, x  
        self.data[x] += self.data[y]
        self.data[y] = x
    
    def find(self, x):
        '''ノード x の親を返す'''
        if self.data[x] < 0:
            return x
        self.data[x] = self.find(self.data[x])
        return self.data[x]

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


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

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




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


if __name__ == '__main__':
    
    ABC126_E()

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

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

Solution (Python):



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


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

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

    ds[x0] = x
    return x


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

    return False


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

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

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

if __name__ == '__main__':
    main()

Solution (Python):

import bisect
from collections import defaultdict
import math

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

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

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

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

if __name__ == '__main__':
    main()

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

Solution (Python):

from collections import deque

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

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

vertices = [False] * N

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

print(count)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.v = [-1 for _ in range(n)]  

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

    def unite(self, x, y):  
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if -self.v[x] < -self.v[y]:  
            x, y = y, x  
        self.v[x] += self.v[y]  
        self.v[y] = x  

    def root(self, x):
        return self.v[x] < 0  

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

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


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

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

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

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

U = [0]*(N+1)

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

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

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

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

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

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


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

Solution (Python):


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

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

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

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

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

Solution (Python):
import sys
sys.setrecursionlimit(100000)

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

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

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

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

    print(len(rlist))

if __name__ == '__main__':
    main()

Solution (Python):
class UnionFindNode(object):

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

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

    def is_root(self):
        return not self.parent_

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

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

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

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

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

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

Solution (Python):
import collections

class UnionFind:
    def __init__(self, n):
        self.par = [k for k 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 tree_count(self):
        l = collections.Counter(self.par[1:])
        return len(l)


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)
    

for j in range(1,n+1):
    _ = uf.find(j)

print(uf.tree_count())

Solution (Python):
class UnionFind(object):
    def __init__(self, nodes):
        self.__parents = {node: None for node in nodes}

    def union(self, a, b):
        root_of_a = self.find(a)
        root_of_b = self.find(b)
        if root_of_a != root_of_b:
            self.__parents[root_of_a] = root_of_b

    def find(self, a):
        if self.__parents[a] is None:
            return a
        root = self.find(self.__parents[a])
        self.__parents[a] = root
        return root

    @property
    def roots(self):
        return set(node for node, parent in self.__parents.items() if parent is None)

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

xyzs = [tuple(map(int, input().split())) for _ in range(m)]

union_find = UnionFind(range(1, n+1))
for x, y, z in xyzs:
    union_find.union(x, y)

print(len(union_find.roots))

Solution (Python):
N, M = [int(i) for i in input().strip().split(' ')]

a = {}
for i in range(M):
  X, Y, _ = [int(i) for i in input().strip().split(' ')]
  if X not in a: a[X] = set()
  if Y not in a: a[Y] = set()
  a[X].add(Y)
  a[Y].add(X)

len_a = len(a)


def test(key_set):
  tmp = set()
  for key in key_set:
    if key in a:
      tmp = tmp.union(a[key])
      del a[key]

  
  return tmp


counter = 0


while len(a) > 0:
  
  
  key, key_set = a.popitem()
  
  tmp = test(key_set)
  while len(tmp) > 0:
    tmp = test(tmp)
  
  counter += 1

print(counter + N - len_a)

Solution (Python):
class UF():
  def __init__(self, N):
    self._parent=[n for n in range(0, N)]
    self._size=[1] * N

  def find_root(self, x):
    if self._parent[x]==x:return x
    self._parent[x]=self.find_root(self._parent[x])
    return self._parent[x]

  def unite(self, x, y):
    gx=self.find_root(x)
    gy=self.find_root(y)
    if gx==gy:return

    if self._size[gx]<self._size[gy]:
      self._parent[gx]=gy
      self._size[gy]+=self._size[gx]
    else:
      self._parent[gy]=gx
      self._size[gx]+=self._size[gy]

  def size(self, x):
    return self._size[self.find_root(x)]

  def samegroup(self, x, y):
    return self.find_root(x)==self.find_root(y)

  def groupnum(self):
    N=len(self._parent)
    ans=0
    for i in range(N):
      if self.find_root(i)==i:
        ans+=1
    return ans

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

Solution (Python):
class UF():
  def __init__(self, N):
    self._parent = [n for n in range(0, N)]
    self._size = [1] * N

  def find_root(self, x):
    if self._parent[x] == x: return x
    self._parent[x] = self.find_root(self._parent[x])
    return self._parent[x]

  def unite(self, x, y):
    gx = self.find_root(x)
    gy = self.find_root(y)
    if gx == gy: return

    if self._size[gx] < self._size[gy]:
      self._parent[gx] = gy
      self._size[gy] += self._size[gx]
    else:
      self._parent[gy] = gx
      self._size[gx] += self._size[gy]

  def size(self, x):
    return self._size[self.find_root(x)]

  def samegroup(self, x, y):
    return self.find_root(x) == self.find_root(y)

  def groupnum(self):
    N = len(self._parent)
    ans = 0
    for i in range(N):
      if self.find_root(i) == i:
        ans += 1
    return ans

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

Solution (Python):
class UF():
    def __init__(self, N):
        self._parent = [n for n in range(0, N)]
        self._size = [1] * N

    def find_root(self, x):
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x])
        return self._parent[x]

    def unite(self, x, y):
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def size(self, x):
        return self._size[self.find_root(x)]

    def samegroup(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def groupnum(self):
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

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

Solution (Python):

"""
E - 1 or 2
https://atcoder.jp/contests/abc126/tasks/abc126_e

"""
import sys


class DisjointSet(object):
    def __init__(self, n):
        self.rank = [0] * n
        self.p = list(range(n))
        self.size = [1] * n

    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 self.rank[x] > self.rank[y]:
            self.size[self.p[x]] += self.size[self.p[y]]
            self.p[y] = self.findSet(x)
        else:
            self.size[self.p[y]] += self.size[self.p[x]]
            self.p[x] = self.findSet(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]

def solve(N, M, hints):
    d = DisjointSet(N+1)
    for x, y, z in hints:
        d.unite(x, y)
    for i in range(1, N+1):
        d.findSet(i)

    ans = set(d.p[1:])
    return len(ans)


def main(args):
    N, M = map(int, input().split())
    hints = [[int(i) for i in input().split()] for _ in range(M)]
    ans = solve(N, M, hints)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):

"""
E - 1 or 2
https://atcoder.jp/contests/abc126/tasks/abc126_e

"""
import sys


class DisjointSet:
    def __init__(self, n):
        self.p = list(range(n))

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

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

    def unite(self, i, j):
        i = self.root(i)
        j = self.root(j)
        if j >= i:
            self.p[j] = i
        else:
            self.p[i] = j


def solve(N, M, hints):
    d = DisjointSet(N+1)
    for x, y, z in hints:
        d.unite(x, y)
    for i in range(1, N+1):
        d.root(i)

    ans = set(d.p)
    ans.discard(d.p[0])
    return len(ans)


def main(args):
    N, M = map(int, input().split())
    hints = [[int(i) for i in input().split()] for _ in range(M)]
    ans = solve(N, M, hints)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):
n,m=map(int,input().split())
a=[list(map(int,input().split()))[:2]for i in range(m)]
b=[i for i in range(n+1)]
c=[1]*(n+1)
def root(x):
    if b[x]==x:
        return x
    x=b[x]
    return root(x)
def unite(x,y):
    x=root(x)
    y=root(y)
    if x!=y:
        if c[x]>c[y]:
            b[y]=x
            c[x]+=1
        else:
            b[x]=y
            c[y]+=1
for i,j in a:
    unite(i,j)
for i in range(1,n+1):
    b[i]=root(i)
print(len(set(b[1:])))

Solution (Python):
def search(n):
    idx = n
    while A[n-1] != n:
        n = A[n-1]
    A[idx-1] = n

    return n

N, M = list(map(int, input().split()))
A = [i for i in range(1, N+1)]
ans = 0

for i in range(M):
    X, Y, Z = list(map(int, input().split()))
    X_root, Y_root = search(X), search(Y)

    if X_root != Y_root:
        A[X_root-1] = Y_root
        ans += 1

print(N-ans)

Solution (Python):
class UnionFind():

    def __init__(self, n):
        self.n = n
        self.root = [-1] * (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 False
        if self.Size(x) < self.Size(y):
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x

        return True

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

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

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

Uni = UnionFind(N)

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

roots = set()
cnt = 0
for i in range(1, N+1):
    r = Uni.Find_Root(i)
    if r not in roots:
        cnt += 1
        roots.add(r)

print(cnt)

Solution (Python):

class UnionFindTree():
    def __init__(self, N):
        self.parent = [-1]*(N+1)
        self.rank = [1]*(N+1)
        self.size = [1]*(N+1)
        self.count = 0

    def find(self, i):
        if self.parent[i] == -1:
            group = i
        else:
            group = self.find(self.parent[i])
            self.parent[i] = group
        return group

    def unite(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.rank[px] == self.rank[py]:  
                self.rank[px] += 1
            elif self.rank[px] < self.rank[py]:
                px, py = py, px

            self.parent[py] = px
            self.size[px] += self.size[py]
            self.count += 1

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

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


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

UFT = UnionFindTree(N)
for x, y, z in A:
    x -= 1
    y -= 1
    UFT.unite(x, y)
print(N - UFT.count)

Solution (Python):
from collections import deque

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

checked = [False] * N

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

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

component = 0

for c , check in enumerate(checked) :
    if check :
        continue

    stack = deque([c])
    component += 1

    while stack :
        current = stack.pop()

        if checked[current] :
            continue

        checked[current] = True
        for v in edge[current] :
            if not checked[v] :
                stack.append(v)

print(component)