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):
N, M = map(int, input().split())


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


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


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


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

    if rank[x] > rank[y]:
        parent[y] = x
    else:
        parent[x] = y
        if rank[x] == rank[y]:
            rank[y] += 1


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

num = 0
for i in range(N):
    if i == find(i):
        num += 1

print(num)

Solution (Python):
import scipy.sparse as sp
import scipy.sparse.csgraph as gp


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

adj = sp.dok_matrix((N,N), dtype=bool)
def it():
    for m in range(M):
        x,y,z = map(int,input().split())
        x,y = x-1,y-1
        adj[x,y] = True
        adj[y,x] = True
it()

res,_ = gp.connected_components(adj, directed=False)
print(res)

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 size(self, x):
    return -self.root[self.find_root(x)]

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

UF = UnionFind(N)
for i in range(M):
  x = hint[i][0]
  y = hint[i][1]
  UF.unite(x, y)
print(len([r for r in UF.root if r < 0]) - 1)

Solution (Python):
import sys

sys.setrecursionlimit(10000)
INF = float('inf')


class UnionFind:
    def __init__(self, size=None, nodes=None):
        """
        size か nodes どっちか指定。
        nodes は set、size は list を使う。
        set の最悪計算量は O(N) なので size 指定のほうが若干速い
        :param int size:
        :param collections.Iterable nodes:
        """
        assert size is not None or nodes is not None
        if size is not None:
            self._parents = [i for i in range(size)]
            self._ranks = [0 for _ in range(size)]
            self._sizes = [1 for _ in range(size)]
        else:
            self._parents = {k: k for k in nodes}
            self._ranks = {k: 0 for k in nodes}
            self._sizes = {k: 1 for k in nodes}

    def unite(self, x, y):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        :return:
        """
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        
        if self._ranks[x] > self._ranks[y]:
            
            self._parents[y] = x
            self._sizes[x] += self._sizes[y]
        else:
            
            self._parents[x] = y
            self._sizes[y] += self._sizes[x]
            if self._ranks[x] == self._ranks[y]:
                self._ranks[y] += 1

    def find(self, x):
        """
        x が属する木の root
        :param x:
        :return:
        """
        if self._parents[x] == x:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]

    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        :return:
        """
        return self._sizes[self.find(x)]


N, M = list(map(int, input().split()))
X, Y, Z = zip(*[list(map(int, input().split())) for _ in range(M)])

uf = UnionFind(size=(N + 1) * 2)
for x, y, z in zip(X, Y, Z):
    uf.unite(x, y)

roots = set()
ans = 0
for i in range(1, N + 1):
    root = uf.find(i)
    if root not in roots:
        roots.add(root)
        ans += 1

print(ans)

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

    def __len__(self):
        return self.size

    def root(self, i):
        """0 <= i < n"""
        if self.data[i] < 0:
            return i
        self.data[i] = self.root(self.data[i])
        return self.data[i]

    def connected(self, i, j):
        return self.root(i) == self.root(j)

    def groupsize(self, i):
        return self.sizes[self.root(i)]

    def roots(self):
        """O(n)"""
        return [i for i, v in enumerate(self.data) if v < 0]

    def unite(self, i, j):
        i = self.root(i)
        j = self.root(j)
        if i == j:
            return
        if (-self.data[i]) < (-self.data[j]):
            self.data[i] = j
            self.sizes[j] += self.sizes[i]
        elif (-self.data[i]) > (-self.data[j]):
            self.data[j] = i
            self.sizes[i] += self.sizes[j]
        else:
            self.data[i] += -1
            self.data[j] = i
            self.sizes[i] += self.sizes[j]


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)

print(len(uf.roots()))

