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

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = list(range(n))
        self.ranks = [0 for _ in range(n)]

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

    def merge(self, x, y):
        x = self.get_root(x)
        y = self.get_root(y)
        if x != y:
            if self.ranks[x] < self.ranks[y]:
                self.parents[x] = y
            else:
                self.parents[y] = x
                if self.ranks[x] == self.ranks[y]:
                    self.ranks[x] += 1


n, m = ril()
uf = UnionFind(n)
for _ in range(m):
    x, y, z = ril()
    uf.merge(x - 1, y - 1)
for i in range(n):
    uf.get_root(i)
print(len(set(uf.parents)))

Solution (Python):
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = list(range(n))
        self.ranks = [0 for _ in range(n)]

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

    def merge(self, x, y):
        x = self.get_root(x)
        y = self.get_root(y)
        if x != y:
            if self.ranks[x] < self.ranks[y]:
                self.parents[x] = y
            else:
                self.parents[y] = x
                if self.ranks[x] == self.ranks[y]:
                    self.ranks[x] += 1


n, m = ril()
uf = UnionFind(n)
for _ in range(m):
    x, y, z = ril()
    uf.merge(x - 1, y - 1)
res = set()
for i in range(n):
    res.add(uf.get_root(i))
print(len(res))

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

class CountTree():
  def __init__(self,n):
    self.n=n
    self.parents=[-1]*n
  
  def find(self,x):
    if self.parents[x]<0:
      return x
    else:
      self.parents[x]=self.find(self.parents[x])
      return self.parents[x]
    
  def union(self,x,y):
    x=self.find(x)
    y=self.find(y)
    if x==y:
      return
    if self.parents[x]>self.parents[y]:
      x,y=y,x
    self.parents[x]+=self.parents[y]
    self.parents[y]=x
    
  def roots(self):
    return [i for i,x in enumerate(self.parents) if x<0]
  def group_count(self):
    return len(self.roots())
  
def solve():
  n,m=(int(i) for i in input().split())
  ct=CountTree(n)
  for i in range(m):
    x,y,z=[int(i) for i in input().split()]
    ct.union(x-1,y-1)
  print(ct.group_count())
solve()

Solution (Python):
class union_find():
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [1 for i in range(n + 1)]

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

        ret = self.find(self.par[c])
        self.par[c] = ret
        return ret

    def union(self, x, y):
        xr = self.find(x)
        yr = self.find(y)
        if xr == yr:
            return

        if self.rank[yr] > self.rank[xr]:
            self.par[xr] = yr
        else:
            self.par[yr] = xr
            if self.rank[xr] == self.rank[yr]:
                self.rank[xr] += 1

    def show(self):
        print('parent', self.par[1:])
        print('rank', self.rank[1:])

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

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


print([i == v for i, v in enumerate(uf.par)].count(True) - 1)

Solution (Python):
import sys


input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    alist = [set([]) for _ in range(N+1)]
    for _ in range(M):
        X, Y, _ = map(int, input().split())
        alist[X].add(Y)
        alist[Y].add(X)

    f = [0]*(N+1)
    f[0] = 1
    stack = []
    ans = 0
    for i in range(1, N+1):
        if len(alist[i]) and not f[i]:
            stack.append(i)
            ans += 1
        elif not len(alist[i]):
            ans += 1
        while len(stack):
            n = stack.pop()
            f[n] = 1
            for m in alist[n]:
                if not f[m]:
                    stack.append(m)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n, m = map(int, input().split())
    xyz = [list(map(int, input().split())) for _ in [0] * m]
    g = [[] for _ in [0] * n]
    for x,y,z in xyz:
        g[x - 1].append(y - 1)
        g[y - 1].append(x - 1)
    v = [False] * n
    cnt=0
    for i in range(n):
        if v[i]:
            continue
        cnt+=1
        q = [i]
        v[i]=True
        while q:
            j = q.pop()
            for k in g[j]:
                if v[k] == False:
                    q.append(k)
                    v[k]=True                
    print(cnt)
main()

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

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):
import sys
sys.setrecursionlimit(1000000)
n,m=map(int,input().split())
lb=[0 for i in range(n)]
l=[[] for i in range(n+1)]
for i in range(m):
  x,y,z=map(int,input().split())
  l[x].append(y)
  l[y].append(x)
def dfs(a,num):
  if lb[a-1]!=0:
    pass
  else:
    lb[a-1]=num
    for i in l[a]:
      dfs(i,num)
  return None
for i in range(n):
  dfs(i+1,i+1)
count=0
laa=[0 for i in range(n+1)]
for i in range(n):
  if lb[i]==0:
    count+=1
  elif laa[lb[i]]==0:
    count+=1
    laa[lb[i]]=1
  else:
    pass
