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):
from collections import deque

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

seen = [False] * n
ans = 0
for i in range(n):
    if not seen[i]:
        seen[i] = True
        node = deque(graph[i])
        while node:
            v = node.popleft()
            if seen[v]:
                continue
            seen[v] = True
            node.extend(graph[v])
        ans += 1

print(ans)

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

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

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

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


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

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

n_tree = set(uf.root)
ans = len(n_tree) - 1
print(ans)

Solution (Python):
class Uf:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

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

        return self.p[x]

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

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

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

def main():
    n,m = map(int,input().split())
    ls = [[int(x) for x in input().split()] for _ in range(m)]
    uni = Uf(n+1)

    for i in range(m):
        a,b,c = ls[i]
        uni.unite(a,b)
    ans = 0
    for i in range(1,n+1):
        if i == uni.root(i):
            ans +=1
        else:
            pass
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter,defaultdict,deque
import sys
from itertools import permutations, combinations
from heapq import heappop, heappush

sys.setrecursionlimit(10**8)
mod = 10**9+7
    
def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return sorted([list(map(int, input().split())) for _ in range(n)])

def find(x): 
    if par[x]==x:
        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
    if rank[x]<rank[y]:
        par[x]=y
    else:
        par[y]=x
        if rank[x]==rank[y]:
            rank[x]+=1

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

def main():
    n,m = map(int,input().split()) 
    global par,rank
    par=[i for i in range(n)]  
    rank=[0 for _ in range(n)] 
    for _ in range(m):
        a,b,z = map(int,input().split())
        unite(a-1,b-1)
    dic=defaultdict(int)
    ans=0
    for i in range(n):
        if dic[find(i)]==0:
            ans+=1
            dic[find(i)]=1
    print(ans)
        
if __name__ == "__main__":
    main()

Solution (Python):
import sys

input = sys.stdin.readline

def search(x, y):
    while root[x] != x: x = root[x]
    while root[y] != y: y = root[y]
    return x, y

def rebuild(x, y, r):
    while root[x] != r: x, root[x] = root[x], r
    while root[y] != r: y, root[y] = root[y], r
        
N, M = map(int, input().split())

root = {i:i for i in range(1, N+1)}
size = {i:1 for i in range(1, N+1)}
ans = 0

for i in range(M):
    x, y, z = map(int, input().split())
    
    x_r, y_r = search(x, y)

    if x_r == y_r: continue
    
    root[y_r] = x_r
    size[x_r] += size[y_r]
    if size[x_r] > 10: rebuild(x, y, x_r)
    ans += 1

print(N-ans)

Solution (Python):
import sys

input = sys.stdin.readline


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)

