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
        self.rank=[0]*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.rank[x]<self.rank[y]:
            self.parents[y]+=self.parents[x]
            self.parents[x]=y
        else:
            self.parents[x]+=self.parents[y]
            self.parents[y]=x

            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1

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

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

    def group_count(self):
        count=0
        for e in self.parents:
            if e<0: count+=1
        return count

from sys import stdin
def main():
    
    readline=stdin.readline
    n,m=map(int,readline().split())
    uf=UnionFind(n)
    for i in range(m):
        x,y,z=map(int,readline().split())
        x-=1
        y-=1
        uf.union(x,y)
    print(uf.group_count())

if __name__=="__main__":
    main()

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
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())

def main():
    n, m = LI()
    uf = UnionFind(n)
    for _ in range(m):
        x, y, z = LI()
        x -= 1
        y -= 1
        uf.union(x, y)
    cnt = set()
    for i in range(n):
        cnt.add(uf.find(i))
    print(len(cnt))

main()

Solution (Python):


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


N, M = LI()
XYZ = [LI() for _ in range(M)]


class Node:

    def __init__(self, num):
        self.num = num
        self.parent = None

    def root(self):
        if self.parent is None:
            return self
        self.parent = self.parent.root()
        return self.parent


class UnionFind:

    def __init__(self, n):
        self.n = n
        self.nodes = [Node(i) for i in range(n)]
        self.groups = {i: 1 for i in range(n)}
    
    def union(self, x, y):
        x = self.nodes[x].root().num
        y = self.nodes[y].root().num
        if x == y:
            return
        if self.groups[x] < self.groups[y]:
            x, y = y, x
        self.groups[x] += self.groups[y]
        del self.groups[y]
        self.nodes[y].parent = self.nodes[x]
    
    def same(self, x, y):
        a = self.nodes[x].root()
        b = self.nodes[y].root()
        return True if a == b else False
    

def main():
    uf = UnionFind(N)
    for x, y, z in XYZ:
        uf.union(x - 1, y - 1)
    
    ans = len(uf.groups)
    print(ans)


if __name__ == "__main__":
    main()

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

def unite(x,y):
  x,y=find(x),find(y)
  if x!=y:
    if x>y:
        x,y=y,x
    par[x]+=par[y] 
    par[y]=x 

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

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

N, M = map(int, input().split())
par = [-1] * N

def main():
  for i in range(M):
    x, y, z = map(int, input().split())
    unite(x-1, y-1)
  ans = set([])
  for i in range(N):
    ans.add(find(i))
  print(len(ans))
if __name__ ==  "__main__":
  main()

Solution (Python):
from collections import defaultdict
dic = defaultdict(list)
n, m = map(int, input().split())
seen = set()
l = [None] * n
for i in range(m):
    x, y, _ = map(int, input().split())
    dic[x-1].append(y-1)
    dic[y-1].append(x-1)
for i in range(n):
    if i in seen:
        continue
    seen.add(i)
    l[i] = i
    stack = [i]
    while stack:
        q = stack.pop()
        for child in dic[q]:
            if child not in seen:
                seen.add(child)
                l[child] = i
                stack.append(child)
print(len(set(l)))

Solution (Python):
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)]

N,M=map(int,input().split())
uni=UnionFind(N)
L=[]
for i in range(M):
    l=list(map(int,input().split()))
    L.append(l)
for i in range(M):
    uni.Unite(L[i][0],L[i][1])
x=-1
for i in range(N+1):
    if uni.root[i]<0:
        x+=1
print(x)

Solution (Python):
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 same(self, x, y):
        return self.find(x) == self.find(y)
 
    def count_member(self, x):
        return -self.p[self.find(x)]

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

for i in range(m):
  x,y,z=map(int,input().split())
  if not(uf.same(x,y)):
    uf.union(x,y)
    ans-=1
  uf.union(x,y)

print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")











N,M = map(int,input().split())
fr = [[] for _ in range(N)]
for _ in range(M):
    x,y,z = map(int,input().split())
    fr[x-1].append(y-1)
    fr[y-1].append(x-1)
used = [-1]*N 
renketu = []
index = 0
def dfs(fr,cur,parent,index,li):
    children = fr[cur]
    for chi in children:
        if chi == parent or used[chi] != -1:
            continue
        used[chi] = index
        li.append(chi)
        dfs(fr,chi,cur,index,li)
for i in range(N):
    if used[i] != -1:
        continue
    li = [i]
    used[i] = index
    dfs(fr,i,-1,index,li)
    index += 1
    renketu.append(li)
n = len(renketu)
print(n)

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

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 
    if self.root[x] > self.root[y]:
      x, y = y, x
    self.root[x] += self.root[y]
    self.root[y] = x 
  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)]
  def Members(self, x): 
    return [i for i in range(self.n) if self.Find_Root(i)==self.Find_Root(x)]
  def Roots(self): 
    return [i for i, x in enumerate(self.root) if x < 0]
  def Group_Count(self): 
    return len(self.Roots())

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