print(count)

Solution (Python):
n, m = map(int, input().split())
a = [i for i in range(n + 1)]
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 in range(m):
  x,y,z=map(int,input().split())
  unite(a,x,y)
ans = -1
for i, v in enumerate(a):
    if i == v:
        ans += 1

print(ans)

Solution (Python):
n,m=map(int,input().split())
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)
A=UnionFind(n)
for i in range(m):
    a,b,c=map(int,input().split())
    A.union(a,b)
List=A.par
counter=0
for j in range(n+1):
    if List[j]==j:
        counter+=1
print(counter-1)

Solution (Python):
n,m=map(int,input().split())
xy=[]
data=[[] for i in range(n+1)]
for _ in range(m):
    x,y,z=map(int,input().split())
    xy.append([x,y])
    data[x].append(y)
    data[y].append(x)
flag=[0]*(n+1)
count=0
for i in range(1,n+1):
    if flag[i]==0:
        count+=1
        flag[i]=1
        que=[i]
        while que:
            h=que.pop()
            for u in data[h]:
                if flag[u]==0:
                    flag[u]=1
                    que.append(u)
print(count)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class UnionFind(object):
    def __init__(self,n):
        self.__par=list(range(n))
        self.__rank=[0]*n
        self.__size=[1]*n
        self.__connected=n

    def root(self,k):
        if(self.__par[k]==k): return k
        self.__par[k]=self.root(self.__par[k])
        return self.__par[k]

    def unite(self,i,j):
        i=self.root(i); j=self.root(j)
        par=self.__par; rank=self.__rank; size=self.__size
        if(i==j): return False
        if(rank[i]>rank[j]):
            par[j]=i
            size[i]+=size[j]
        else:
            par[i]=j
            size[j]+=size[i]
            if(rank[i]==rank[j]): rank[j]+=1
        self.__connected-=1
        return True

    def size(self,k):
        return self.__size[self.root(k)]

    def connected(self):
        return self.__connected

def resolve():
    n,m=map(int,input().split())
    uf=UnionFind(n)
    for _ in range(m):
        x,y,z=map(int,input().split())
        x-=1; y-=1
        uf.unite(x,y)
    print(uf.connected())
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(m):
        x,y,z=map(int,input().split())
        x-=1; y-=1
        E[x].append(y)
        E[y].append(x)

    visited=[0]*n
    def dfs(v)->bool:
        if(visited[v]):
            return False
        visited[v]=1
        for nv in E[v]:
            dfs(nv)
        return True

    ans=0
    for v in range(n):
        ans+=dfs(v)
    print(ans)
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(m):
        x,y,z=map(int,input().split())
        x-=1; y-=1
        E[x].append(y)
        E[y].append(x)

    visited=[0]*n
    def dfs(v,p)->bool:
        if(visited[v]):
            return False
        visited[v]=1
        for nv in E[v]:
            if(nv==p): continue
            dfs(nv,v)
        return True

    ans=0
    for v in range(n):
        ans+=dfs(v,-1)
    print(ans)
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class UnionFind(object):
    def __init__(self,n):
        self.__par=list(range(n))
        self.__rank=[0]*n
        self.__size=[1]*n

    def root(self,k):
        if(self.__par[k]==k): return k
        self.__par[k]=self.root(self.__par[k])
        return self.__par[k]

    def unite(self,i,j):
        i=self.root(i); j=self.root(j)
        par=self.__par; rank=self.__rank; size=self.__size
        if(i==j): return False
        if(rank[i]>rank[j]):
            par[j]=i
            size[i]+=size[j]
        else:
            par[i]=j
            size[j]+=size[i]
            if(rank[i]==rank[j]): rank[j]+=1
        return True

    def size(self,k):
        return self.__size[self.root(k)]

def resolve():
    n,m=map(int,input().split())
    uf=UnionFind(n)
    for _ in range(m):
        x,y,z=map(int,input().split())
        x-=1; y-=1
        uf.unite(x,y)
    print(len({uf.root(i) for i in range(n)}))
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class UnionFind(object):
    def __init__(self,n):
        self.__par=list(range(n))
        self.__rank=[0]*n
        self.__size=[1]*n

    def root(self,k):
        if(self.__par[k]==k): return k
        self.__par[k]=self.root(self.__par[k])
        return self.__par[k]

    def unite(self,i,j):
        i=self.root(i); j=self.root(j)
        par=self.__par; rank=self.__rank; size=self.__size
        if(i==j): return False
        if(rank[i]>rank[j]):
            par[j]=i
            size[i]+=size[j]
        else:
            par[i]=j
            size[j]+=size[i]
            if(rank[i]==rank[j]): rank[j]+=1
        return True

    def size(self,k):
        return self.__size[self.root(k)]

