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




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 members(x):
    root = find(x)
    return [i for i in range(n) if find(i) == root]


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


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


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



par = [-1]*n

"""
uniteでまとめ、findで見つける。
n(要素数)だけ最初に付け加えること。
"""
lst = []
for i in range(m):
    x,y,z = map(int,input().split())
    x,y = x-1,y-1
    if z%2 == 0:
        unite(x,y)
    else:
        lst.append([x,y])

for i,j in lst:
    unite(i,j)

print(group_count())

Solution (Python):
import sys

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
    def find(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        self.parent[x] = y

def main():
    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)
    s = set()
    for i in range(N):
        s.add(uf.find(i))
    print(len(s))

if __name__ == "__main__":
    sys.setrecursionlimit(10**6)
    main()

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    edge=[[] for _ in range(N)]
    for i in range(M):
        X,Y,Z=map(lambda x:int(x)-1,input().split())
        edge[X].append(Y)
        edge[Y].append(X)
    used=[False]*N
    ans=0
    for i in range(N):
        if not used[i]:
            ans+=1
            queue=deque()
            queue.append(i)
            while queue:
                node=queue.popleft()
                used[node]=True
                for nextnode in edge[node]:
                    if not used[nextnode]:
                        queue.append(nextnode)
    print(ans)
                    

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

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

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


ans = 0
is_used = [False]*N
for i in range(N):
  if is_used[i]:
    continue
  
  ans += 1
  is_used[i] = True
  d = deque([i])
  while d:
    node = d.pop()
    children = tree[node]
    for child in children:
      if is_used[child]:
        continue
      
      is_used[child] = True
      d.append(child)

print(ans)

Solution (Python):

class UnionFindPathCompression():
    def __init__(self, n):
        self.parents = list(range(n))

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

        self.parents[y] = x

    def roots(self):
        r=[i for i,x in enumerate(self.parents) if i==x]
        return len(r)

if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    LIST=[list(map(int,input().split())) for i in range(M)]
    union_find=UnionFindPathCompression(N)
    for l in LIST:
        union_find.union(l[0]-1,l[1]-1)
    print(union_find.roots())

Solution (Python):




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

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

    def union(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if x==y:
            return
        elif 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.menbers(r) for r in self.roots()}

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

if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    LIST=[list(map(int,input().split())) for i in range(M)]
    union_find=UnionFind(N)
    for l in LIST:
        union_find.union(l[0]-1,l[1]-1)

    print(union_find.group_count())

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

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

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

        if x == y:
            return

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

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

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

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


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

uf = UnionFind(n)
for i in range(len(l)):
    x, y = l[i]
    uf.union(x - 1, y - 1)
ans = uf.group_count()
print(ans)

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

n,m = map(int,input().split())
par = [-1]*n

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

tank = set([])
for i in range(n):
    tank.add(find(i))
print(len(tank))

Solution (Python):
def main():


    


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

    n,m = map(int,input().split())
    par = [-1]*n

    for i in range(m):
        X,Y,Z = map(int,input().split())
        unite(X-1,Y-1)
    
    tank = set([])
    for i in range(n):
        tank.add(find(i))
    print(len(tank))

if __name__ == '__main__':
    main()

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

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

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

visited = [False] * n

def dfs(v, p):
    visited[v] = True
    for nv in g[v]:
        if nv == p or visited[nv]: continue
        dfs(nv, v)

cnt = 0

for v in range(n):
    if not visited[v]:
        dfs(v, -1)
        cnt += 1

print(cnt)

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())
    x -= 1
    y -= 1
    u.union(x,y)
ans = []
for i in range(N):
    ans.append(u.find(i))
ans = len(set(ans))
print(ans)

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

n, m = map(int, input().split())
F = [[] for _ in range(n)]
for _ in range(m):
  x, y, z = map(int, input().split())
  x -= 1
  y -= 1
  F[x].append(y)
  F[y].append(x)
seen = [False]*n
def dfs(v):
  seen[v] = True
  for nv in F[v]:
    if seen[nv]:
      continue
    dfs(nv)
ans = 0
for v in range(n):
  if not seen[v]:
    ans += 1
    dfs(v)
print(ans)

Solution (Python):
class Union_Find():
    def __init__(self, num):
        self.par = [-1]*(num+1)
        self.siz = [1]*(num+1)

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

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

    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] < self.par[ry]:
                self.par[ry] = rx
                self.siz[rx] += self.siz[ry]
            elif self.par[rx] > self.par[ry]:
                self.par[rx] = ry
                self.siz[ry] += self.siz[rx]
            else:
                self.par[rx] -= 1
                self.par[ry] = rx
                self.siz[rx] += self.siz[ry]
        return

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


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

ans = []
for i in range(1, n+1):
    ans.append(tree.find(i))

print(len(set(ans)))

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

G = {k: [] for k in range(N)}
for _ in range(M):
    X, Y, Z = map(int, input().split())
    
    G[X-1].append(Y-1)
    G[Y-1].append(X-1)

