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

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


def find(x):
    if P[x]==x:
        return x
    else:
        return find(P[x])
        
def union(y,z):
    Y=find(y)
    Z=find(z)
    if Y!=Z:
        if size[Y]>=size[Z]:
            P[Z]=P[Y]
            size[Y]+=size[Z]
        else:
            P[Y]=P[Z]
            size[Z]+=size[Y]

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

ans=0
for i in range(1,N+1):
    if i==P[i]:
        ans+=1
print(ans)

Solution (Python):

def main():
    buf = input()
    buflist = list(buf.split())
    N = int(buflist[0])
    M = int(buflist[1])
    edge = dict()
    for i in range(N):
        edge[i] = [] 
    for i in range(M):
        buf = input()
        buflist = list(buf.split())
        X = int(buflist[0])-1 
        Y = int(buflist[1])-1 
        Z = int(buflist[2])
        edge[X].append(Y)
        edge[Y].append(X)
    seen = []
    for i in range(N):
        seen.append(False)
    group_num = 0
    for i in range(N):
        if seen[i]:
            continue
        group_num += 1
        seen[i] = True
        stack = []
        for x in edge[i]:
            stack.append(x)
        while stack:
            current = stack.pop()
            if seen[current]:
                continue
            seen[current] = True
            for x in edge[current]:
                if not seen[x]:
                    stack.append(x)
    print(group_num)

if __name__ == '__main__':
    main()

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

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

    
    def connect(self,a,b):
        if self.root(a) == self.root(b):return False
        a = self.root(a);b = self.root(b)
        if self.size(a) < self.size(b):a,b = b,a
        self.parent[a] += self.parent[b]
        self.parent[b] = a
        return True

n,m = map(int,input().split())
uni = UnionFind(n)
for i in range(m):
    x,y,z = map(int,input().split())
    x -= 1
    y -= 1
    uni.connect(x,y)
ans = 0
for i in uni.parent:
    if i < 0:
        ans += 1
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
 
n,m = map(int,input().split())
 

par = [] 
rank = [] 
 

for i in range(n):
    
    par.append(i)
    rank.append(0)
 

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

def unite(x,y,par,rank):
    x = find(x,par)
    y = find(y,par)
    
    if x != y:
        
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x]==rank[y]:
                rank[x] += 1
 

def same(x,y,par):
    return find(x,par) == find(y,par)
 
for i in range(m):
    X,Y,Z = map(int,input().split())
    unite(X-1,Y-1,par,rank)
 
tank = []
for i in range(n):
    p = find(i,par)
    tank.append(p)
print(len(set(tank)))

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

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

visited = [False for i in range(N)]
v_to = [[] for i in range(N)]

for i in range(M):
  X, Y, Z = map(int, input().split())
  v_to[X - 1].append(Y - 1)
  v_to[Y - 1].append(X - 1)

def dfs(i):
  if visited[i]:
    return 0

  visited[i] = True
  for to in v_to[i]:
    dfs(to)

  return 1

ans = 0
for i in range(N):
  ans += dfs(i)

print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, elems):
        self.parent = dict()
        self.children = dict()
        for e in elems:
            self.parent[e] = e
            self.children[e] = 1

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

        return self.root(self.parent[e])

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

    def unite(self, x, y):
        if self.same(x, y):
            return

        rx, ry = self.root(x), self.root(y)
        
        if self.members(ry) < self.members(rx):
            rx, ry = ry, rx

        self.children[ry] += self.children[rx]
        self.parent[rx] = ry

    def members(self, x):
        return self.children[self.root(x)]


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

uf = UnionFind(range(1, n+1))
c = 0
for _ in range(m):
    x, y, z = map(int, input().split())
    if uf.same(x, y):
        continue
    else:
        c += 1
        uf.unite(x, y)

print(n - c)

Solution (Python):
class UnionFind():

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

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

  def union(self, x, y):
    xroot, yroot = self.find(x), self.find(y)
    if xroot == yroot:
      return False
    elif self.rank[xroot] < self.rank[yroot]:
      self.par[xroot] = yroot
    elif self.rank[xroot] > self.rank[yroot]:
      self.par[yroot] = xroot
    else:
      self.par[yroot] = xroot
      self.rank[xroot] += 1
    return True

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