def resolve():
    n,m=map(int,input().split())
    uf=UnionFind(n)
    for _ in range(m):
        x,y,z=map(int,input().split())
        x-=1; y-=1
        uf.unite(x,y)
    print(len({uf.root(i) for i in range(n)}))
resolve()

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












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

print (ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**5+10)
input = sys.stdin.readline
def dfs(v,G,visit):
    visit[v-1]=1    
    for next in G[v-1]:        
        if visit[next-1]:
            continue
        _ = dfs(next,G,visit) 
 
N, M =map(int, input().split())
G  = [[] for _ in range(N)]
for i in range(M):
    a,b ,_= map(int, input().split())
    G[a-1].append(b)
    G[b-1].append(a)
    
count = 0

visit = [0]*N
for i in range(1,N+1):
  if visit[i-1]:
    continue
  if G[i-1]:  
    _ = dfs(i,G,visit)
  else:
    visit[i-1] = 1
  count += 1

print(count)

Solution (Python):
import numpy as np
import sys
sys.setrecursionlimit(10**5+1)
input = sys.stdin.readline

def dfs(v,G,visit):
    visit[v-1]=1    
    for next in G[v-1]:        
        if visit[next-1]:
            continue
        _ = dfs(next,G,visit) 
 
N, M =map(int, input().split())
G  = [[] for _ in range(N)]
for i in range(M):
    a,b ,_= map(int, input().split())
    G[a-1].append(b)
    G[b-1].append(a)
 
count = 0

visit = np.array([0]*N)
for i in range(1,N+1):
  if visit[i-1]:
    continue
  if G[i-1]:  
    _ = dfs(i,G,visit)
  else:
    visit[i-1] = 1
  count += 1

print(count)

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

parent=[i for i in range(n)]
rank=[0 for i in range(n)]

def find(a):
  if parent[a]==a:
    return a
  else:
    return find(parent[a])

def union(a,b):
  ar=find(a)
  br=find(b)
  if ar==br:
    return
  if rank[a]>rank[b]:
    parent[br]=ar
  else:
    parent[ar]=br
    if rank[a]==rank[b]:
      rank[a]+=1
      
def same(a,b):
  ar=find(a)
  br=find(b)
  return ar==br

q=[None]*m

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

for i in range(len(q)):
  union(q[i][0],q[i][1])
  
roots=[0]*len(parent)
for i in range(len(parent)):
  roots[i]=find(i)

print(len(set(roots)))

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
from collections import deque

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)

    def update_all(self):
        for i in range(n+1):
            self.par[i] = self.find(i)


n, m = getList()

UF = UnionFind(n)
for i in range(m):
    a, b, c = getList()
    if not UF.same_check(a, b):
        UF.union(a, b)

UF.update_all()

print(len(list(set(UF.par))) - 1)

Solution (Python):


MOD = 10 ** 9 + 7

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

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

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

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

uf = UnionFind(n)
for x, y, z in xyz_m:
    uf.union(x - 1, y - 1)

print(uf.group_count())

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


class DisjointSet():
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

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

    def count_groups(self):
        return len([i for i, x in enumerate(self.parent) if i == x])


d = DisjointSet(N)
for i in range(M):
    xi, yi, zi = map(int, input().split())
    d.unite(xi - 1, yi - 1)
print(d.count_groups())

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

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

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


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

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

p=[i for i in range(n)]
r=[0 for i in range(n)]

def find(x):
  if p[x]==x:
    return x
  else:
    p[x]=find(p[x])
    return p[x]

def unite(x,y):

  x = find(x)
  y = find(y)
  if x==y:
    return

  if r[x]<r[y]:
    p[x]=y
  else:
    p[y]=x
    if r[x]==r[y]:
      r[x] += 1

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

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

s = set()
for i in range(n):
  s.add(find(i))

print(len(s))

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

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

    def size(self, index):
        return -1 * self.parents[self.root(index)]

    def add(self, A, B):
        A = self.root(A)
        B = self.root(B)
        if (A == B):
            return
        if (self.size(A) < self.size(B)):
            A, B = B, A
        self.parents[A] += self.parents[B]
        self.parents[B] = A
N, M = [int(x) for x in input().split()]
XYZ = [[int(x) - 1 for x in input().split()] for _ in range(M)]
uf = UnionFind(N)
for x, y, z in XYZ:
    uf.add(x, y)
s = set()
for i in range(N):
    s.add(uf.root(i))
print(len(s))

Solution (Python):