print(sum(uf.root(j) for j in range(n)))

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

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 isSameGroup(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 range(M):
    x,y,z = map(int, input().split())
    uf.unite(x, y)
    
L = [0]*(N+1)
for i in range(1, N+1):
    r = uf.find_root(i)
    if L[r] == 0:
        L[r] = 1
        
print(sum(L))

Solution (Python):
N,M=map(int,input().split())
XYZ=[]
for i in range(M):
    X,Y,Z=map(int,input().split())
    XYZ.append([X,Y])

def find_root(root,x):
    y = root[x]
    if x == y:
        return x
    z = find_root(root,y)
    root[x] = z
    return z
 
def merge(root,size,x,y):
    x = find_root(root,x)
    y = find_root(root,y)
    if x == y:
        return
    sx,sy = size[x],size[y]
    if sx < sy:
        sx,sy = sy,sx
        x,y = y,x
    root[y] = x
    size[x] += sy
    
def UF_make(graph,n):
    Root=list(range(n+1))
    Size=[1] * (n+1)
    for i in range(len(graph)):
        merge(Root,Size,graph[i][0],graph[i][1])
    for i in range(n+1):
        Root[i] = find_root(Root,i)
    Root.pop(0)
    return Root

L=UF_make(XYZ,N)
print(len(set(L)))

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
n, m = [int(i) for i in sys.stdin.readline().split()]
parent = [i for i in range(n)]

def unite(a, b):
    root_a = find_root(a)
    parent[a] = root_a
    root_b = find_root(b)
    parent[b] = root_b
    if root_a != root_b:
        parent[root_b] = root_a

def find_root(a):
    ls = []
    while parent[a] != a:
        ls.append(a)
        a = parent[a]
    for l in ls:
        parent[l] = a
    return a


for i in range(m):
    x, y, z = [int(i) for i in sys.stdin.readline().split()]
    x -= 1
    y -= 1
    unite(x, y)

_set = set()
for i in range(n):
    _set.add(find_root(i))
print(len(_set))

Solution (Python):
import collections
class UnionFind:
    def __init__(self, max_size):
        self.parent = [i for i in range(max_size+1)]
        self.depth = [0 for _ in range(max_size+1)]
        self.cnt = [1 for i in range(max_size+1)]
    def find(self, x):
        deque = collections.deque()
        t = x
        while t != self.parent[t]:
            deque.append(t)
            t = self.parent[t]
        while deque:
            tmp = deque.pop()
            self.parent[tmp] = t
        return t
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.depth[x] < self.depth[y]:
            self.parent[x] = y
            self.cnt[y] += self.cnt[x]
        else:
            self.parent[y] = x
            self.cnt[x] += self.cnt[y]
            if self.depth[x] == self.depth[y]:
                self.depth[x] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def size(self, x):
        return self.cnt[self.find(x)]
n, m = map(int, input().split())
utree = UnionFind(n+10)
for _ in range(m):
    x, y, z = map(int, input().split())
    utree.unite(x, y)
s = {utree.find(i) for i in range(1, n+1)}
print(len(s))

Solution (Python):
import collections


class UnionFind:
    def __init__(self, max_size):
        self.parent = [i for i in range(max_size+1)]
        self.depth = [0 for _ in range(max_size+1)]
        self.cnt = [1 for i in range(max_size+1)]
    
    '''
    
    def find(self, x):
        t = x
        while t!=self.parent[t]:
            t = self.parent[t]
        self.parent[x]=t
        return t
    '''

    def find(self, x):
        de = collections.deque()
        t = x
        while t != self.parent[t]:
            de.append(t)
            t = self.parent[t]
        while de:
            tmp = de.pop()
            self.parent[tmp] = t
        return t

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.depth[x] < self.depth[y]:
            self.parent[x] = y
            self.cnt[y] += self.cnt[x]
        else:
            self.parent[y] = x
            self.cnt[x] += self.cnt[y]
            if self.depth[x] == self.depth[y]:
                self.depth[x] += 1

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

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


n, m = map(int, input().split())
utree = UnionFind(n+10)
for _ in range(m):
    x, y, z = map(int, input().split())
    utree.unite(x, y)
s = {utree.find(i) for i in range(1, n+1)}
print(len(s))

Solution (Python):
import collections


class UnionFind:
    def __init__(self, max_size):
        self.parent = [i for i in range(max_size+1)]
        self.depth = [0 for _ in range(max_size+1)]
        self.cnt = [1 for i in range(max_size+1)]
    
    '''
    
    def find(self, x):
        t = x
        while t!=self.parent[t]:
            t = self.parent[t]
        self.parent[x]=t
        return t
    '''

    def find(self, x):
        deque = collections.deque()
        t = x
        while t != self.parent[t]:
            deque.append(t)
            t = self.parent[t]
        while deque:
            tmp = deque.pop()
            self.parent[tmp] = t
        return t

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.depth[x] < self.depth[y]:
            self.parent[x] = y
            self.cnt[y] += self.cnt[x]
        else:
            self.parent[y] = x
            self.cnt[x] += self.cnt[y]
            if self.depth[x] == self.depth[y]:
                self.depth[x] += 1

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

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


n, m = map(int, input().split())
utree = UnionFind(n+10)
for _ in range(m):
    x, y, z = map(int, input().split())
    utree.unite(x, y)
s = {utree.find(i) for i in range(1, n+1)}
print(len(s))

Solution (Python):
import collections
class UnionFind:
    def __init__(self, max_size):
        self.parent = [i for i in range(max_size+1)]
        self.depth = [0 for _ in range(max_size+1)]
        self.cnt = [1 for i in range(max_size+1)]
    
    def find(self, x):
        de = collections.deque()
        t = x
        while t!=self.parent[t]:
            de.append(t)
            t = self.parent[t]
        while de:
            tmp = de.pop()
            self.parent[tmp] = t
        return t
    
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        elif self.depth[x]<self.depth[y]:
            self.parent[x] = y
            self.cnt[y] += self.cnt[x]
        else:
            self.parent[y] = x
            self.cnt[x]+=self.cnt[y]
            if self.depth[x]==self.depth[y]:
                self.depth[x]+=1
    def same(self, x, y):
        return self.find(x)==self.find(y)
    def size(self,x):
        return self.cnt[self.find(x)]

n,m = map(int,input().split())
utree = UnionFind(n+10)
for _ in range(m):
    x,y,z = map(int,input().split())
    utree.unite(x,y)
s = {utree.find(i) for i in range(1,n+1)}
print(len(s))

Solution (Python):
import collections
class UnionFind:
    def __init__(self, max_size):
        self.parent = [i for i in range(max_size+1)]
        self.depth = [0 for _ in range(max_size+1)]
        self.cnt = [1 for i in range(max_size+1)]
    
    def find(self, x):
        de = collections.deque()
        t = x
        while t!=self.parent[t]:
            de.append(t)
            t = self.parent[t]
        while de:
            tmp = de.pop()
            self.parent[tmp] = t
        return t
    
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        elif self.depth[x]<self.depth[y]:
            self.parent[x] = y
            self.cnt[y] += self.cnt[x]
        else:
            self.parent[y] = x
            self.cnt[x]+=self.cnt[y]
            if self.depth[x]==self.depth[y]:
                self.depth[x]+=1
    def same(self, x, y):
        return self.find(x)==self.find(y)
    def size(self,x):
        return self.cnt[self.find(x)]

n,m = map(int,input().split())
utree = UnionFind(n+10)
for _ in range(m):
    x,y,z = map(int,input().split())
    utree.unite(x,y)
s = {utree.find(i) for i in range(1,n+1)}
print(len(s))

Solution (Python):
class UnionFind:
    def __init__(self, max_size):
        self.parent = [i for i in range(max_size+1)]
        self.depth = [0 for _ in range(max_size+1)]
        self.cnt = [1 for i in range(max_size+1)]
    def find(self, x):
        t = x
        while t!=self.parent[t]:
            t = self.parent[t]
        self.parent[x]=t
        return t
    
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        elif self.depth[x]<self.depth[y]:
            self.parent[x] = y
            self.cnt[y] += self.cnt[x]
        else:
            self.parent[y] = x
            self.cnt[x]+=self.cnt[y]
            if self.depth[x]==self.depth[y]:
                self.depth[x]+=1
    def same(self, x, y):
        return self.find(x)==self.find(y)
    def size(self,x):
        return self.cnt[self.find(x)]

n,m = map(int,input().split())
utree = UnionFind(n+10)
for _ in range(m):
    x,y,z = map(int,input().split())
    utree.unite(x,y)
s = {utree.find(i) for i in range(1,n+1)}
print(len(s))

Solution (Python):
class UnionFind:
    def __init__(self, max_size):
        self.parent = [i for i in range(max_size+1)]
        self.depth = [0 for _ in range(max_size+1)]
        self.cnt = [1 for i in range(max_size+1)]
    def find(self, x):
        if self.parent[x]==x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x]) 
            return self.parent[x]
    
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        elif self.depth[x]<self.depth[y]:
            self.parent[x] = y
            self.cnt[y] += self.cnt[x]
        else:
            self.parent[y] = x
            self.cnt[x]+=self.cnt[y]
            if self.depth[x]==self.depth[y]:
                self.depth[x]+=1
    def same(self, x, y):
        return self.find(x)==self.find(y)
    def size(self,x):
        return self.cnt[self.find(x)]