n, m = list(map(int, input().split()))
uf = UnionFind(n+1)
ans = 0
for i in range(m):
  x, y, z = list(map(int, input().split()))
  ans += uf.union(x, y)
print(n-ans)

Solution (Python):
import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools, random
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right; sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]
def mi(n): return [wi() for _ in range(n)]
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

n, m = wi()

w = mi(m)

class UnionFind2(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]


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

    def same(self, x, y):
        return self.find(x) == self.find(y)
u = UnionFind2(n)
for i in range(m):
    u.union(w[i][0] - 1, w[i][1] - 1)

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


print(len(se))

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

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

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

	def unite(self, x, y):
		x, y = self.root(x), self.root(y)
		
		if x == y:
			return False
		
		if -self.parent[x] < -self.parent[y]:
			x, y = y, x
		self.parent[x] += self.parent[y]
		self.parent[y] = x
		return True


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

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

print(sum(p < 0 for p in uf.parent))

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

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

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

memo = [-1] * n

def dfs(v, memo):
    memo[v] = 1
    for nv in graph[v]:
        if memo[nv] != -1:
            continue
        dfs(nv, memo)

ans = 0

for i in range(n):
    if memo[i] != -1:
        continue
    dfs(i, memo)
    ans += 1

print(ans)

Solution (Python):
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]


    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(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 same(self, x, y):
        return self.find(x) == self.find(y)
n, m = map(int, input().split())
U=UnionFind(n)
for i in range(m):
    x, y, z = map(int, input().split())
    U.unite(x-1, y-1)
cnt=0
for i in range(n):
    if U.find(i)==i:
        cnt+=1
print(cnt)

Solution (Python):
import sys

inf = 10 ** 18

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


class UFnode(object):
    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.rank_ = 1

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        root = self.root()
        return root.group_id_

    def rank(self):
        root = self.root()
        return root.rank_

    def unite(self, unite_node):
        root = self.root()
        unite_root = unite_node.root()
        if root.group_id_ != unite_root.group_id_:
            if root.rank() > unite_root.rank():
                unite_root.parent_ = root
                root.rank_ = max(root.rank_, unite_root.rank_ + 1)
            else:
                root.parent_ = unite_root
                unite_root.rank_ = max(root.rank_ + 1, unite_root.rank_)

nodes = [UFnode(i) for i in range(N)]

for i, (Xi, Yi, Zi) in enumerate(XYZ):
    nodes[Xi - 1].unite(nodes[Yi - 1])

print(len(set([nodes[i].find() for i in range(N)])))

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



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

root = list(range(N+1))
depth = [0] * (N+1)

def find_root(x):
  y = root[x]
  if x == y:
    return x
  z = find_root(y)
  root[x] = z
  return z

def merge(x,y):
  global n_component
  xx = find_root(x)
  yy = find_root(y)
  if xx == yy:
    return
  n_component -= 1
  if depth[xx] >= depth[yy]:
    root[yy] = xx
    depth[xx] += 1
  else:
    root[xx] = yy
    depth[yy] += 1
  
for _ in range(M):
  x,y,z = [int(x) for x in input().split()]
  merge(x,y)

answer = n_component
print(answer)

Solution (Python):
import sys

input = sys.stdin.readline

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

class UnionFind:
    def __init__(self,n):
        self.par = [i for i in range(n)] 
        self.rank = [1]*n 
        self.size = [1]*n 
    
    def find(self,x):
        if self.par[x] == x:
            return x
        else:
            return self.find(self.par[x])
            
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            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 same(self,x,y):
        return self.find(x) == self.find(y)
        
    def group_size(self,x):
        return self.size[self.find(x)]
        
uf = UnionFind(N)
for x, y, z in xyz:
    x, y = x-1, y-1
    uf.unite(x,y)
ans = 0
for i in range(N):
    if i == uf.find(i):
        ans += 1
print(ans)

Solution (Python):
class UnionFind:
  def __init__(self):
    self.ht = {}

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

  def unite(self, x, y):
    nx = self.ht[x]
    ny = self.ht[y]
    if self.same(x, y):
      return
    xr = nx.root()
    yr = ny.root()
    xr.set_parent(yr)

  def add(self, x):
    n = Node(x)
    n.set_parent(None)
    self.ht[x] = n

  def show(self):
    roots = {}
    for n in self.ht.values():
      nr = n.root()
      if nr in roots:
        roots[nr].append(n.val)
      else:
        roots[nr] = [n.val]
    for s in roots.values():
      print(s)

  def get_set(self):
    roots = {}
    for n in self.ht.values():
      nr = n.root()
      if nr in roots:
        roots[nr].append(n.val)
      else:
        roots[nr] = [n.val]
    return roots.values()

class Node:
  def __init__(self, val):
    self.val = val

  def root(self):
    n = self
    chain = []
    while n.parent != None:
      chain.append(n)
      n = n.parent
    root = n
    for n in chain:
      n.set_parent(root)
    return root

  def set_parent(self, x):
    self.parent = x




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

for i in range(1, n+1):
  uf.add(i)

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

cnt = len(uf.get_set())

print(cnt)

Solution (Python):
from collections import deque
    
N,M = list(map(int,input().split()))

node_list = [[] for i in range(N)]

for i in range(M):
    x,y,z=list(map(int,input().split()))
    node_list[x-1].append(y-1)
    node_list[y-1].append(x-1)

checked_list = [-1 for i in range(N)]

def BFS(start,color,checked_list,node_list):
    Q=deque([start])
    checked_list[start]=color
    while len(Q)>0:
        v1 = Q.pop()
        for v2 in node_list[v1]:
            if checked_list[v2]==-1:
                checked_list[v2]=color
                Q.appendleft(v2)


count = 0
for i in range(N):
    if checked_list[i]==-1:
        BFS(i,count,checked_list,node_list)
        count+=1
        
print(count)

Solution (Python):
class UnionFindNode(object):
    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.rank_ = 1

    def __str__(self):
        template = "UnionFindNode(group_id: {}, \n\tparent: {}, value: {}, size: {})"
        return template.format(self.group_id_, self.parent_, self.value, self.rank_)

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        root = self.root()
        return root.group_id_

    def rank(self):
        root = self.root()
        return root.rank_

    def unite(self, unite_node):
        root = self.root()
        unite_root = unite_node.root()

        if root.group_id_ != unite_root.group_id_:
            if root.rank() > unite_root.rank():
                unite_root.parent_ = root
                root.rank_ = max(root.rank_, unite_root.rank_ + 1)
            else:
                root.parent_ = unite_root
                unite_root.rank_ = max(root.rank_ + 1, unite_root.rank_)

def main():
    N, M = [int(n) for n in input().split()]
    node_list = [UnionFindNode(i) for i in range(N)]
    for i in range(M):
        X, Y, Z = [int(n) for n in input().split()]
        node_list[X-1].unite(node_list[Y-1])
    gs = set()
    for node in node_list:
        gid = node.find()
        gs.add(gid)
    print(len(gs))
main()

Solution (Python):
def unite(rt, x, y):
	tx = x
	ty = y
	if tx > ty:
		tx, ty = ty, tx
	rt[ty] = tx
def find(rt, x):
	if rt[x] == -1 or rt[x] == x:
		return x
	else:
		rt[x] = find(rt, rt[x])
		return rt[x]
def main():
	n, m = map(int, input().split())
	rt = [-1]*(n+1)
	ans = n
	for i in range(m):
		x, y, z = map(int, input().split())
		root_x = find(rt, x)
		root_y = find(rt, y)
		if root_x == -1 or root_y == -1:
			pass
		elif root_x == root_y:
			continue
		ans -= 1
		unite(rt, root_x, root_y)
	print(ans)
main()

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

def main():
    N, M = LI()
    edges = [[] for _ in range(N)]
    for _ in range(M):
        x, y, xxx = LI_()
        edges[x].append(y)
        edges[y].append(x)
    ans = 0
    visited = [0] * N
    def connect(k):
        visited[k] = 1
        for e in edges[k]:
            if visited[e] == 0:
                connect(e)
    for i in range(N):
        if visited[i] == 0:
            ans += 1
            connect(i)
    return ans

print(main())

Solution (Python):

import sys
INF = float("inf")


class UnionFind(object):
    """重み付きUnionFind木
    """

    def __init__(self, N, unity=0):
        self.tree = list(range(N))
        self.rank = [0] * N
        self.diff_weight = [unity]*N

    def root(self, i):
        if self.tree[i] == i:
            return i
        else:
            r = self.root(self.tree[i])
            self.diff_weight[i] += self.diff_weight[self.tree[i]]
            self.tree[i] = r
            return r

    def weight(self, i):
        self.root(i)
        return self.diff_weight[i]

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

    def unite(self, x, y, w):
        w += self.weight(x)
        w -= self.weight(y)
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.rank[x] < self.rank[y]:
            x, y = y, x
            w = -w
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.tree[y] = x
        self.diff_weight[y] = w
        return True

    def diff(self, x, y):
        return self.weight(x) - self.weight(y)


def solve(N: int, M: int, X: "List[int]", Y: "List[int]", Z: "List[int]"):
    uf = UnionFind(N)
    for x, y, z in zip(X, Y, Z):
        uf.unite(x-1, y-1, z)

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

    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
input = sys.stdin.readline

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

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

def find(x):
    while Group[x] != x:
        x=Group[x]
    return x

def Union(x,y):  
    if find(x) != find(y):
        Group[find(y)]=Group[find(x)]=min(find(y),find(x))

for x,y,z in XYZ:
    Union(x,y)

ANS=[find(i) for i in range(1,N+1)]
print(len(set(ANS)))

Solution (Python):
N, M = map(int, input().split())
R = [i for i in range(N)]
def root(x):
  if R[x] == x:
    return x
  else:
    R[x] = root(R[x])
    return R[x]
def union(x, y):
  rx = root(x)
  ry = root(y)
  if rx < ry:
    R[ry] = rx
  else:
    R[rx] = ry
for i in range(M):
  x, y, z = map(int, input().split())
  union(x - 1, y - 1)
for i in range(N):
  root(i)
print(len(set(R)))

Solution (Python):

class UnionFind:
    def __init__(self, numV):
        self.pars = list(range(numV))
        self.ranks = [0] * numV
    def find(self, x):
        if self.pars[x] == x: return x
        else:
            self.pars[x] = self.find(self.pars[x])
            return self.pars[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        if self.ranks[x] < self.ranks[y]:
            self.pars[x] = y
        else:
            self.pars[y] = x
            if self.ranks[x] == self.ranks[y]:
                self.ranks[x] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)


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)

