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

class UnionFind():
    
    
    def __init__(self, n):
        
        
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    
    """ノードxのrootノードを見つける"""
    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 Union(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
    
    """xとyが同じグループに所属するか"""
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
    
    """ノードxが属する木のサイズ"""
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    
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)
tank = set([])
for i in range(n):
    tank.add(uf.Find_Root(i))
print(len(tank))

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
        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())
A=UnionFind(n)
for i in range(m):
  x,y,z=map(int,input().split())
  A.union(x-1,y-1)
print(A.group_count())

Solution (Python):
import sys
input = sys.stdin.readline
 
n,m = map(int,input().split())
 



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

def unite(x,y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True


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


def size(x):
    return -par[find(x)]



par = [-1]*n


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

A = set()

for i in range(n):
    A.add(find(i))

print(len(A))

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)

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

visited = [False] * N

def dfs(u):
    if visited[u]:
        return

    visited[u] = True
    for v in edges[u]:
        if visited[v]:
            continue
        dfs(v)

ans = 0
for u in range(N):
    if visited[u]:
        continue
    ans += 1
    dfs(u)
print(ans)

Solution (Python):
N, M = (int(i) for i in input().split())
uf = [-1]*N
def parent(v):
    if uf[v] < 0:
        return v
    else:
        uf[v] = parent(uf[v])
        return uf[v]

def size(v):
    return -uf[parent(v)]

def union(u, v):
    pu = parent(u)
    pv = parent(v)
    if pu != pv:
        res = uf[pv] * uf[pu] 
        uf[pv] += uf[pu]
        uf[pu] = pv
    else:
        res = 0
    return res

for i in range(M):
    X, Y, Z = (int(i) for i in input().split())
    union(X-1, Y-1)
ans = 0
for i in range(N):
    if uf[i] < 0:
        ans += 1
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)


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())
XYZ = [list(map(int, input().split())) for _ in range(M)]

uf = UnionFind(N)

for x, y, z in XYZ:
    uf.union(x-1, y-1)

ans = uf.group_count()

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
        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(list(self.roots()))

N,M=map(int, input().split())
XYZ=[tuple(map(int, input().split())) for _ in range(M)]
UF=UnionFind(N)
for x,y,_ in XYZ:
    UF.union(x-1,y-1)
print(UF.group_count())

Solution (Python):
class UnionFindVerSize():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        
        self._parent = [n for n in range(0, N)]
        
        self._size = [1] * N

    def find_root(self, x):
        """ xの木の根(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):
        """ 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 get_size(self, x):
        """ xが属するグループのサイズ（個数）を返す """
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(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())
X=[0 for i in range(M)]
Y=[0 for i in range(M)]
Z=[0 for i in range(M)]
for i in range(0,M):
    X[i],Y[i],Z[i]=map(int,input().split())

u=UnionFindVerSize(N)
for i in range(0,M):
    u.unite(X[i]-1,Y[i]-1)
print(u.calc_group_num())

Solution (Python):


import sys

sys.setrecursionlimit(10**7)

def dfs(num,log):
    visited[num]=min(log,visited[num])
    for item in way[num]:
        if visited[item]==10**7:
            dfs(item,log)
    return 

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

visited=[10**7]*N
way=[[] for i in range(N)]
order=[]

for _ in range(M):
    X,Y,Z=map(int,input().split())
    X,Y=min(X,Y),max(X,Y)
    order.append([X-1,Y-1,Z])

order.sort(key=lambda x:(x[0],x[1]))

for item in order:
    way[item[0]].append(item[1])
    way[item[1]].append(item[0])
    
for i in range(N):
    dfs(i,i)

visited=list(set(visited))
print(len(visited))

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
        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())
uf = UnionFind(N)
for _ in range(M):
    x, y, z = map(int, input().split())
    uf.union(x-1, y-1)

print(uf.group_count())

Solution (Python):

def find_root(x):
    if parent[x] == x:
        return x
    else:
        return find_root(parent[x])



def unite(x, y):
    x = find_root(x)
    y = find_root(y)

    if x != y:
        if rank[x] < rank[y]:
            parent[x] = y
            size[y] += size[x]
        else:
            parent[y] = x
            size[x] += size[y]
            if rank[x] == rank[y]:
                rank[x] += 1



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


n, m = map(int, input().split())
xyz = [list(map(int, input().split())) for _ in range(m)]


parent = [i for i in range(n)]  
rank = [1] * n  
size = [1] * n  


edge = [[xyz[m - 1 - i][0] - 1, xyz[m - 1 - i][1] - 1] for i in range(m)]


res = []
for i in range(m):
    unite(edge[i][0], edge[i][1])

arr = [0] * n
for i in range(n):
    arr[i] = find_root(i)
print(len(set(arr)))

Solution (Python):
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
from fractions import gcd
from copy import deepcopy
import math
import queue
import numpy as np