Solution (Python):
class Unionfind:
  def __init__(self,n):
    self.Tree=[i for i in range(n)]
    self.rank=[0]*n

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

  def unite(self,x,y):
    s1=self.find(x)
    s2=self.find(y)
    if s1==s2:
      pass
    else:
      if self.rank[s1]>self.rank[s2]:
        self.Tree[s2]=s1
      elif self.rank[s1]<self.rank[s2]:
        self.Tree[s1]=s2
      else:
        self.Tree[s2]=s1
        self.rank[s1]+=1

N,M=map(int,input().split())        
uf=Unionfind(N)        
for i in range(M):
  x,y,w=map(int,input().split())
  uf.unite(x-1,y-1)
used=[False]*N
ans=0
for i in range(N):
  uf.find(i)
  if not used[uf.Tree[i]]:
    ans+=1
  used[uf.Tree[i]]=True
  
print(ans)

Solution (Python):






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

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

def unite(x, y):
	x = find_root(x)
	y = find_root(y)
	if(x == y):
		return 0

	if rank[x] < rank[y]:
		par[x] = y

		temp = size[x] * size[y]
		size[y] = size[x] + size[y]
	else:
		par[y] = x
		if (rank[x] == rank[y]):
			rank[x] += 11

		temp = size[x] * size[y]
		size[x] = size[x] + size[y]
	return temp

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


par = list(range(n))
rank = [0]*n
size = [1]*n

edges = [list(map(int, input().split()))[0:2] for _ in range(m)]
edges = [[b[0]-1, b[1]-1] for b in edges] 

for b in range(m):
	unite(edges[b][0] , edges[b][1])




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

print(len(set(arr)))

Solution (Python):


import sys
import math

import array
import bisect
import collections
from collections import Counter, defaultdict
import fractions
import heapq
import re

sys.setrecursionlimit(1000000)


def array2d(dim1, dim2, init=None):
    return [[init for _ in range(dim2)] for _ in range(dim1)]

def argsort(l, reverse=False):
    return sorted(range(len(l)), key=lambda i: l[i], reverse=reverse)

def argmin(l):
    return l.index(min(l))

def YESNO(ans, yes="YES", no="NO"):
    print([no, yes][ans])

II = lambda: int(input())
MI = lambda: map(int, input().split())
MIL = lambda: list(MI())
MIS = lambda: input().split()

class UnionFind(object):
    """UnionFind (経路圧縮、ランクあり)"""
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def union(self, n1, n2):
        r1 = self.root(n1)
        r2 = self.root(n2)
        if r1 != r2:
            if self.rank[r1] < self.rank[r2]:
                self.parent[r1] = r2
            else:
                self.parent[r2] = r1
                if self.rank[r1] == self.rank[r2]:
                    self.rank[r1] += 1

    def root(self, node):
        p = self.parent[node]
        if p == node:
            return p
        p = self.root(p)
        self.parent[node] = p
        return p

    def same(self, n1, n2):
        return self.root(n1) == self.root(n2)


def main():
    N, M = MI()
    uf = UnionFind(N)

    for i in range(M):
        x, y, _ = MI()
        uf.union(x-1, y-1)

    return len(set([uf.root(i) for i in range(N)]))


if __name__ == "__main__":
    print(main())

Solution (Python):
class UnionFind:
    def __init__(self, size: int):
        self.__size = size
        self.__root = [-1] * size

    def find(self, x: int)->int:
        if self.__root[x] < 0:
            return x
        self.__root[x] = self.find(self.__root[x])
        return self.__root[x]

    def union(self, x: int, y: int)->int:
        rx, ry = self.find(x), self.find(y)

        if rx == ry:
            return

        if self.__root[ry] < self.__root[rx]:
            rx, ry = ry, rx

        self.__root[rx] += self.__root[ry]
        self.__root[ry] = rx

    def same(self, x: int, y: int)->bool:
        return self.find(x) == self.find(y)


def one_or_two(N: int, M: int, queries: list)->int:
    uf = UnionFind(N)

    for x, y, _ in queries:
        uf.union(x-1, y-1)

    return len(set(uf.find(i) for i in range(N)))


