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.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,y=self.find(x),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())
    
    
import sys
from functools import lru_cache
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def read():
  return int(readline())
def reads():
  return map(int, readline().split())
n,m=reads()
uf=UnionFind(n)
for i in range(m):
  x,y,z=reads()
  uf.unite(x-1,y-1)
print(uf.group_count())

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=list(map(int,input().split()))
tree=UnionFind(N+1)

for _ in range(M):
    X,Y,Z=list(map(int,input().split()))

    tree.union(X,Y)

print(tree.group_count()-1)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)


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

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

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx != ry:
            if self.r[rx] > self.r[ry]:
                rx, ry = ry, rx
            if self.r[rx] == self.r[ry]:
                self.r[ry] += 1
            self.p[ry] += self.p[rx]
            self.p[rx] = ry

    def count_roots(self):
        return sum(p < 0 for p in self.p)


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

Solution (Python):
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline

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

    g = tuple(set() for _ in range(N))
    for _ in range(M):
        x, y, _ = (int(x) - 1 for x in input().split())
        g[x].add(y)
        g[y].add(x)

    ans = 0
    checked = [False] * N
    for s in range(N):
        if checked[s]: continue
        checked[s] = True
        ans += 1

        dq = deque([s])
        while dq:
            v = dq.popleft()
            for u in g[v]:
                if checked[u]: continue
                checked[u] = True
                dq.append(u)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
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,y=self.find(x),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())
    uf=UnionFind(n)
    XYZ=[tuple(map(int,input().split())) for i in range(m)]
    for x,y,_ in XYZ:
        uf.unite(x-1,y-1)
    print(uf.group_count())


if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
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,y=self.find(x),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())
    uf=UnionFind(n)
    XYZ=[tuple(map(int,input().split())) for i in range(m)]
    for x,y,_ in XYZ:
        uf.unite(x-1,y-1)
    print(uf.group_count())


if __name__=='__main__':
    main()

Solution (Python):
n, m = map(int, input().split())
tree = [-i for i in range(n+1)]

for _i in range(m):
    x, y, z = map(int, input().split())
    while tree[x]>0:
        x = tree[x]
    while tree[y]>0:
        y = tree[y]
    x, y = sorted([x, y])
    if x==y:
        continue
    else:
        tree[y] = x
print(sum(1 for i in tree if i<0))

Solution (Python):
n, m = map(int, input().split())
tree = [-i for i in range(n+1)]

def search_root(num, tree=tree):
    if tree[num] < 0:
        return num
    else:
        tree[num] = search_root(tree[num])
        return tree[num]

for _i in range(m):
    x, y, z = map(int, input().split())
    x, y = sorted([search_root(x), search_root(y)])
    if x==y:
        continue
    else:
        tree[x] = y
print(sum(1 for i in tree if i<0))

Solution (Python):
n, m = map(int, input().split())
tree = [-i for i in range(n+1)]

def search_root(num, tree=tree):
    if tree[num] < 0:
        return num
    else:
        tree[num] = search_root(tree[num])
        return tree[num]

for _i in range(m):
    x, y, z = map(int, input().split())
    x, y = [search_root(x), search_root(y)]
    if x==y:
        continue
    else:
        tree[x] = y
print(sum(1 for i in tree if i<0))

Solution (Python):
n, m = map(int, input().split())
tree = [-i for i in range(n+1)]
rank = [1 for _i in range(n+1)]
def search_root(num, tree=tree):
    if tree[num] < 0:
        return num
    else:
        tree[num] = search_root(tree[num])
        return tree[num]

for _i in range(m):
    x, y, z = map(int, input().split())
    x, y = [search_root(x), search_root(y)]
    if x==y:
        continue
    else:
        if rank[x]<rank[y]:
            rank[y] += 1
            tree[x] = y
        else:
            rank[x] += 1
            tree[y] = x
print(sum(1 for i in tree if i<0))

Solution (Python):
n, m = map(int, input().split())
tree = [-i for i in range(n+1)]
rank = [1 for _i in range(n+1)]
def search_root(num, tree=tree):
    if tree[num] < 0:
        return num
    else:
        tree[num] = search_root(tree[num])
        return tree[num]

for _i in range(m):
    x, y, z = map(int, input().split())
    x, y = sorted([search_root(x), search_root(y)])
    if x==y:
        continue
    else:
        if rank[x]<rank[y]:
            rank[y] += 1
            tree[x] = y
        else:
            rank[x] += 1
            tree[y] = x
print(sum(1 for i in tree if i<0))

Solution (Python):
n, m = map(int, input().split())
tree = [-i for i in range(n+1)]
rank = [1 for _i in range(n+1)]
def search_root(num, tree=tree):
    if tree[num] < 0:
        return num
    else:
        tree[num] = search_root(tree[num])
        return tree[num]