import sys
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 solve(N: int, M: int, X: "List[int]", Y: "List[int]", Z: "List[int]"):
    uf = UnionFind(N)
    
    for i in range(M):
        uf.union(X[i]-1,Y[i]-1)
    
    print(uf.group_count())
    return


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):
import sys
from collections import deque
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, M = map(int, readline().split())
graph = [[] for _ in range(N + 1)]
check = []

for i in readlines():
    x, y, z = map(int, i.split())
    graph[x].append(y)
    graph[y].append(x)
    check.extend([x, y])

check = set(check)
answer = N - len(check)
while check:
    queue = deque([check.pop()])
    while queue:
        v = queue.popleft()
        for j in graph[v]:
            if j in check:
                queue.append(j)
                check.remove(j)
    answer += 1

print(answer)

Solution (Python):
class Unionfind():
    def __init__(self,N,weighted=False):
        self.root = list(range(N))
        self.depth = [1 for _ in range(N)]
        self.weighted = False
        if weighted:
            self.weighted = True
            self.weight = [0 for _ in range(N)]
    def find(self,x):
        if self.root[x] == x:
            return x
        else:
            r = self.find(self.root[x])
            if self.weighted:
                self.weight[x] += self.weight[self.root[x]]
            self.root[x] = r
            return r
    def unite(self,a,b,x=0):
        A = self.find(a)
        B = self.find(b)
        if self.weighted:
            wa = self.weight[a]
            wb = self.weight[b]
        if A == B:
            return
        elif self.depth[A] > self.depth[B]:
            self.root[B] = A
            self.depth[A] += self.depth[B]
            if self.weighted:
                self.weight[B] = wa -wb + d
        else:
            self.root[A] = B
            self.depth[B] += self.depth[A]
            if self.weighted:
                self.weight[A] = wb - wa - d
N,M = map(int,input().split())
uf = Unionfind(N)
for _ in range(M):
    x,y,_ = map(int,input().split())
    uf.unite(x-1,y-1)
root_set = set()
for i in range(N):
    root_set.add(uf.find(i))
print(len(root_set))

Solution (Python):
import sys
from collections import deque
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, M = map(int, readline().split())
graph = [[] for _ in range(N + 1)]
check = set([])

for i in readlines():
    x, y, z = map(int, i.split())
    graph[x].append(y)
    graph[y].append(x)
    check.add(x)
    check.add(y)

answer = N - len(check)
while check:
    queue = deque([check.pop()])
    while queue:
        v = queue.popleft()
        for j in graph[v]:
            if j in check:
                queue.append(j)
                check.remove(j)
    answer += 1

print(answer)

Solution (Python):
import sys
from collections import deque
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, M = map(int, readline().split())
graph = [[] for _ in range(N + 1)]

for i in readlines():
    x, y, z = map(int, i.split())
    graph[x].append(y)
    graph[y].append(x)

cnt = 0
checked = set([])

for i in graph:
    if i:
        if i[0] not in checked:
            queue = deque([i[0]])
            while queue:
                v = queue.popleft()
                for j in graph[v]:
                    if j not in checked:
                        queue.append(j)
                        checked.add(j)
            cnt += 1


print(N - len(checked) + cnt)

Solution (Python):


import sys
def input():
	return sys.stdin.readline().strip()

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


class Union_Find():
	def __init__(self, n):
		self.union = [i for i in range(n)]
		self.level = [0 for i in range(n)]
		self.num = n

	def root(self, i, mode=0):
		keiro = [i]
		ans = i
		while ans != self.union[ans]:
			ans = self.union[ans]
			keiro.append(ans)
		if mode == 0:
			return ans
		else:
			return ans, keiro

	def unite(self, i, j):
		root_i, list_i = self.root(i, 1)
		root_j, list_j = self.root(j, 1)
		if root_i != root_j:
			self.num -= 1
			if self.level[root_i] < self.level[root_j]:
				self.level[root_j] = max(self.level[root_i] + 1, self.level[root_j])
				for node in list_i:
					self.union[node] = root_j
			else:
				self.level[root_i] = max(self.level[root_j] + 1, self.level[root_i])
				for node in list_j:
					self.union[node] = root_i

union = Union_Find(N)

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

print(union.num)

Solution (Python):
class UF:
    def __init__(self, N):
        self.uf = [-1]*N
        self.n = N

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

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

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x==y: return
        if self.size(x) > self.size(y): x, y = y, x
        self.uf[y] += self.uf[x]
        self.uf[x] = y
        self.n -= 1

N, M = list(map(int,input().split()))
uf = UF(N)
for _ in range(M):
    X, Y, Z = list(map(int,input().split()))
    uf.union(X-1,Y-1)
print(uf.n)