if __name__ == "__main__":
    M = 0
    N, M = map(int, input().split())
    queries = [tuple(int(s) for s in input().split()) for _ in range(M)]

    ans = one_or_two(N, M, queries)
    print(ans)

Solution (Python):


import sys
sys.setrecursionlimit(int(1e9))

class UnionFind():
  def __init__(self):
    self.roots = {}
    self.nums = {}

  def find_root(self, a):
    if a not in self.roots:
      self.nums[a] = 1
      return a
    else:
      self.roots[a] = self.find_root(self.roots[a])
      return self.roots[a]

  def unite(self, a, b):
    root_a = self.find_root(a)
    root_b = self.find_root(b)
    n_a = self.nums[root_a]
    n_b = self.nums[root_b]
    if root_a == root_b:
      return
    else:
      if n_a > n_b: 
        self.roots[root_b] = root_a
        self.nums[root_a] = n_a + n_b
        del self.nums[root_b]
      else:
        self.roots[root_a] = root_b
        self.nums[root_b] = n_a + n_b
        del self.nums[root_a]
      return
  
  def is_union(self, a,b):
    return self.find_root(a) == self.find_root(b)
  
  
N , M = list(map(int, input().split()))
XYZ = [list(map(int, input().split())) for _ in range(M)]

uf = UnionFind()

_set = set()

for x,y,z in XYZ:
  uf.unite(x,y)
  _set.add(x)
  _set.add(y)
  
answer = len(set([uf.find_root(i) for i in _set])) + N-len(_set)
print(answer)

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

from collections import Counter

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

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

def find(x):
	if g[x] == x:
		return x
	g[x] = find(g[x])
	return g[x]

def union(x, y):
	x = find(x)
	y = find(y)
	if x != y:
		g[x] = y

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

print(len(Counter([find(i) for i in range(1, N+1)])))

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

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


class UnionFind:
    def __init__(self, node: int) -> None:
        self.n = node
        self.par = [i for i in range(self.n)]
        self.rank = [0 for i in range(self.n)]

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

    def unite(self, x: int, y: int) -> bool:
        if self.isSame(x, y):
            
            return False

        rx = self.find(x)
        ry = self.find(y)

        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = self.par[ry]
        else:
            self.par[ry] = self.par[rx]

            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

        return True

    def isSame(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)


n,m = li()
uf = UnionFind(n)
for _ in range(m):
    x,y,z = li()
    x -= 1
    y -= 1
    uf.unite(x,y)

pars = set()
for i in range(n):
    uf.find(i)
    pars.add(uf.par[i])

print(len(pars))

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.data=[-1 for i in range(n)]

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

    def uni(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if(x==y):
            return
        if self.data[y]<self.data[x]:
            x,y=y,x
        self.data[x]+= self.data[y]
        self.data[y] = x

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

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

n,m=map(int,input().split())
uf=UnionFind(n)
for i in range(m):
    x,y,z=map(int,input().split())
    uf.uni(x-1,y-1)
count=0
for i in range(n):
    if uf.data[i]<0:
        count+=1
print(count)

Solution (Python):
import sys
sys.setrecursionlimit(2*10**5)


N, M = map(int, input().split())
X, Y, Z = (
    zip(*(map(int, input().split()) for _ in range(M))) if M else
    ((), ())
)

G = [set() for _ in range(N + 1)]
for x, y in zip(X, Y):
    G[x].add(y)
    G[y].add(x)


dp = [-1 for _ in range(N + 1)]


def f(i, k):
    for t in G[i]:
        if dp[t] == -1:
            dp[t] = k
            f(t, k)


L = 0
for i in range(1, N + 1):
    if dp[i] == -1:
        L += 1
        f(i, L)
ans = L
print(ans)

Solution (Python):

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

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

    def unite(self, x, y):
        root_x = self.get_root(x)
        root_y = self.get_root(y)
        
        
        
        if root_x != root_y:
            
            if self.nodes[root_x] < self.nodes[root_y]:
                big_root = root_x
                small_root = root_y
            else:
                small_root = root_x
                big_root = root_y
            self.nodes[big_root] += self.nodes[small_root]
            self.nodes[small_root] = big_root


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

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

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

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

def par(i):
    if X[i] == i:
        return i
    tmp = par(X[i])
    X[i] = tmp
    return tmp
    
ans = N
for _ in range(M):
    x, y, z = map(int, input().split())
    
    px = par(x-1)
    py = par(y-1)
    if px != py:
        ans -= 1
        X[py] = px

print(ans)

Solution (Python):
def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a
 
def union(A, x, y):

    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    A[y] = bx
    A[by] = bx

N, M = map( int, input().split())
V = [ i for i in range(N)]
for _ in range(M):
    x, y,_ = map( int, input().split())
    union(V, x-1, y-1)
print( sum( [1 for i in range(N) if i == V[i]]))

Solution (Python):

import sys
input=sys.stdin.readline
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 x==y:
            return
        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)