n,m = map(int,input().split())
utree = UnionFind(n+10)
for _ in range(m):
    x,y,z = map(int,input().split())
    utree.unite(x,y)
s = {utree.find(i) for i in range(1,n+1)}
print(len(s))

Solution (Python):
class UnionFind:
    def __init__(self, max_size):
        self.parent = [i for i in range(max_size+1)]
        self.depth = [0 for _ in range(max_size+1)]
        self.cnt = [1 for i in range(max_size+1)]
    def find(self, x):
        t = x
        while t!=self.parent[t]:
            t = self.parent[t]
        self.parent[x]=t
        return t
    
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        elif self.depth[x]<self.depth[y]:
            self.parent[x] = y
            self.cnt[y] += self.cnt[x]
        else:
            self.parent[y] = x
            self.cnt[x]+=self.cnt[y]
            if self.depth[x]==self.depth[y]:
                self.depth[x]+=1
    def same(self, x, y):
        return self.find(x)==self.find(y)
    def size(self,x):
        return self.cnt[self.find(x)]

n,m = map(int,input().split())
utree = UnionFind(n+10)
for _ in range(m):
    x,y,z = map(int,input().split())
    utree.unite(x,y)
s = {utree.find(i) for i in range(1,n+1)}
print(len(s))

Solution (Python):
class UnionFind:
    def __init__(self, max_size):
        self.parent = [i for i in range(max_size+1)]
        self.depth = [0 for _ in range(max_size+1)]
        self.cnt = [1 for i in range(max_size+1)]
    def find(self, x):
        if self.parent[x]==x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x]) 
            return self.parent[x]
    
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        elif self.depth[x]<self.depth[y]:
            self.parent[x] = y
            self.cnt[y] += self.cnt[x]
        else:
            self.parent[y] = x
            self.cnt[x]+=self.cnt[y]
            if self.depth[x]==self.depth[y]:
                self.depth[x]+=1
    def same(self, x, y):
        return self.find(x)==self.find(y)
    def size(self,x):
        return self.cnt[self.find(x)]

