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):
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)





class Unionfind:

  def __init__(s,n):
    s.sz = [1] * n
    s.ances = [i for i in range(n)]

  def root(s,x):
    a = []
    y = x
    while s.ances[y] != y:
      a.append(y)
      y = s.ances[y]
    for z in a:
      s.ances[z] = y
    return y

  def conn(s,x,y):
    i = s.root(x)
    j = s.root(y)
    if i==j:
      return
    
    k  = j if (s.sz[i]<s.sz[j]) else i
    if k==j:
      s.ances[i] = j
    else:
      s.ances[j] = i
    s.sz[k] = s.sz[i] + s.sz[j]



n,m = inm()
uf = Unionfind(n+1)
for i in range(m):
    x,y,z = inm()
    uf.conn(x,y)
a = [0]*(n+1)
for i in range(1,n+1):
    a[uf.root(i)] = 1
print(sum(a))

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

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


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

    print(len(uni.roots()))


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import defaultdict,deque
input = sys.stdin.readline
N,M= map(int,input().split())
XYZ= [list(map(int,input().split())) for i in range(M)]
g = defaultdict(list)

for x,y,z in XYZ:
    g[x].append(y)
    g[y].append(x)

visited = [False] * (N+1)

connect = 0
for i in range(1,N+1):
    if visited[i]:
        continue
    connect += 1
    dq = deque([i])
    while dq:
        v = dq.pop()
        visited[v] = True
        for nv in g[v]:
            if visited[nv]:
                continue
            dq.append(nv)

print(connect)

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

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

Solution (Python):
import sys, collections, heapq
def input(): return sys.stdin.readline().strip()

class UnionFind():
    """
    https://note.nkmk.me/python-union-find/
    DFSの上位互換と考えて良い
    ２要素x, yがpath-connectedかどうかをlogオーダーで判定する（螺旋本の14.1節参照）
    さらに連結成分の要素数がO(1)で取得可能なように改造してある
    """
    def __init__(self, n):
        """
        要素数をnとして、各ノードを0,1,...,(n-1)の番号で管理する
        parentsは各ノードの属する木の根を表す
        ただし根ノードのparentには(その木のノード数)*(-1)を格納する
        """
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        """
        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, yのそれぞれ属する木Tx, Tyの根同士を繋ぐ
        このとき木の要素数が小さい方を大きい方に繋ぐ（rankではなくsizeを用いる）
        """
        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):
        """
        xの属する木の要素数を返す
        根の親を要素数の(-1)倍で定めておいたおかげでO(1)で取得可能
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """
        xとyがpath-connectedかを判定する
        """
        return self.find(x) == self.find(y)

    def members(self, x):
        """
        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())
    hint = []
    for _ in range(M):
        x, y, _ = map(int, input().split())
        hint.append((x - 1, y - 1))

    """
    xが分かればyも分かるので、それを「頂点xと頂点yの間に辺がある」と解釈すれば
    求めるのはグラフの連結成分そのもの。よってUnionFindTreeで終わり。
    """

    tree = UnionFind(N)
    for x, y in hint:
        tree.union(x, y)
    print(tree.group_count())


if __name__ == "__main__":
    main()

Solution (Python):
N,M=map(int,input().split())
tree=[[]for i in range(N)]
ischecked=[0]*N
ans=0
for i in range(M):
    X,Y,Z=map(int,input().split())
    tree[X-1].append(Y-1)
    tree[Y-1].append(X-1)
for i in range(N):
    if ischecked[i]==1:
        continue
    ischecked[i]=1
    q=tree[i]
    while q:
        a=q.pop()
        if ischecked[a]==1:
            continue
        ischecked[a]=1
        q.extend(tree[a])
    ans=ans+1
print(ans)