uf=UnionFind(n)
for _ in range(m):
    x,y,z=map(int,input().split())
    x-=1; y-=1
    uf.union(x,y)
Ans=[0]*n
for i in range(n):
    Ans[uf.find(i)]=1
print(sum(Ans))

Solution (Python):
class UnionFindTree():
    def __init__(self, N):
        self.__parent_of = [None] * N
        self.__rank_of = [0] * N
        self.__size = [1] * N

    def root(self, value):
        if self.__parent_of[value] is None:
            return value
        else:
            self.__parent_of[value] = self.root(self.__parent_of[value])
            return self.__parent_of[value]

    def unite(self, a, b):
        r1 = self.root(a)
        r2 = self.root(b)
        if r1 != r2:
            if self.__rank_of[r1] < self.__rank_of[r2]:
                self.__parent_of[r1] = r2
                self.__size[r2] += self.__size[r1]
            else:
                self.__parent_of[r2] = r1
                self.__size[r1] += self.__size[r2]
                if self.__rank_of[r1] == self.__rank_of[r2]:
                    self.__rank_of[r1] += 1

    def is_same(self, a, b):
        return self.root(a) == self.root(b)

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

    def groups(self):
        groups = {}
        for k in range(len(self.__parent_of)):
            r = self.root(k)
            if r not in groups:
                groups[r] = []
            groups[r].append(k)
        return [groups[x] for x in groups]


def main():
    N, M = map(int, input().split())
    uft = UnionFindTree(N)
    for _ in range(M):
        x, y, z = map(int, input().split())
        uft.unite(x-1, y-1)
    print(len(uft.groups()))


if __name__ == "__main__":
    main()

Solution (Python):
import sys


class UnionFind(object):
    def __init__(self, N):
        self._parent = list(range(N))
        self.__num_components = [1] * N

    def root(self, x):
        if self._parent[x] == x:
            return x
        else:
            
            self._parent[x] = self.root(self._parent[x])
            return self._parent[x]

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

    def num_connected(self, x):
        return self.__num_components[self.root(x)]

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if (x == y):
            return
        rank_x = self.__num_components[x]
        rank_y = self.__num_components[y]
        if rank_x < rank_y:
            self._parent[x] = y
            self.__num_components[y] += rank_x
        else:
            self._parent[y] = x
            self.__num_components[x] += rank_y
        return


fin = sys.stdin.readline
N, M = [int(elem) for elem in fin().split()]
conditions = [tuple(int(elem) - 1 for elem in fin().split()) for _ in range(M)]
uf = UnionFind(N)
for X, Y, _ in conditions:
    uf.unite(X, Y)

num_distinct_components = 0
for i in range(N):
    if uf.root(i) == i:
        num_distinct_components += 1
print(num_distinct_components)

Solution (Python):
N,M = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(M)]

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