for i in range(N):
    UF.find(i)

parents = UF.pars
print(len(set(parents)))

Solution (Python):
class UnionFind():

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

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

  def union(self, x, y):
    xroot, yroot = self.find(x), self.find(y)
    if xroot == yroot:
      return False
    elif self.rank[xroot] < self.rank[yroot]:
      self.par[xroot] = yroot
    elif self.rank[xroot] > self.rank[yroot]:
      self.par[yroot] = xroot
    else:
      self.par[yroot] = xroot
      self.rank[xroot] += 1
    return True

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

n, m = list(map(int, input().split()))
uf = UnionFind(n+1)
ans = 0
for i in range(m):
  x, y, z = list(map(int, input().split()))
  ans += uf.union(x, y)
print(n-ans)

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


def dfs(graph, start, visited):
    stack = [start]
    visited.add(start)
    while stack:
        label = stack.pop(0)
        for node in g[label]:
            if node not in visited:
                visited.add(node)
                stack.append(node)
    return visited


g = {i: [] for i in range(1, N + 1)}
for i in range(M):
    x, y, z = map(int, input().split())
    g[x].append(y)
    g[y].append(x)
ans = 0
for i in range(1, N + 1):
    if i not in v:
        ans += 1
        dfs(g, i, v)
print(ans)