visited = [False]*N

sys.setrecursionlimit(1000000)


def dfs(ci):
    for ni in G[ci]:
        if visited[ni] is True:
            continue
        visited[ni] = True
        dfs(ni)


ans = 0
for i in range(N):
    if visited[i] is False:
        ans += 1
        visited[i] = True
        dfs(i)
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
n,m = map(int, input().split(' '))
abe = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
visited = [0]*(n+1)
for a,b,e in abe:
    graph[a].append(b)
    graph[b].append(a)
stack = []
cnt = 0
append = stack.append
pop = stack.pop
for i in range(1,n+1):
    if visited[i] != 1:
        cnt += 1
        append(i)
    while stack:
        x = pop()
        visited[x] = 1
        for y in graph[x]:
            if visited[y] != 1:
                append(y)
print(cnt)

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

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


uf1=UnionFind(n)
for i in range(m):
    b=a[i][0]
    c=a[i][1]
    uf1.union(b-1,c-1)

ans=uf1.group_count()
print(ans)

Solution (Python):
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines







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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

def main():
	n,m=map(int,input().split())
	uf=UnionFind(n)
	
	for i in range(m):
		x,y,z=map(int,input().split())
		x-=1;y-=1
		uf.union(x,y)
	print(uf.group_count())
		
		
		
	
	
	
	
	


	
if __name__ == "__main__":
	main()

Solution (Python):
def main():
    N, M = map(int, input().split())
    known = [False] * N
    rel = [list() for _ in range(N)]
    
    for _ in range(M):
        x, y, z = list(map(int, input().split()))
        rel[x - 1].append(y - 1)
        rel[y - 1].append(x - 1)
    r = 0
    for i in range(N):
        if known[i]:
            continue
        known[i] = True
        r += 1
        cur = rel[i].copy()
        while cur:
            t = cur.pop()
            if not known[t]:
                cur.extend(rel[t])
                known[t] = True
    print(r)

main()

Solution (Python):
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components


def solve():
    N, M = map(int, input().split())
    X = [0 for _ in range(M)]
    Y = X[:]
    for i in range(M):
        X[i], Y[i], _ = map(lambda x: int(x)-1, input().split())
    
    graph = csr_matrix(([1]*M, (X, Y)), (N, N))
    ans = connected_components(graph)[0]
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
class UnionFind:
    def __init__(self, data):
        """
        与えられたdataまでの長さの配列を作成
        配列は1から開始する
        それがunionfindの親となり初めは自分自身
        またrankも定義し初期値は0
        """
        self.parent = {}
        self.rank = {}
        for i in range(1, data+1):
            self.parent[i] = i
            self.rank[i] = 0


    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 same(self, x, y):
        """
        与えられた2つの値が同一グループ(親)かチェック
        """
        return self.find(x) == self.find(y)


    def unite(self, x, y):
        """
        与えられた2つの値を同一のグループ(親)にする
        """
        x = self.find(x)
        y = self.find(y)
        if x == y: 
            return
        if self.rank[x] > self.rank[y]: 
            self.parent[y] = x
            return
        else: 
            self.parent[x] = y
            if self.rank[x] == self.rank[y]: self.rank[y] += 1
            return


N,M = map(int, input().split())
union_find = UnionFind(N)
for i in range(M):
    X,Y,Z = map(int, input().split())
    union_find.unite(X,Y)

ans = 0
for i in range(1,N+1):
    if union_find.find(i) == i:
        ans += 1

print(ans)

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

    n,m = map(int,input().split())
    
    
    par = [-1]*n

    for i in range(m):
        X,Y,Z = map(int,input().split())
        unite(X-1,Y-1)
    
    tank = set([])
    for i in range(n):
        tank.add(find(i))
    print(len(tank))

if __name__ == '__main__':
    main()

Solution (Python):



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




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

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



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



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


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




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


for i in range(1,n+1):
    find(i)


ans=len(set(par))-1

print(ans)

Solution (Python):



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

par = [i for i in range(n+1)]
rank = [0 for i in range(n+1)]

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

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

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

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

for i in range(1,n+1):
    find(i)
    
ans=len(set(par))-1

print(ans)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,m = LI()
def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]

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

def union(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

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

xyz = [LI() for _ in range(m)]
for x,y,z in xyz:
    if root(x-1) != root(y-1):
        union(x-1,y-1)
f = defaultdict(lambda :0)
ans = 0
for i in range(n):
    if f[root(i)] == 0:
        ans += 1
        f[root(i)] = 1

print(ans)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,m = LI()
def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]

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