Solution (Python):
class UnionFind(): 
    def __init__(self,n):
        self.n=n
        self.par = [-1]*n
    def find(self,x):
        if self.par[x] <0: 
            return x
        else: 
            self.par[x]=self.find(self.par[x]) 
            return self.par[x]
    def union(self,x,y):
        x=self.find(x) 
        y=self.find(y)

        if x==y: 
            return 
        if self.par[x]>self.par[y]: 
            x,y=y,x
        self.par[x]+=self.par[y] 
        self.par[y]=x

    def size(self,x):
        return -self.par[self.find(x)] 
    
    def same(self,x,y): 
        return self.find(x)==self.find(y)

    def member(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.par) if x<0]
    
    def group_count(self): 
        return len(self.roots())

    def all_member(self): 
        return {r: self.member(r) for r in self.roots()}
    def __str__(self):
        return "\n".join('{}:{}'.format(r,self.member(r)) for r in self.roots)
n,m=map(int,input().split())
xyz = [list(map(int, input().split())) for _ in range(m)]
x, y ,z= [list(i) for i in zip(*xyz)]
uf = UnionFind(n)
for i in range(m):
    uf.union(x[i]-1,y[i]-1)
print(uf.group_count())

Solution (Python):



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

    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 find(self, x):          
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

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

    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())
    uf = UnionFind(N)
    rel = [list(map(int,input().split())) for i in range(M)]
    for i in rel:
        uf.union(i[0]-1, i[1]-1)

    print(uf.group_count())


if __name__ == '__main__':
    main()

Solution (Python):
from sys import setrecursionlimit

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

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

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


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

    def count_group(self):
        return len({self.find(x) for x in range(n)})

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.count_group())

Solution (Python):
class UnionFind:
    N = 0
    cost = 0
    par = []
    group = 0
    
    def init(N):
        UnionFind.N = N
        UnionFind.group = N
        UnionFind.par = [i for i in range(N)]

    def find(v):
        c = 0
        u = v
        while v != UnionFind.par[v]:
            v = UnionFind.par[v]
            c += 1

        if c > 10:
            while u != v: u, UnionFind.par[u] = UnionFind.par[u], v

        return v

    def union(v, u, c=0):
        vr = UnionFind.find(v)
        ur = UnionFind.find(u)

        if vr == ur: return True

        UnionFind.par[ur] = vr
        UnionFind.cost += c
        UnionFind.group -= 1
        
        return False
            
    def get_cost():
        return UnionFind.cost

    def get_group():
        return UnionFind.group

    def same(v, u):
        return UnionFind.find(v) == UnionFind.find(u)

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

for i in range(M):
    x, y, _ = list(map(int, input().split()))
    x -= 1; y -= 1

    UnionFind.union(x, y)

print(UnionFind.get_group())

Solution (Python):
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


class UF:
    def __init__(self, N):
        self.parent = [i for i in range(N)]
    
    def get_parent(self, a):
        p = self.parent[a]
        if a == p:
            return a
        
        q = self.get_parent(p)
        self.parent[a] = q
        return q

    def make_pair(self, a, b):
        pa = self.get_parent(a)
        pb = self.get_parent(b)
        if pa == pb:
            return
        
        self.parent[pa] = pb
        self.parent[a] = pb
    
    def is_pair(self, a, b):
        return self.get_parent(a) == self.get_parent(b)

    def num_group(self):
        return sum(1 for i, j in enumerate(self.parent) if i == j)


def main():
    N, M = read_values()
    uf = UF(N)
    
    for _ in range(M):
        X, Y, _ = read_index()
        uf.make_pair(X, Y)

    print(uf.num_group())


if __name__ == "__main__":
    main()

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

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

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

Solution (Python):
import copy
N,M = map(int,(input().split()))
x = [0]*M
y = [0]*M
z = [0]*M
line = [[] for _ in range(N+1)]
dot = []

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