n,m = map(int,input().split())
utree = UnionFind(n+10)
for _ in range(m):
    x,y,z = map(int,input().split())
    utree.unite(x,y)
s = {utree.find(i) for i in range(1,n+1)}
print(len(s))

Solution (Python):
class UnionFind:
    def __init__(self, max_size):
        self.parent = [i for i in range(max_size+1)]
        self.depth = [0 for _ in range(max_size+1)]
        self.cnt = [1 for i in range(max_size+1)]
    def find(self, x):
        if self.parent[x]==x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x]) 
            return self.parent[x]
    
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        elif self.depth[x]<self.depth[y]:
            self.parent[x] = y
            self.cnt[y] += self.cnt[x]
        else:
            self.parent[y] = x
            self.cnt[x]+=self.cnt[y]
            if self.depth[x]==self.depth[y]:
                self.depth[x]+=1
    def same(self, x, y):
        return self.find(x)==self.find(y)
    def size(self,x):
        return self.cnt[self.find(x)]

n,m = map(int,input().split())
utree = UnionFind(n+10)
for _ in range(m):
    x,y,z = map(int,input().split())
    utree.unite(x,y)
l = [utree.find(i) for i in range(1,n+1)]
print(len(set(l)))

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
n, m = map(int, input().split())
memo = [1 for _ in range(n)]
E = [[] for _ in range(n)]
for i in range(m):
    x, y, z = map(int, input().split())
    E[x-1].append(y-1)
    E[y-1].append(x-1)
def dfs(cur, pre):
    stack = deque([[cur, pre]])
    while stack:
        cur, pre = stack.pop()
        memo[cur] = 0
        for e in E[cur]:
            if e != pre and memo[e]:
                stack.append([e, cur])
ans = 0
for i in range(n):
    if memo[i]:
        dfs(i, -1)
        ans += 1
print(ans)

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
n, m = map(int, input().split())
memo = set(list(range(n)))
E = [[] for i in range(n)]
for i in range(m):
    x, y, z = map(int, input().split())
    E[x-1].append(y-1)
    E[y-1].append(x-1)