for _i in range(m):
    x, y, z = map(int, input().split())
    x, y = sorted([search_root(x), search_root(y)])
    if x==y:
        continue
    else:
        if rank[x]<rank[y]:
            rank[y] += 1
            tree[x] = y
        else:
            rank[x] += 1
            tree[y] = x
print(sum(1 for i in tree if i<0))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
class UnionFind:
    
    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.length = [1 for _ in range(n)] 
        self.numberOfElements = n
    
    def makeSet(self, n):
        self.parents = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.length = [1 for _ in range(n)]
        self.numberOfElements = n

    
    def findRoot(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.findRoot(self.parents[x])
            return self.parents[x]

    
    def uniteNode(self, x, y):
        x = self.findRoot(x)
        y = self.findRoot(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parents[x] = y
            self.length[y] += self.length[x]
        else:
            self.parents[y] = x
            self.length[x] += self.length[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    
    def getLength(self, x):
        x = self.findRoot(x)
        return self.length[x]        

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

    
    def getNumberOfGroup(self):
        s = set()
        for i in range(self.numberOfElements):
            s.add(self.findRoot(i))
        return len(s)

def main():
    n, m = map(int, readline().split())
    uf = UnionFind(n)
    for _ in range(m):
        x, y, z = map(int, readline().split())
        uf.uniteNode(x-1, y-1)
    print(uf.getNumberOfGroup())
if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
class UnionFind:
    
    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.length = [1 for _ in range(n)] 
        self.numberOfElements = n
    
    def makeSet(self, n):
        self.parents = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.length = [1 for _ in range(n)]
        self.numberOfElements = n

    
    def findRoot(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.findRoot(self.parents[x])
            return self.parents[x]

    
    def uniteNode(self, x, y):
        x = self.findRoot(x)
        y = self.findRoot(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parents[x] = y
            self.length[y] += self.length[x]
        else:
            self.parents[y] = x
            self.length[x] += self.length[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    
    def getLength(self, x):
        x = self.findRoot(x)
        return self.length[x]        

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

    
    def getNumberOfGroup(self):
        s = set()
        for i in range(self.numberOfElements):
            s.add(self.findRoot(i))
        return len(s)

def main():
    n, m = map(int, readline().split())
    uf = UnionFind(n)
    for _ in range(m):
        x, y, z = map(int, readline().split())
        uf.uniteNode(x-1, y-1)
    print(uf.getNumberOfGroup())
if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.length = [1 for _ in range(n)] 

    def makeSet(self, n):
        self.parents = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.length = [1 for _ in range(n)]

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

    def getLength(self, x):
        x = self.find(x)
        return self.length[x]        

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


def main():
    n, m = map(int, readline().split())
    uf = UnionFind(n)
    for _ in range(m):
        x, y, z = map(int, readline().split())
        x-=1
        y-=1
        uf.unite(x, y)
    s = set()
    for i in range(n):
        s.add(uf.find(i))
    print(len(s))
if __name__ == '__main__':
    main()

Solution (Python):
def find_base_label(lookup_table, label):
    base_label = label
    while lookup_table[base_label] != base_label:
        base_label = lookup_table[base_label]
    return base_label


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

    lookup_table = list(range(n))
    for _ in range(m):
        x, y, z = map(int, input().split())

        base_label_1 = find_base_label(lookup_table, x - 1)
        base_label_2 = find_base_label(lookup_table, y - 1)

        if base_label_1 < base_label_2:
            lookup_table[base_label_2] = base_label_1
        elif base_label_2 < base_label_1:
            lookup_table[base_label_1] = base_label_2

    for i in range(n):
        lookup_table[i] = lookup_table[lookup_table[i]]

    print(len(set(lookup_table)))


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)

N, M = map(int, input().split())
unionfind = UnionFind(N + 1)
for _ in range(M):
    x, y, z = map(int, input().split())
    unionfind.union(x, y)
print(len([p for p in unionfind.parents if p < 0]) - 1)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(1000000)
n,m=map(int,input().split())

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

seen = [0 for i in range(n)]

def dfs(i):
    for nec in g[i]:
        if seen[nec]!=0:continue
        seen[nec]=1
        dfs(nec)

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

print(cnt)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class UnionFind():
    def __init__(self, n):
        self.n = n
        
        
        self.parents = [-1] * n
    def find(self, x):
        if 0 > self.parents[x]:
            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 0 > x]
    
    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()

tree = UnionFind(N)

for _ in range(M):
	X, Y, Z = MAP()
	tree.union(X-1, Y-1)

print(tree.group_count())

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class UnionFind():
    def __init__(self, n):
        self.n = n
        
        
        self.parents = [-1] * n
    def find(self, x):
        if 0 > self.parents[x]:
            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 0 > x]
    
    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()

tree = UnionFind(N)
for _ in range(M):
	X, Y, Z = MAP()
	tree.union(X-1, Y-1)

print(tree.group_count())

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

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

A = [[] for _ in range(N)]
for i in range(M):
  a,b,c = map(int,input().split())
  a -=1; b-=1
  A[a].append(b)
  A[b].append(a)


reach = [-1 for _ in range(N)] 
def dfs(v):
  if reach[v] != -1:
    return
  else:
    reach[v] = 1
  for u in A[v]:
    dfs(u)
    
test = 0    
for i in range(N):
  if reach[i] == -1:
    dfs(i)
    test += 1
print(test)

Solution (Python):
def find(x):
    while G[x][0]!=x:
        x = G[x][0]
    return x
def union(x,y):
    xa = find(x)
    ya = find(y)
    if G[xa][1]>=G[ya][1]:
        G[ya][0] = xa
        G[xa][1] = max(G[xa][1],G[ya][1]+1)
    else:
        G[xa][0] = ya
        G[ya][1] = max(G[ya][1],G[xa][1]+1)
N,M = map(int,input().split())
G = {i:[i,0] for i in range(1,N+1)}
for _ in range(M):
    x,y,z = map(int,input().split())
    union(x,y)
hist = [0 for _ in range(N+1)]
for i in range(1,N+1):
    x = find(i)
    hist[x] = 1
print(sum(hist))

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


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

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

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


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


def unite(x,y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y              
        size[y] += size[x]      
    else:
        par[y] = x              
        size[x] += size[y]      
        if rank[x] == rank[y]:
            rank[x] += 1

for _ in range(M):
    x,y,z = map(int,input().split())
    unite(x,y)
ans = 0
for i in range(1,N+1):
    if par[i] == i:
        ans += 1
print(ans)

Solution (Python):
from collections import deque
N,M = map(int,input().split())
G = [[] for i in range(N+1)]
for i in range(M):
  x,y,z = map(int,input().split())
  G[x].append(y)
  G[y].append(x)

cnt = 0
seen = [False]*(N+1)
for i in range(1,N+1):
  if seen[i] == False:
    seen[i] = True
    cnt += 1
    d = deque([i])
    while len(d)>0:
      v = d.popleft()
      for j in G[v]:
        if seen[j] == False:
          seen[j] = True
          d.append(j)

print(cnt)

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


uni=UnionFind(N)
for i in range(M):
  x,y,z=map(int, input().split())
  uni.Unite(x-1,y-1)
L=[]
for i in range(N):
    a=uni.Find_Root(i)
    L.append(a)

print(len(set(L)))

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


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


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    


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)


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  



N, M = read_ints()
X, Y, Z = read_col(M)

uf = UnionFind(N)
for x, y in zip(X, Y):
    uf.unite(x - 1, y - 1)


cnt = Counter([])
for i in range(N):
    cnt[uf.root(i)] += 1
print(len(cnt))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    tree = [[] for _ in range(n)]
    for _ in range(m):
        x, y, _ = map(int, input().split())
        tree[x - 1].append(y - 1)
        tree[y - 1].append(x - 1)

    def dfs(v):
        for u in tree[v]:
            if visited[u]:
                continue
            else:
                visited[u] = True
                dfs(u)

    visited = [False for _ in range(n)]
    res = 0
    for i in range(n):
        if not visited[i]:
            res += 1
            visited[i] = True
            dfs(i)

    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys

input = sys.stdin.buffer.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 is_same(x, y):
    return find(x) == find(y)


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




par = [-1] * (n + 1)

for _ in range(m):
    x, y, z = map(int, input().split())
    unite(x, y)
ans = 0
for i in range(1, n + 1):
    if i == find(i):
        ans += 1
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

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

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

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

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

    
    def connect(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-1] += self.parent[B-1] 
        self.parent[B-1] = A 
        return True
    
    def same(self, A, B):
        if self.root(A) == self.root(B):
            return True
        else:
            return False

ans = N
uni = UnionFind(N + 1)
for _ in range(M):
    x, y, z = map(int, input().split())
    if uni.same(x, y):
        continue
    uni.connect(x, y)
    ans -= 1

print (ans)

Solution (Python):
class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.componentCount = size

    def root(self, index):
        if self.parent[index] == index:  
            return index
        rootIndex = self.root(self.parent[index])  
        self.parent[index] = rootIndex  
        return rootIndex

    def union(self, index1, index2):  
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2:  
            return

        self.componentCount -= 1  

        if self.height[root1] < self.height[root2]:
            self.parent[root1] = root2  
            self.size[root2] += self.size[root1]
        else:
            self.parent[root2] = root1  
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2]:
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2):
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index):
        return self.size[self.root(index)]

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

for _ in range(M):
    a, b, c = map(int, input().split())
    tree.union(a - 1, b - 1)

print(tree.componentCount)