roots = {i:0 for i in range(1, N+1)}
for i in range(1, N+1):
  r = uf.Find_Root(i)
  roots[r] += 1 

ans = 0
for v in roots.values():
  if v > 0:
    ans += 1
print(ans)

Solution (Python):

import sys
try:
    from typing import List
except ImportError:
    pass


sys.setrecursionlimit(1000000)


def solve(N: int, M: int, X: "List[int]", Y: "List[int]", Z: "List[int]"):
    par = list(range(N))

    def getpar(n: int):
        if par[n] == n:
            return n
        par[n] = getpar(par[n])
        return par[n]

    def union(a: int, b: int):
        par[getpar(b)] = getpar(a)

    for Xi, Yi in zip(X, Y):
        Xi -= 1
        Yi -= 1
        union(Xi, Yi)

    print(len({getpar(i) for i in range(N)}))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    X = [int()] * (M)  
    Y = [int()] * (M)  
    Z = [int()] * (M)  
    for i in range(M):
        X[i] = int(next(tokens))
        Y[i] = int(next(tokens))
        Z[i] = int(next(tokens))
    solve(N, M, X, Y, Z)


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

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

N, M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
    X, Y, _ = map(int, input().split())
    X -= 1
    Y -= 1
    uf.union(X, Y) 
print(uf.group_count())

Solution (Python):
n, m = map(int, input().split())
g = [[] for i in range(n)]
for i in range(m):
  u,v,z=map(int, input().split())
  g[u-1].append((u-1, v-1, z))
  g[v-1].append((v-1,u-1,z))
count = 0
renketu_list = [-1]*n
stack = []
for i in range(n):
  if renketu_list[i] == -1:
    count += 1
    renketu_list[i] = count
    while len(g[i]) > 0:
      stack.append(g[i].pop())
    while len(stack) > 0:
      u,v,z=stack.pop()
      if renketu_list[v] == -1:
        renketu_list[v] = count
        while len(g[v])>0:
          stack.append(g[v].pop())

print(count)

Solution (Python):

def find(x):
    global par
    if par[x]<0:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
        
def unite(x,y):
    x,y=find(x),find(y)
    global par
    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 size(x):
    return -par[find(x)]
def same(x,y):
    return find(x)==find(y)

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

root=[]
for i in range(n):
  root.append(find(i))
r=set(root)
print(len(r))

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()}
      
N, M = map( int, input().split() )
uf = UnionFind( N )
for i in range( M ):
  a, b, z = map( int, input().split() )
  uf.union( a - 1, b - 1 )
print( uf.group_count() )

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

pr = [[] for i in range(n+1)]

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

def grouping(n,arr):
    gr = []
    al = [-1 for i in range(n+1)]
    q = queue.Queue()
    for i in range(1,n+1):
        if al[i] == 0:
            continue
        else:
            gi = []
            q.put(i)
            al[i] = 0
            while not q.empty():
                qi = q.get()
                gi.append(qi)
                for ai in arr[qi]:
                    if al[ai] < 0:
                        q.put(ai)
                        al[ai] = 0
            gr.append(gi)
    return gr

print(len(grouping(n,pr)))

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * 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):
        xx = self.find(x)
        yy = self.find(y)
        if self.rank[xx] < self.rank[yy]:
            self.par[xx] = yy
        else:
            self.par[yy] = xx
            if self.rank[xx] == self.rank[yy]:
                self.rank[xx] += 1
        self.par[x] = self.find(x)
        self.par[y] = self.find(y)
                
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
n, m = map(int, input().split())
union = UnionFind(n)

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

for i in range(n):
    union.find(i)
print(len(set(union.par)))

Solution (Python):
import collections





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

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

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

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

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

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







tank = set([])
for i in range(1,n+1):
    tank.add(uf.find(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 are_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) == self.n]

    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())
uni = UnionFind(N)
for i in range(M):
    x, y, z = map(int, input().split())
    uni.union(x-1, y-1)
print(uni.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 are_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) == self.n]

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

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

def update(v):
    for nv in G[v]:
        if seen[nv]:
            continue
        seen[nv]=1
        update(nv)

N,M=map(int,input().split())
seen=[0]*N
G=[[] for i in range(N)]
for i in range(M):
    X,Y,Z=map(int,input().split())
    X,Y=X-1,Y-1
    G[X].append(Y)
    G[Y].append(X)
ans=0
for i in range(N):
    if(seen[i]):
        continue
    ans+=1
    seen[i]=1
    update(i)
print(ans)

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

def update(v):
    for nv in con[v]:
        if seen[nv]:
            continue
        seen[nv]=1
        update(nv)