def dfs(cur, pre):
    stack = deque([[cur, pre]])
    while stack:
        cur, pre = stack.pop()
        memo.discard(cur)
        for e in E[cur]:
            if e != pre and e in memo:
                stack.append([e, cur])
ans = 0
for i in range(n):
    if i in memo:
        dfs(i, -1)
        ans += 1
print(ans)

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
n, m = map(int, input().split())
memo = set(list(range(n)))
E = [[] for i in range(n)]
for i in range(m):
    x, y, z = map(int, input().split())
    E[x-1].append(y-1)
    E[y-1].append(x-1)
def dfs(cur, pre):
    stack = deque([[cur, pre]])
    while stack:
        cur, pre = stack.pop()
        if pre != -1:
            memo.discard(cur)
        for e in E[cur]:
            if e != pre and e in memo:
                stack.append([e, cur])
ans = 0
while len(memo):
    cur = memo.pop()
    dfs(cur, -1)
    ans += 1
print(ans)

Solution (Python):
class UnionFind:
  
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.rank = [0]*n
    self.num = n
  def find(self, x):
    if self.par[x]==x:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]
  
  def unite(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    self.num -= 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 same(self, x, y):
    return self.find(x)==self.find(y)
  
  def psize(self):
    return self.num

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)
for i in range(N):
  m = union.find(i)
ans = set(union.par)
print(len(ans))

Solution (Python):
class UnionFind:
  
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.rank = [0]*n
    self.size = n
  def find(self, x):
    if self.par[x]==x:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]
  
  def unite(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    self.size -= 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 same(self, x, y):
    return self.find(x)==self.find(y)
  
  def size(self):
    return len(set(self.par))

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

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

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())
                     
uf = UnionFind(N)
for xyz in XYZ:
  x, y, z = xyz                       
  uf.union(x - 1, y - 1)
print(uf.group_count())

Solution (Python):
import sys
input = sys.stdin.readline

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 roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

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

def main():
    N, M = map(int, input().split())
    uni = UnionFind(N)
    for _ in range(M):
        X, Y, Z = map(int, input().split())
        X -= 1
        Y -= 1
        uni.union(X,Y)

    print(uni.group_count())



if __name__ == "__main__":
    main()

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.par = list(range(n))
        self.rank = [0] * n
        self.size = [1] * n

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

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

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


def p_e():
    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)
    ans = set()
    for i in range(n):
        ans.add(uf.find(i))
    print(len(ans))
    

if __name__ == '__main__':
    p_e()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n, m = map(int, input().split())
adjacent_list = [[] for i in range(n + 1)]
for i in range(m):
    x, y, z = map(int,input().split())
    adjacent_list[x].append(y)
    adjacent_list[y].append(x)

finished = set()
ans = 0
def dfs(node):
    global finished
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i)

while len(finished) != n:
    for i in range(1,n+1):
        if i not in finished:
            dfs(i)
            ans += 1
print(ans)

Solution (Python):

n,m = map(int,input().split())
pre = [i for i in range(n)]
ans = n
for _ in range(m):
  x,y,z = map(int,input().split())
  x -= 1
  y -= 1
  X = [x]
  Y = [y]
  while pre[x] != x:
    X.append(x)
    x = pre[x]
  while pre[y] != y:
    Y.append(y)
    y = pre[y]
  if x != y:
    ans -= 1
    for xx in X:
      pre[xx] = y
    for yy in Y:
      pre[yy] = y
    pre[x] = y

print(ans)

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

  def find(self, x):
    if self.parents[x] < 0:
      return x
    
    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 root_len(self):
    count = 0
    for i in self.parents:
      if i < 0:
        count += 1
    
    return count
    
n,m = map(int,input().split())

uf = UnionFind(n)

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

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

  def find(self, x):
    if self.parents[x] < 0:
      return x
    
    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 
    
    self.parents[y] = x
    
  def root_len(self):
    count = 0
    for i in self.parents:
      if i < 0:
        count += 1
    
    return count
    
n,m = map(int,input().split())

uf = UnionFind(n)

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