uf = UnionFind(N)
for x,y,z in src:
    x,y = x-1,y-1
    uf.unite(x,y)
print(N - uf.count)

Solution (Python):
from collections import deque


'''UnionFindクラス'''
class UnionFind:

    def __init__(self, n):
        self.parent =  [-1 for _ in range(n)]

    def root(self, x):
        '''根を返す'''
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def merge(self, x, y):
        '''xとyの根を結合する'''
        x = self.root(x)
        y = self.root(y)
        if x != y:
            if self.parent[x] > self.parent[y]:
                x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x
        return

    def is_same(self, x, y):
        '''xとyの根が同じかどうかを返す（根が同じ:True、根が異なる:False）'''
        return self.root(x) == self.root(y)

    def get_size(self, x):
        '''xが含まれる木の要素数を返す'''
        return -self.parent[self.root(x)]


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

graph = [[] for i in range(n)]
for i in range(m):
    graph[info[i][0] - 1].append([info[i][1] - 1, info[i][2]])
    graph[info[i][1] - 1].append([info[i][0] - 1, info[i][2]])

uf = UnionFind(n)
visited = [False]*n
ans = 0
for i in range(n):
    if not visited[i]:
        ans += 1
        visited[i] = True
        q = deque()
        q.append(i)
        while q:
            pos = q.pop()
            for j, cost in graph[pos]:
                if not visited[j]:
                    visited[j] = True
                    q.append(j)
print(ans)

Solution (Python):
n, m = map(int, input().split())
fa = {i: i for i in range(1, n + 1)}
cnt = n

def getfa(x):
	if fa[x] == x:
		return x
	fa[x] = getfa(fa[x])
	return fa[x]

for i in range(m):
	x, y, z = map(int, input().split())
	fx = getfa(x)
	fy = getfa(y)
	if fx != fy:
		cnt -= 1
	fa[fy] = fx

print(cnt)

Solution (Python):

import sys
sys.setrecursionlimit(200000)

def solve(N: int, M: int, X: "List[int]", Y: "List[int]", Z: "List[int]"):
    conn = [[] for _ in range(N)]
    for i in range(M):
        conn[X[i] - 1].append(Y[i] - 1)
        conn[Y[i] - 1].append(X[i] - 1)

    def dfs(idx, conn, visited):
        visited[idx] = True
        for c in conn[idx]:
            if not visited[c]:
                dfs(c, conn, visited)
        return visited

    visited = [False] * N
    ret = 0
    for i in range(N):
        if not visited[i]:
            visited = dfs(i, conn, visited)
            ret += 1
    print(ret)
    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):
class Uf:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])

        return self.p[x]

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

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

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

N, M = map(int, input().split())
uf = Uf(N+1)
for _ in range(M):
    X, Y, Z = map(int, input().split())
    uf.unite(X, Y)
s = set()
for i in range(1, N+1):
    s.add(uf.root(i))
print(len(s))

Solution (Python):
class UnionFind():
    n=1
    par=[0]
    rnk=[0]
    def __init__(self,size):
        self.n=size
        self.par=[i for i in range(self.n)]
        self.rnk=[0 for i in range(self.n)]
    def find(self,vertex1):
        if self.par[vertex1]==vertex1:
            return vertex1
        else:
            self.par[vertex1]=self.find(self.par[vertex1])
            return self.par[vertex1]
    def unite(self,vertex1,vertex2):
        vertex1=self.find(vertex1)
        vertex2=self.find(vertex2)
        if vertex1==vertex2:
            return
        if (self.rnk[vertex1]<self.rnk[vertex2]):
            self.par[vertex1]=vertex2
        else:
            self.par[vertex2]=vertex1
            if(self.rnk[vertex1]==self.rnk[vertex2]):
                self.rnk[vertex1]+=1
    def same(self,vetrex1,vertex2):
        return self.find(vetrex1)==self.find(vertex2)