N,M=map(int,input().split())
seen=[0]*N
con=[[] for i in range(N)]
cnt=[[i,0] for i in range(N)]
for i in range(M):
    X,Y,Z=map(int,input().split())
    X,Y=X-1,Y-1
    con[X].append(Y)
    con[Y].append(X)
    cnt[X][1]+=1
    cnt[Y][1]+=1
cnt.sort(key=lambda x:x[1],reverse=True)
ans=0
for i,a in cnt:
    if(seen[i]):
        continue
    ans+=1
    seen[i]=1
    update(i)
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 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())

def main():
    N, M = map(int, input().split())
    uni = UnionFind(N)
    for _ in range(M):
        x, y, z = map(int, input().split())
        x, y = x-1, y-1
        uni.union(x, y)
    print(uni.group_count())
main()

Solution (Python):
from collections import deque,defaultdict

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

G = defaultdict(list)
for i in range(M):
    G[data[i][0]].append(data[i][1])
    G[data[i][1]].append(data[i][0])

D = [0]+[-1]*(N)

c = 0
for i in range(1,N+1):
    if D[i] != -1:
        continue
    else:
        q = deque([i])
        while q:
            n = q.pop()
            D[n] = 0
            for d in G[n]:
                if D[d] != -1:
                    continue
                else:
                    q.append(d)
        c += 1

print(c)

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 is_same(self, x, y):
        return self.find(x) == self.find(y)

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
def LILI(n): return [LI() for _ in range(n)]
INF = 10 ** 18
MOD = 10 ** 9 + 7

'''MEMO:
1 or 2 が書かれている。
与えられた x, y, z について,
z が偶数なら A_x + A_y は偶数。つまり (1, 1) or (2, 2)
z が奇数なら上記は奇数。つまり (1, 2) or (2, 1)
最小何枚で確実にすべてわかるか。

結局 union-find して独立なグラフの個数を求める問題か。
'''

import collections
import itertools
import operator

class UnionFind:
    def __init__(self, elems=None):
        class KeyDict(dict):  
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()  
        self.rank = collections.defaultdict(int)  
        self.size_ = collections.defaultdict(lambda: 1)  

        if elems is not None:
            for elem in elems:
                _, _ = self.parent[elem], self.rank[elem]

    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
        if self.rank[x] < self.rank[y]:  
            x, y = y, x
        self.parent[y] = x  
        self.size_[x] += self.size_[y]
        if self.rank[x] == self.rank[y]:  
            self.rank[x] += 1

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

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

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield [x for x, _ in group]


def main(): 
    N, M = LI()
    uf = UnionFind()
    for _ in range(M):
        X, Y, Z = LI()
        uf.unite(X, Y)
    for i in range(1, N+1):
        uf.unite(i,i)
    print(len(list(uf.grouper())))

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

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

import sys
input = sys.stdin.readline
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.group_count())

Solution (Python):
import numpy as np
from scipy.sparse import csr_matrix, csgraph
N, M = map(int, input().split())
print(csgraph.connected_components(csr_matrix(([1] * M, (np.array([tuple(map(lambda n: int(n) - 1, input().split()[:2])) for _ in range(M)], dtype=np.int32).T)), shape=(N, N), dtype=np.int32), return_labels=False))

Solution (Python):
import numpy as np
from scipy.sparse import csr_matrix, csgraph
N, M = map(int, input().split())
row, column, _ = np.array([tuple(map(lambda n: int(n) - 1, input().split())) for _ in range(M)], dtype=np.int32).T
matrix = csr_matrix(([1] * M, (row, column)), shape=(N, N), dtype=np.int32)
print(csgraph.connected_components(matrix)[0])

Solution (Python):
n,m=map(int,input().split())
xy=[list(map(int,input().split())) for _ in range(m)]
ans=[1]*n
a=list(range(n))
def find(a, x):
    if a[x] != x:
        a[x] = find(a, a[x])
    return a[x]
 
 
def unite(a, x, y):
    x = find(a, x)
    y = find(a, y)
    if x != y:
        a[x] = min(x, y)
        a[y] = a[x]
 
for i,j ,k in xy:
    unite(a,i-1,j-1)
q=[]
for i in range(n):
    p=find(a,i)
    q.append(p)
print(len(set(q)))

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 same(self, x, y):
        return self.find(x) == self.find(y)


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

ans = 0
for i in range(1, N+1):
  if uf.parents[i] < 0:
    ans += 1
print(ans)

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

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

seen = [False] * (N+1)

last_start = -1
counter = 0
while True:
    start = last_start + 1
    while seen[start]:
        start += 1

    if start == N:
        break

    if path[start]:
        stack = [start]
        while stack:
            pos = stack.pop()
            seen[pos] = True
            for next_node in path[pos]:
                if not seen[next_node]:
                    stack.append(next_node)
    else:
        seen[start] = True

    counter += 1
    last_start = start

print(counter)