Solution (Python):
N,M=map(int,input().split())
edges = [[] for _ in range(N)]
for _ in range(M):
    x,y,z = map(int,input().split())
    edges[x-1].append(y-1)
    edges[y-1].append(x-1)
from collections import deque
queue = deque()
ans = 0
index = 0
checked = [False for _ in range(N)]
while index < N:
    if checked[index]:
        index += 1
        continue
    ans += 1
    queue.append(index)
    checked[index] = True
    while len(queue) > 0:
        v = queue.popleft()
        for w in edges[v]:
            if checked[w]:
                continue
            queue.append(w)
            checked[w] = True
    index += 1
print(ans)

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

    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 union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)

        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False
N,M = map(int,input().split())
u = UnionFind(N)
for i in range(M):
    X,Y,Z = map(int,input().split())
    u.union(X-1,Y-1)
ans = []
for i in range(N):
    ans.append(u.find(i))
ans = len(set(ans))
print(ans)

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

n, m = [int(i) for i in input().split()]
U = [[int(i) for i in input().split()] for j in range(m)]

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

for u, v, w in U:
    E[u].append(v)
    E[v].append(u)

visited = [False] * (n + 1)

def dfs(v):
    if visited[v]:
        return 0
    
    visited[v] = True

    for e in E[v]:
        dfs(e)
    
    return 1