def union(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

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

xyz = [LI() for _ in range(m)]
for x,y,z in xyz:
    if root(x-1) != root(y-1):
        union(x-1,y-1)
f = defaultdict(int)
for i in range(n):
    f[root(i)] = 1

ans = 0
for i,j in f.items():
    if j != 1:
        continue
    ans += 1
print(ans)

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

graph = [[] for _ in range(N+1)]
for i in range(M):
  X, Y, Z = map(int, input().split())
  graph[X].append(Y)
  graph[Y].append(X)

answer = 0
stack = []
seen = [0] * (N+1)

for i in range(1, N+1):
  if seen[i] == 0:
    answer += 1
    seen[i] = 1
    if len(graph[i]):
      stack.append(i)
      while stack:
        s = stack.pop()
        for g in graph[s]:
          if seen[g] == 0:
            stack.append(g)
            seen[g] = 1
print(answer)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    n,m=map(int, input().split())
    
    tree=[[] for _ in range(n)]
    for i in range(m):
        x,y,w = map(int,input().split())
        tree[x-1].append(y-1)
        tree[y-1].append(x-1)
    
    singles = [ i for i in range(n) if tree[i]==[]]
    
    visited=[False]*n
    for i in singles:
        visited[i] = True
    ans=len(singles)
    
    from collections import deque
    while False in visited:
        ans+=1
        start = visited.index(False)
        visited[start]=True
        q=deque([(start,togo) for togo in tree[start]])
        while q:
            parent,x = q.pop()
            visited[x]=True
            for y in tree[x]:
                if not visited[y]:
                    q.append((x,y))
    
    
    print(ans)
    
if __name__ == '__main__':
    main()

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

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

singles = [ i for i in range(n) if tree[i]==[]]

visited=[False]*n
for i in singles:
    visited[i] = True
ans=len(singles)

from collections import deque
while False in visited:
    ans+=1
    start = visited.index(False)
    visited[start]=True
    q=deque([(start,togo) for togo in tree[start]])
    while q:
        parent,x = q.pop()
        visited[x]=True
        for y in tree[x]:
            if not visited[y]:
                q.append((x,y))


print(ans)

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

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

cost=0

uf=Uf(n)
for i in range(m):
    uf.unite(x[i],y[i])
cnt=set()
for i in range(n):
    tmp=uf.root(i)
    cnt.add(tmp)

print(len(cnt))

Solution (Python):

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

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

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

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

check = [False]*n

cnt=0
import queue
q=queue.Queue()
for i in range(n):
	if check[i]:
		continue
	cnt+=1
	check[i]=True
	q.put(i)

	while not q.empty():
		now=q.get()
		for ne in g[now]:
			if check[ne]:
				continue
			check[ne]=True
			q.put(ne)

print(cnt)

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

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

check = [False]*n

cnt=0
import queue
for i in range(n):
	if check[i]:
		continue
	cnt+=1
	check[i]=True
	q=queue.Queue()
	q.put(i)

	while not q.empty():
		now=q.get()
		for ne in g[now]:
			if check[ne]:
				continue
			check[ne]=True
			q.put(ne)

print(cnt)

Solution (Python):

import sys, math, itertools, heapq, collections, bisect, string
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**7)
inf = float('inf')
mod = 10**9+7
ans = inf ;count = 0 ;pro = 1

class UnionFind:
    __slots__ = ['id','sz']

    def __init__(self, n):
        self.id = [-1] * n
        self.sz = n

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

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

    def union(self, x, y):
        s1, s2 = self.root(x), self.root(y)
        if s1 != s2:
            if self.id[s1] <= self.id[s2]:
                self.id[s1] += self.id[s2]
                self.id[s2] = s1
            else:
                self.id[s2] += self.id[s1]
                self.id[s1] = s2
            self.sz-=1
            return True
        return False


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.sz)

Solution (Python):
import sys
sys.setrecursionlimit(500*500)
N, M = map(int,input().split())
Q = [list(map(int,input().split())) for _ in range(M)]
C = [[] for _ in range(N+1)]
count = 0
for q in Q:
    X = q[0]
    Y = q[1]
    C[X].append(Y)
    C[Y].append(X)

flag = [-1]*(N+1)
flag[1] = 0
def dfs(s):
    global count
    for c in C[s]:
        flag[s] = 0
        if flag[c] == -1:
            flag[c] = 0
            count += 1
            dfs(c)

for i in range(1,N+1):
    dfs(i)
print(N-count)

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

class UnionFind():
    def __init__(self,n):
        self.n=n
        self.root=[-1]*(n+1)
        self.rnk=[0]*(n+1)

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

    def Unite(self,x,y):
        x=self.Find_Root(x)
        y=self.Find_Root(y)
        if x==y:
            return
        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)]

uf=UnionFind(n)
for _ in range(m):
    x,y,z=map(int,input().split())
    x-=1
    y-=1
    uf.Unite(x,y)
r=[0]*n
for i in range(n):
    r[i]=uf.Find_Root(i)
s=set(r)
print(len(s))

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

    cnt=0
    col=[None]*n
    def dfs(v)->bool:
        if(col[v] is not None): return False
        Q=[v]
        col[v]=cnt
        while(Q):
            v=Q.pop()
            for nv in E[v]:
                if(col[nv] is not None): continue
                col[nv]=cnt
                Q.append(nv)
        return True

    for v in range(n):
        cnt+=dfs(v)

    print(cnt)
resolve()