class UnionFind:

    def __init__(self, n):
        self.par =  [-1] * n
        self.rank = [0] * n
    
    def root(self,x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

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

        if x == y:
            return
        else:
            if self.rank[x] <self.rank[y]:
                self.par[y] += self.par[x] 
                self.par[x] = y
            else:
                self.par[x] += self.par[y]
                self.par[y] = x
                if self.rank[x] == self.rank[y]: 
                    self.rank[x] += 1
    
    def is_same(self, x, y):
        return self.root(x) == self.root(y)

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

Tree = UnionFind(N)

for i in range(N):
    for j in line[i]:
        Tree.union(i-1,j-1)

nohint = 0
hint = []
for i in range(N):
    if Tree.size(i) == 1:
        nohint += 1
    else:
        hint.append(Tree.root(i))

print(nohint + len(set(hint)))

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    
    

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

    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    
    def unite(x,y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x,y = y,x
            par[x] += par[y]
            par[y] = x
            return True
    
    def same(x,y):
        return find(x) == find(y)
    
    def size(x):
        return -par[find(x)]
    
    
    def roots():
        return [i for i, x in enumerate(par) if x < 0]
    
    par = [-1]*n

    for x,y,z in xyz:
        if same(x-1, y-1):
            continue
        unite(x-1, y-1)

    res = len(roots())
    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


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

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

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

        if x == y:
            return

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

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

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

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

    def get_n_groups(self):
        return len(self.get_parent_list())


def main():
    N, M = map(int, input().split())
    tree = UnionFind(N)
    for _ in range(M):
        x, y, z = map(int, input().split())
        x -= 1
        y -= 1
        tree.unite(x, y)
    n_groups = tree.get_n_groups()
    print(n_groups)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import defaultdict


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


class UnionFind:
    def __init__(self, n_nodes):
        self.n_nodes = n_nodes
        self.parent = [i for i in range(n_nodes)]
        self.rank = [1] * n_nodes
        self.size = [1] * n_nodes

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

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

    def get_parent_list(self):
        return [i for i in range(self.n_nodes) if self.find(i) == i]

    def get_n_groups(self):
        return len(self.get_parent_list())

    def get_members(self, x):
        parent = self.find(x)
        return [i for i in range(self.n_nodes) if self.find(i) == parent]

    def get_members_dict(self):
        return {par: self.get_members(par) for par in self.get_parent_list()}


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


if __name__ == "__main__":
    main()

Solution (Python):


import sys



















def main():
    mod = 1000000007                  
    inf = float('inf')
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    

    class UnionFindTree:
        def __init__(self, num_of_elm):
            self.n = num_of_elm
            self.table = [i for i in range(self.n)]
            self.rank = [0] * self.n
            self.group_size = [1] * self.n
        
        def _find_set(self, x):
            parent = self.table[x]
            if x == parent:
                return x
            else:
                root = self._find_set(parent)
                
                self.table[x] = root
                return root
        
        def is_same(self, x, y):
            return self._find_set(x) == self._find_set(y)

        def union(self, x, y):
            shallow_root = self._find_set(x)
            deep_root = self._find_set(y)
            if self.rank[shallow_root] > self.rank[deep_root]:
                shallow_root, deep_root = deep_root, shallow_root
            
            if shallow_root == deep_root:
                return False
            
            else:
                self.table[shallow_root] = deep_root
                self.group_size[deep_root] += self.group_size[shallow_root]
                
                if self.rank[shallow_root] == self.rank[deep_root]:
                    self.rank[deep_root] += 1
                return True

        def akin_num(self, x):
            x_root = self._find_set(x)
            return self.group_size[x_root]

        def print_group_id(self):
            print([self._find_set(x) for x in self.table])    
    

    n, m = mi()
    uf = UnionFindTree(n)
    groups = n
    for _ in range(m):
        x, y, _ = mi()
        x -= 1
        y -= 1
        if uf.union(x, y):
            groups -= 1
    print(groups)

if __name__ == "__main__":
    main()

Solution (Python):
from sys import setrecursionlimit, exit
setrecursionlimit(1000000000)

from collections import Counter

def main():
    n, m = map(int, input().split())
    par = [i for i in range(n)]
    size = [1] * n

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

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

    def unite(x, y):
        x = root(x)
        y = root(y)
        if x == y:
            return
        par[x] = y
        size[y] += size[x]
    
    for _ in range(m):
        x, y, z = map(int, input().split())
        unite(x - 1, y - 1)
    for i in range(n):
        root(i)
    print(len(Counter(par)))

main()

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

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


from collections import defaultdict
xyz = defaultdict(lambda: set([]))
for _ in range(m):
    x,y,z=map(int,input().split())
    xyz[x].add(y)
    xyz[y].add(x)

no_checked=[0]*n

def DFS(x):
    global no_checked
    global xyz
    no_checked[x-1]=1
    for item in xyz[x]:
        if no_checked[item-1]==0:
            DFS(item)

cnt=0
for i in range(1,n+1):
    if no_checked[i-1]==0:
        cnt+=1
        DFS(i)

    
print(cnt)

Solution (Python):
import sys

input = sys.stdin.readline


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

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

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

        if x == y:
            return

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

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

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

    u = UnionFind(N)

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

    print(u.group_count())


if __name__ == '__main__':
    main()

Solution (Python):
import sys

input = sys.stdin.readline


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

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

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

        if x == y:
            return

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

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

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

    u = UnionFind(N + 2)

    f = True
    for x, y, z in XYZ:
        x += 1
        y += 1
        if z % 2 == 0:
            u.union(x, y)
        else:
            if f:
                f = False
                u.union(x, 0)
                u.union(y, 1)
            if u.same(x, 0):
                u.union(y, 1)
            if u.same(x, 1):
                u.union(y, 0)
            if u.same(y, 0):
                u.union(x, 1)
            if u.same(y, 1):
                u.union(x, 0)

    for x, y, z in XYZ:
        x += 1
        y += 1
        if z % 2 == 1:
            u.union(x, y)
        else:
            if f:
                f = False
                u.union(x, 0)
                u.union(y, 1)
            if u.same(x, 0):
                u.union(y, 1)
            if u.same(x, 1):
                u.union(y, 0)
            if u.same(y, 0):
                u.union(x, 1)
            if u.same(y, 1):
                u.union(x, 0)

    print(u.group_count())


if __name__ == '__main__':
    main()

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

    def get_root(self, i):
        while self.parent[i] != -1:
            i = self.parent[i]
        return i

    def is_same_tree(self, i, j):
        return self.get_root(i) == self.get_root(j)

    def merge(self, i, j):
        i = self.get_root(i)
        j = self.get_root(j)
        if i == j:
            return

        if self.rank[i] > self.rank[j]:
            self.parent[j] = i
            self.rank[i] = max(self.rank[i], self.rank[j] + 1)
            self.count[i] += self.count[j]
        else:
            self.parent[i] = j
            self.rank[j] = max(self.rank[j], self.rank[i] + 1)
            self.count[j] += self.count[i]

n, m = [int(i) for i in input().split()]
uf = UnionFind(n)
for _ in range(m):
    x, y, _ = [int(i) - 1 for i in input().split()]
    uf.merge(x, y)
print(uf.parent.count(-1))

Solution (Python):
N,M=map(int,input().split())
XYZ=[]
for i in range(M):
  x,y,z=map(int,input().split())
  XYZ.append([x,y,z])
class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n+1)
    self.rnk=[0]*(n+1)
  def find(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.find(self.root[x])
      return self.root[x]
  def unite(self,x,y):
    x=self.find(x)
    y=self.find(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 count(self,x):
    return -self.root[self.find(x)]
uf=UnionFind(N)
for i in range(M):
  uf.unite(XYZ[i][0],XYZ[i][1])
ans=-1
for i in range(len(uf.root)):
  if uf.root[i]<0:
    ans+=1
print(ans)