Mod = 1000000007
import sys
sys.setrecursionlimit(1000000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): 
    n,m = map(int,input().split())
    un = UnionFind(n)
    xyz = [list(map(int,input().split())) for i in range(m)]
    for i in range(m):
        un.union(xyz[i][0]-1,xyz[i][1]-1)
    ans = 0
    for i in range(n):
        if un.findroot(i) == i:
            ans += 1
    print(ans)
if __name__ == "__main__":
    main()

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
        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())
uf = UnionFind(N)
for i in range(M):
    X, Y, Z = map(int, input().split())
    uf.union(X-1, Y-1)

ans = uf.group_count()
print(ans)

Solution (Python):
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
from fractions import gcd
from copy import deepcopy
import math
import queue
import numpy as np

Mod = 1000000007
import sys
sys.setrecursionlimit(1000000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): 
    n,m = map(int,input().split())
    un = UnionFind(n)
    xyz = [list(map(int,input().split())) for i in range(m)]
    for i in range(m):
        un.union(xyz[i][0]-1,xyz[i][1]-1)
    ans = 0
    for i in range(n):
        if un.findroot(i) == i:
            ans += 1
    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):
import sys
input=sys.stdin.readline
n,m = map(int, input().split())
xyz=[]
for i in range(m):
    tmp = list(map(int,input().split()))
    xyz.append(tmp)

link = [[] for _ in range(n)]
for tmp in xyz:
    link[tmp[0]-1].append(tmp[1]-1)
    link[tmp[1]-1].append(tmp[0]-1)

from collections import deque
Q = deque()

from collections import defaultdict
visited = defaultdict(int)
num=0
for i in range(n):
    if visited[i] != 0:
        continue
    num+=1

    Q.append(i)
    visited[i] = num

    while Q:
        now=Q.popleft()
        for nxt in link[now]:
            if visited[nxt] != 0:
                continue
            Q.append(nxt)
            visited[nxt]=num

ans=set()
for v in visited.values():
    ans.add(v)