N,M=map(int,input().split())
G=UnionFind(N)
for i in range(M):
    x,y,z=map(int,input().split())
    G.unite(x-1,y-1)
X=[G.find(i) for i in range(N)]
print(len(set(X)))

Solution (Python):
import sys
def input():
	return sys.stdin.readline()[:-1]
sys.setrecursionlimit(10 ** 6)
 
class UnionFind():
	def __init__(self, size):
		self.length = size
		self.table = [-1 for _ in range(size)]
		self.size = [1 for _ in range(size)]
 
	def find(self, x):
		if self.table[x] < 0:
			return x
		else:
			self.table[x] = self.find(self.table[x])
			return self.table[x]
 
	def unite(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
				self.table[s1] -= 1
				self.size[s1] += self.size[s2]
				self.size[s2] = 0
			else:
				self.table[s1] = s2
				self.table[s2] -= 1
				self.size[s2] += self.size[s1]
				self.size[s1] = 0
 
		return

	def get_size(self):
		cnt = 0
		for i in range(self.length):
			if self.table[i] < 0:
				cnt += 1
		return cnt

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

Solution (Python):
N,M=list(map(int,input().strip().split(' ')))
graph=[[]  for i in range(N+1)]
for _ in range(M):
    a,b,c=list(map(int,input().strip().split(' ')))
    graph[a]+=[b]
    graph[b]+=[a]

checked={}
def dfs(root):
    connected=[]
    stack=[]
    stack+=[root]
    parent={}
    parent[root]=-1
    checked[root]=1
    while stack:
        v=stack.pop()
        for node in graph[v]:
            if node!=parent[v] and node not in checked:
                checked[node]=1
                parent[node]=v
                stack+=[node]
    return stack
count=0
for i in range(1,N+1):
    if i not in checked:
        dfs(i)
        count+=1
print(count)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    n,k = LI()
    s = input()
    for i in range(k-1):
        print(s[i],end = "")
    print(s[k-1].lower(),end = "")
    for i in range(k,n):
        print(s[i],end = "")
    print()
    return


def B():
    s = S()
    k = int(s[0])*10+int(s[1])
    l = int(s[2])*10+int(s[3])
    if k == 0:
        if l == 0:
            print("NA")
        elif l < 13:
            print("YYMM")
        else:
            print("NA")
    elif k < 13:
        if l == 0:
            print("MMYY")
        elif l < 13:
            print("AMBIGUOUS")
        else:
            print("MMYY")
    else:
        if l == 0:
            print("NA")
        elif l < 13:
            print("YYMM")
        else:
            print("NA")


def C():
    n,k = LI()
    ans = 0
    for i in range(1,n+1):
        l = k/i
        ans += 1/n*1/(2 << max(0,math.ceil(math.log(l,2))))
    print(ans*2)
    return


def D():
    n = I()
    v = [[] for i in range(n)]
    for i in range(n-1):
        x,y,w = LI()
        x -= 1
        y -= 1
        v[x].append((y,w))
        v[y].append((x,w))
    ans = [0 for i in range(n)]
    bfs_map = [1 for i in range(n)]
    bfs_map[0] = 0
    q = deque()
    q.append(0)
    while q:
        x = q.popleft()
        for y,w in v[x]:
            if bfs_map[y]:
                if w%2:
                    ans[y] = ans[x]^1
                else:
                    ans[y] = ans[x]
                bfs_map[y] = 0
                q.append(y)
    for i in ans:
        print(i)
    return


def E():
    def root(x):
        if par[x] == x:
            return par[x]
        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 rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
    n,m = LI()
    par = [i for i in range(n)]
    rank = [0 for i in range(n)]
    for i in range(m):
        x,y,z = LI()
        x -= 1
        y -= 1
        if not same(x,y):
            unite(x,y)
    for i in range(n):
        root(i)
    par = list(set(par))
    print(len(par))
    return


def F():
    n = I()

    return


if __name__ == "__main__":
    E()