ans = 0

for i in range(1, n + 1):
    ans += dfs(i)

print(ans)

Solution (Python):
from sys import stdin
from collections import deque

n, m = map(int, raw_input().strip().split())
inp = stdin.readlines()

g = [[] for i in xrange(n + 1)]

for line in inp:
    x, y, z = map(int, line.strip().split())
    g[x].append(y)
    g[y].append(x)

vis = [0] * (n + 1)

def bfs(root):
    global vis
    
    vis[root] = 1
    q = deque([root])
    while q:
        u = q.popleft()
        for v in g[u]:
            if not vis[v]:
                vis[v] = 1
                q.append(v)
    
ans = 0
for u in xrange(1, n + 1):
    if vis[u] == 0:
        bfs(u)
        ans += 1

print ans

Solution (Python):
class Union:
  def __init__(self, num):
    self.T = [-1 for i in range(num)]

  def root(self, x):
    if self.T[x] < 0: return x
    return self.root(self.T[x])

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

  def merge(self, x, y):
    a = self.root(x)
    b = self.root(y)
    if a == b: return False
    if self.size(a) < self.size(b): a, b = b, a
    self.T[a] += self.T[b]
    self.T[b] = a
    return True


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

uni = Union(N)

for x,y,z in XYZ:
  uni.merge(x - 1, y - 1)

Ans = 0
for i in uni.T:
  if i < 0:
    Ans += 1

print(Ans)

Solution (Python):

import sys


class UnionFind:
    """
    sizeによる実装
    """

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.size = [1 for _ in range(N)]

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

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]

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

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

    def componentNum(self):
        ret = 0
        for i in range(N):
            if self.parent[i] == i:
                ret += 1
        return ret


sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

for x, y, z in hint:
    Un.union(x, y)
comp = Un.componentNum()
print(comp)

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

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

    def merge(self, x, y): 
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]: 
            x,y=y,x
        self.parent[x] += self.parent[y] 
        self.parent[y] = x 
        return True

    def issame(self, x, y): 
        return self.root(x) == self.root(y)
        
    def size(self,x): 
        return -self.parent[self.root(x)]
        
        
n,m = [int(i) for i in input().split()]

T=UnionFind(n)
c=0
for _ in [0]*m:
    x,y,z=[int(i) for i in input().split()]
    if not T.issame(x-1,y-1):
        T.merge(x-1,y-1)
        c+=1

print(n-c)

Solution (Python):

def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
n,m=IL()

par=[]
rank=[]
def init(a): 
    for i in range(a):
        par.append(i)
        rank.append(0)
def find(x): 
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
    return par[x]
def unite(x,y): 
    x=find(x)
    y=find(y)
    if rank[x]==rank[y]:
        par[x]=y
    else:
        par[y]=x
        if rank[x]==rank[y]:
            rank[x]+=1
    return
def same(x,y): 
    return find(x)==find(y)

init(n)
gn=n
for i in range(m):
    x,y,z=IL()
    if find(x-1)!=find(y-1):
        n-=1
        unite(x-1,y-1)
print(n)

Solution (Python):
N,M=map(int,input().split())
xyz= [list(map(int,input().split())) for _ in [0]*M]
par = [-1]*N
def get_parent(n):
    if par[n]==-1:return n
    else:
        par[n] = get_parent(par[n])
        return par[n]
def merge(i,j):
    i = get_parent(i)
    j = get_parent(j)
    if i!=j:par[j] = i
    return
for x,y,z in xyz:
    merge(x-1,y-1)
print(par.count(-1))

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


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

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

    
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


UF = UnionFind(N)

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

print(len(set(UF.par)))