print(len(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
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(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())
uf=UnionFind(n)
for i in range(m):
  x,y,z=map(int,input().split())
  uf.unite(x-1,y-1)
print(uf.group_count())

Solution (Python):
import sys



sys.setrecursionlimit(10 ** 9)

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



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

seen = [0] * (N + 1)

for X, Y, Z in XYZ:
    graph[X].append(Y)
    graph[Y].append(X)


def dfs(a):
    if seen[a] == 1:
        return
    else:
        seen[a] = 1
        for i in graph[a]:
            dfs(i)


ans = 0

for i in range(1, N + 1):
    if seen[i] == 1:
        continue
    else:
        dfs(i)
        ans += 1

print(ans)

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

class UnionFind(object):
    def __init__(self, n):
        self.parent={i:i for i in range(1,n+1)}
        self.size={i:1 for i in range(1,n+1)}
    def find(self, a):
        if self.parent[a]!=a:
            self.parent[a]=self.find(self.parent[a])
        return self.parent[a]
    def getsize(self, a):
        return self.size[self.find(a)]
    def unite(self, a, b):
        a=self.find(a)
        b=self.find(b)
        if a==b:return
        if self.size[a]>self.size[b]:
            self.size[a]+=self.size[b]
            self.parent[b]=a
        else:
            self.size[b]+=self.size[a]
            self.parent[a]=b
    def isunited(self, a, b):
        return self.find(a)==self.find(b)

uft = UnionFind(N)
for _ in range(M):
    x, y, z = map(int, input().split())
    uft.unite(x, y)
group = {uft.find(i) for i in range(1, N+1)}
print(len(group))

Solution (Python):
from collections import defaultdict, deque

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

d = [0]*(n+1)  
ddict = defaultdict(list)  
relation = [[i, 0] for i in range(1, n+1)]  
for _ in range(m):
    x, y, z = map(int, input().split())
    ddict[x].append(y)
    ddict[y].append(x)
    relation[x-1][1] += 1
    relation[y-1][1] += 1
    
relation.sort(reverse=True, key=lambda x: x[1])

ans = 0
for i, r in relation:
    
    if r >=1:  
        if d[i] == 0:  
            ans += 1
            d[i] = 1
            que = deque(ddict[i])  
            while que:
                s = que.popleft()
                if d[s] == 0:
                    d[s] = 1
                    que += ddict[s]                    
                else:  
                    continue
        else:  
            continue
            
    else:  
        ans += 1
        
print(ans)

Solution (Python):
from collections import deque

n,m = map(int,input().split())
remains = set(range(1,n+1))
edges = [[] for _ in range(n+1) ]

for i in range(m):
    x,y,z = map(int, input().split())
    edges[x].append(y)
    edges[y].append(x)

ans = 0
while(len(remains) > 0):
    ans += 1

    d = deque()
    d.append(remains.pop())
    while(len(d) > 0):
        tmp = d.pop()
        for i in edges[tmp]:
            if( i in remains):
                d.append(i)
                remains.remove(i)

print(ans)

Solution (Python):



















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

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

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

    def unite(self, A, B):
        
        
        A = self.root(A)
        B = self.root(B)

        
        if (A == B):
            return False

        
        if (self.size(A) < self.size(B)):
            A, B = B, A

        
        self.parent[A] += self.parent[B]  
        self.parent[B] = A  

        return True

    def is_in_same(self, A, B):
        return self.root(A) == self.root(B)

    def n_disjoint(self):
        
        return sum([x < 0 for x in self.parent])


import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


N, M = read_ints()
uf = UnionFind(N)
for m in range(M):
    x, y, z = read_ints()
    uf.unite(x - 1, y - 1)

print(uf.n_disjoint())

Solution (Python):
class UnionFind():
    def __init__(self, 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


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

print(sum([x < 0 for x in uf.parents]))

Solution (Python):
n, m = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(m):
  x, y, z = map(int, input().split())
  adj[x-1].append(y-1)
  adj[y-1].append(x-1)
opn = [True] * n
count = 0
for i in range(n):
  if opn[i]:
    count += 1
    opn[i] = False
    stack = [i]
    while stack:
      u = stack.pop()
      for v in adj[u]:
        if opn[v]:
          stack.append(v)
          opn[v] = False
print(count)

Solution (Python):
class union_find():
  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 main():
  N,M=map(int,input().split())
  box=union_find(N)
  for i in range(M):
    x,y,z=map(int,input().split())
    box.union(x-1,y-1)
  box.find(1)
  ans=0
  for i, x in enumerate(box.parents):
    if x<0:
      ans+=1
  print(ans)
main()

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

par=[-1]*(n+1)
def find(x):
    if par[x]<0:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def size(x):
    oya=find(x)
    return -par[oya]
def unite(x,y):
    if find(x)==find(y):
        return False
    else:
        if size(y)>size(x):
            y,x=x,y  
        oya_x=find(x)
        oya_y=find(y)
        par[oya_x]-=size(oya_y)  
        par[oya_y]=oya_x  
        return True

def is_same(x,y):
    return find(x)==find(y)
for _ in range(m):
    x,y,z=map(int,input().split())
    unite(x,y)
ans_set=set()
for i in range(1,n+1):
    ans_set.add(find(i))
print(len(ans_set))

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

class UnionFind():
  def __init__(self, n):
    self.par = [i for i in range(n)]

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

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

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

for i 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.root(i))
print(len(ans))

Solution (Python):

import numpy as np
import sys
sys.setrecursionlimit(100000)


class UnionFind:
    def __init__(self, size):
        
        
        self.table = [-1 for i in range(size)]

    def _find(self, x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x

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

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] >= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def get_ntree(self):
        res = 0
        for c in self.table:
            if c < 0:
                res += 1
        return res

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

    def get_nclass(self):
        done = []
        for x in range(len(self.table)):
            if x in done:
                continue
            while self.table[x] >= 0:
                done.append(x)
                x = self.table[x]

    def get_nodenum(self):
        res = []
        for t in self.table:
            if t < 0:
                res.append(-t)

        return res



def acinput():
    return list(map(int, input().split(" ")))



directions=np.array([[1,0],[0,1],[-1,0],[0,-1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def serch(x, count):
    
            

    for d in directions:
        nx = d+x
        
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count


N,M=acinput()

uf = UnionFind(N)

for i in range(M):
    tmp = acinput()
    uf.union(tmp[0]-1,tmp[1]-1)


print(uf.get_ntree())

Solution (Python):
import sys

n, m = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    x, y, z = map(int, sys.stdin.readline().split())
    graph[x].append(y)
    graph[y].append(x)

def main():
    to_check = set(range(1, n+1))
    checked = set()
    cnt = 0
    while to_check:
        queue = set([to_check.pop()])
        cnt += 1
        while queue:
            v = queue.pop()
            checked.add(v)
            to_check -= set([v])
            for u in graph[v]:
                if not u in checked:
                    queue.add(u)
    return cnt

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
import sys

n, m, *xyz = map(int, sys.stdin.read().split())
xyz = zip(*[iter(xyz)] * 3)

root = list(range(n+1))
height = [0] * (n + 1)

sys.setrecursionlimit(10**7)
def find_root(v):
    u = root[v]
    if u == v:
        return u
    w = find_root(u)
    root[v] = w
    return w

def unite(u, v):
    ru = find_root(u)
    rv = find_root(v)
    if ru == rv:
        return
    if height[u] >= height[v]:
        root[rv] = ru
        height[ru] = max(height[ru], height[rv] + 1)
    else:
        root[ru] = rv

def main():
    for x, y, z in xyz:
        unite(x, y)
    
    for i in range(1, n+1):
        find_root(i)

    return len(set(root[1:]))

if __name__ == '__main__':
    ans = main()
    print(ans)

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


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * 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 union(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
            self.size[y] += self.size[x]
            self.size[x] = 0
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


UF = UnionFind(N)
for i in range(M):
    x, y, z = map(int, input().split())
    x, y = x - 1, y - 1
    UF.union(x, y)
UF.all_find()


print(len(set(UF.par)))