Problem:
 Score : 500 points    Problem Statement There are N cards placed face down in a row. On each card, an integer 1 or 2 is written.  Let A_i be the integer written on the i -th card.  Your objective is to guess A_1, A_2, ..., A_N correctly.  You know the following facts:   For each i = 1, 2, ..., M , the value A_{X_i} + A_{Y_i} + Z_i is an even number.   You are a magician and can use the following magic any number of times:  Magic : Choose one card and know the integer A_i written on it. The cost of using this magic is 1 .  What is the minimum cost required to determine all of A_1, A_2, ..., A_N ?  It is guaranteed that there is no contradiction in given input.      Constraints  All values in input are integers.  2 \leq N \leq 10^5  1 \leq M \leq 10^5  1 \leq X_i < Y_i \leq N  1 \leq Z_i \leq 100  The pairs (X_i, Y_i) are distinct.  There is no contradiction in input. (That is, there exist integers A_1, A_2, ..., A_N that satisfy the conditions.)         Input Input is given from Standard Input in the following format:  N  M  X_1  Y_1  Z_1  X_2  Y_2  Z_2  \vdots  X_M  Y_M  Z_M       Output Print the minimum total cost required to determine all of A_1, A_2, ..., A_N .        Sample Input 1 3 1
1 2 1      Sample Output 1 2  You can determine all of A_1, A_2, A_3 by using the magic for the first and third cards.       Sample Input 2 6 5
1 2 1
2 3 2
1 3 3
4 5 4
5 6 5      Sample Output 2 2       Sample Input 3 100000 1
1 100000 100      Sample Output 3 99999

Solution (Python):
import sys

class UFT: 
    def __init__(self, N): 
        self.tree = [int(i) for i in range(N)] 
        self.rank = [0 for i in range(N)]

    def find(self, a):
        if self.tree[a] == a: return a
        else:
            self.tree[a] = self.find(self.tree[a])
            return self.tree[a]

    def unite(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b: return
        if self.rank[a] < self.rank[b]: self.tree[a] = b
        else:
            self.tree[b] = a
            if self.rank[a] == self.rank[b]: self.rank[a] += 1

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    parent = UFT(N)
    for i in range(M):
        x, y, z = map(int, input().split())
        parent.unite(x-1, y-1)
    for i in range(N):
        parent.find(i)

    print(len(set(parent.tree)))
    
    return 0

if __name__ == "__main__":
    solve()

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

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

    def Unite(self, x, y):
        
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        
        if(x == y):
            return
        
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    

    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


n, m = map(int, input().split())
uni = UnionFind(n)
cnt = 0

for i in range(m):
    x, y, _ = map(int, input().split())
    if not uni.isSameGroup(x, y):
        cnt += 1
        uni.Unite(x, y)

print(n - cnt)

Solution (Python):
from collections import deque
N,M = map(int,input().split())
E = [[] for _ in range(N+1)]
for i in range(M):
    x,y,z = map(int,input().split())
    E[x].append(y)
    E[y].append(x)

d = [-1]*(N+1)

def dfs(start,num):
    q = deque([start])
    d[start] = num
    while(q):
        v = q.pop()
        for s in E[v]:
            if(d[s] == -1):
                d[s] = num
                q.append(s)

group_num = 0
for i in range(1,N+1):
    if(d[i] == -1):
        group_num += 1
        dfs(i,group_num)

print(group_num)

Solution (Python):
from collections import deque
N,M=map(int,input().split())
tree=[[] for _ in range(N)]
colornum=[-1]*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)

for i in range(N):
    d=deque()
    if colornum[i]==-1:
        d.append(i)
        colorid = i
    else:
        colorid=colornum[i]
    while len(d)>0:
        v=d.popleft()
        colornum[v]=colorid
        for j in tree[v]:
            if colornum[j]==-1:
                d.append(j)
print(len(set(colornum)))

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

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

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

visited = [False for _ in range(n)]


def dfs(v, p):
    for u in tree[v]:
        if u == p:
            continue
        elif visited[u]:
            continue
        else:
            visited[u] = True
            dfs(u, v)


res = 0
for i in range(n):
    if not visited[i]:
        visited[i] = True
        dfs(i, -1)
        res += 1

print(res)

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 __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

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)

import sys
input = sys.stdin.readline 
n,m = [int(i) for i in input().split()]
par = [-1]*n
for i in range(m):
  x,y,z = [int(i)-1 for i in input().split()]
  unite(x,y)
   
import collections
chk = []
chk = collections.deque(chk)
for i in range(n):
  chk_append = chk.append
  chk_append(find(i))
  
chk = set(chk)
print(len(chk))

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)

n,m = [int(i) for i in input().split()]
par = [-1]*n
for i in range(m):
  x,y,z = [int(i)-1 for i in input().split()]
  unite(x,y)
  
chk = []
for i in range(n):
  chk_append = chk.append
  chk_append(find(i))
  
chk = set(chk)
print(len(chk))

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

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

G=[[] for _ in range(N+1)]
for el in XYZ:
    G[el[0]].append(el[1])
    G[el[1]].append(el[0])


seen=[False]*(N+1)
todo=queue.Queue()
def bfs(n):
    seen[n]=True
    for nxt in G[n]:
        if seen[nxt]==False:
            bfs(nxt)


cnt=0
for check in range(1, N+1):
    if seen[check]==False:
        cnt+=1
        bfs(check)
print(cnt)

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

par = [-1]*(N+1)


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

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

ans = 0
counted = [False] * (N+1)
for i in range(1,N+1):
    root = find(i)
    if not counted[root]:
        ans += 1
        counted[root] = True
print(ans)

Solution (Python):
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left, bisect_right

def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iip_ord():
    return [ord(i) - ord("a") for i in input()]


def main():
    ans = solve()
    if ans is not None:
        print(ans)


class union_find():
    def __init__(self, id):
        self.parent = None
        self.id = id

    def root(self):
        if not self.parent:
            return self
        else:
            return self.parent.root()

    def union(self, target):
        sr = self.root().id
        tr = target.root().id
        if sr == tr:
            return
        elif sr > tr:
            self.root().parent = target.root()
        else:
            target.root().parent = self.root()


def solve():
    N, M = iip(False)

    uf = [union_find(i) for i in range(N)]

    for i in range(M):
        x, y, _ = iip(True)
        uf[x-1].union(uf[y-1])

    uf = set([i.root().id for i in uf])
    
    print(len(uf))



def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

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

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

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

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

    if x == y:
      return

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

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

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

uf = UnionFind(N)

for _ in range(M):
  x,y,z = map(int, input().split())
  uf.union(x-1,y-1)
  
ans = len(uf.roots())
  
print(ans)

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

def f(j):
  nodes[j]=1
  for k in links[j]:
    if nodes[k]==0:
      f(k)

N, M=map(int, input().split())
XYZ=[list(map(int, input().split())) for _ in range(M)]
links=[[] for _ in range(N+1)]
for i in range(M):
  links[XYZ[i][0]].append(XYZ[i][1])
  links[XYZ[i][1]].append(XYZ[i][0])
  
nodes=[0]*(N+1)
ans=0
for i in range(1, N+1):
  if nodes[i]==0:
    ans+=1
    nodes[i]=1
    for j in links[i]:
      f(j)
      
print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        '木の初期化をする'
        self.p = [-1] * n
        self.rank = [1]*n
        self.root = n
    def find(self, x):
        'x の親を返す'
        if self.p[x] == -1:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def unite(self, x, y):
        'rankの低い親を高い方のの親にする'
        if not self.same(x,y):
            x = self.find(x)
            y = self.find(y)
            if self.rank[x] > self.rank[y]:
                x,y = y,x
            elif self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.p[x] = y
            self.root -= 1
            return True
        else:
            return False

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


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

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

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

N,M = map(int,input().split())
XYZ = list()
for i in range(M):
    x,y,z = map(int,input().split())
    XYZ.append((x,y,z))

uf = UnionFind(N)
for xyz in XYZ:
    x,y,z = xyz
    uf.unite(x-1,y-1)

ans = set()
for i in range(N):
    ans.add(uf.find(i))

print(len(ans))

Solution (Python):
N, M = map(int, input().split())
UF = [-1] * (N+1)
def find(x):
    global UF
    if UF[x] == -1:
        return x
    else:
        UF[x] = find(UF[x])
        return UF[x]
def union(x,y):
    global UF
    xx = find(x)
    yy = find(y)
    if UF[x] == UF[y] == -1:
        UF[y] = xx
        return
    elif xx == yy:
        return 
    else:
        UF[yy] = xx
        return 
    
for _ in range(M):
    x, y, z = map(int, input().split())
    union(x,y)
    
print(sum([i < 0 for i in UF[1:]]))

Solution (Python):
N, M = map(int, input().split())
ans = [-1] * N

def find(x):
    global ans
    if ans[x] == -1:
        return x
    else:
        ans[x] = find(ans[x])
        return ans[x]
    
for _ in range(M):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    xx = find(x)
    yy = find(y)
    if ans[x] == ans[y] == -1:
        ans[y] = x
    elif xx == yy:
        continue
    else:
        ans[yy] = xx

n = 0
for i in ans:
    if i == -1:
        n += 1

print(n)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


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, readline().split())
xyz = [list(map(int, readline().split())) for i in range(m)]
uf = UnionFind(n)
ans = 0
for x, y, z in xyz:
    uf.union(x - 1, y - 1)
for i in range(n):
    if uf.find(i) == i:
        ans += 1
print(ans)

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

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

visited = [0] * N
def dfs(v):
    if visited[v] == 1:
        return
    visited[v] = 1
    for nv in edge[v]:
        dfs(nv)
ans = 0
for i in range(N):
    if visited[i] == 1:
        continue
    ans += 1
    dfs(i)

print(ans)

Solution (Python):
import sys

rl = sys.stdin.readline


class UnionFind:
    def __init__(self, n: int):
        self.n = n
        self.parents = [-1] * n
    
    def find(self, x: int):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x: int, y: int):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        if self.parents[y] < self.parents[x]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x: int):
        return -self.parents[self.find(x)]
    
    def same(self, x: int, y: int):
        return self.find(x) == self.find(y)
    
    def members(self, x: int):
        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 solve():
    N, M = map(int, rl().split())
    uf = UnionFind(N)
    for _ in range(M):
        x, y, _ = map(lambda z: int(z) - 1, rl().split())
        uf.union(x, y)
    print(uf.group_count())


if __name__ == '__main__':
    solve()

Solution (Python):

import sys
sys.setrecursionlimit(10**8)


class Node:
    def __init__(self, index):
        self.index = index
        self.ref = []
        self.visited = False

    def append(self, node):
        self.ref.append(node)
        node.ref.append(self)

    def visit(self):
        self.visited = True
        for r in self.ref:
            if not r.visited:
                r.visit()


def solve(N: int, M: int, X: "List[int]", Y: "List[int]", Z: "List[int]"):
    nodes = [Node(i) for i in range(N)]
    X = [x-1 for x in X]
    Y = [y-1 for y in Y]
    for i in range(M):
        nodes[X[i]].append(nodes[Y[i]])
    sum = 0
    for i in range(N):
        if not nodes[i].visited:
            sum += 1
            nodes[i].visit()
    print(sum)
    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


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

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if 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 is_same_group(self, x, y):
        return self.find(x) == self.find(y)

    def get_group_num(self):
        return sum([1 if self.par[i] == i else 0 for i in range(len(self.par))])


N, M = map(int, sys.stdin.readline().split())
uf = UnionFind(N)
for _ in range(M):
    x, y, z = map(int, sys.stdin.readline().split())
    x -= 1
    y -= 1
    uf.unite(x, y)

print(uf.get_group_num())

Solution (Python):



import sys
sys.setrecursionlimit(10**5)

def main():
  n, m = map(int, input().split())
  luf = [-1] * (n+1)
  
  def find(x):
    if luf[x] < 0:
      return x
    else:
      luf[x] = find(luf[x])
      return luf[x]
  
  def union(x, y):
    px, py = find(x), find(y)
    if px == py:
      return
    if px < py:
      px, py = py, px
    luf[px] += luf[py]
    luf[py] = px
  
  for _ in range(m):
    x, y, z = map(int, input().split())
    union(x, y)

  print(sum([x<0 for x in luf[1:]]))

if __name__=='__main__':
  main()

Solution (Python):
N, M = map(int, input().split())
par = [i for i in range(N)]
rank = [0 for i in range(N)]
def root(x):
  if par[x] == x:
    return x
  else:
    par[x] = root(par[x])
    return par[x]
def unite(x, y):
  x, y = root(x), root(y)
  if x != y:
    if rank[x] < rank[y]:
      par[x] = y
    else:
      par[y] = x
      if rank[x] == rank[y]:
        rank[x] += 1

for i in range(M):
  X, Y, Z = map(int, input().split())
  unite(X-1, Y-1)
for i in range(N):
  root(i)
print(len(set(par)))

Solution (Python):
n,m=map(int,input().split())
par=[-1]*n
def find(x):
    if par[x]<0:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def union(x,y):
    x,y=find(x),find(y)
    if x!=y:
        if x>y:
            x,y=y,x
        par[x]+=par[y]
        par[y]=x

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

ans=0
for i in range(n):
    if par[i]<0:
        ans+=1
        n+=par[i]
print(ans+n)

Solution (Python):
from collections import defaultdict
n, m = map(int, input().split())
friends_of = defaultdict(list)
for _ in range(m):
    x, y, _ = map(int, input().split())
    friends_of[x - 1].append(y - 1)
    friends_of[y - 1].append(x - 1)
ans = 0
visited = [False] * n
for i in range(n):
    if not visited[i]:
        ans += 1
        stack = [i]
        while len(stack) != 0:
            popped = stack.pop()
            visited[popped] = True
            for friend in friends_of[popped]:
                if not visited[friend]:
                    stack.append(friend)
print(ans)

Solution (Python):

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

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

    def unite(self, x, y):  
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

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

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

    def group_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.parent) if i == x]

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

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

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

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.unite(x,y)

print(uf.group_count())

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

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

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

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return

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

    def update_p(self):
        for x in range(self.n):
            self.root(x)

    def get_size(self, x):
        return self.size[self.find_set(x)]




def main():
    n, m = [int(i) for i in input().split()]
    uf = UnionFind(n)
    for _ in range(m):
        x, y, _ = [int(i) for i in input().split()]
        uf.unite(x-1, y-1)
    uf.update_p()
    print(len(set(uf.par)))

if __name__ == '__main__':
    main()

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

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            if self.parent[y] < self.parent[x]:
                x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x
            self._size -= 1

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

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

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


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

uf_tree = UnionFind(N)
for _ in range(M):
    X, Y, Z = map(int, input().split())
    X -= 1; Y -= 1;
    uf_tree.unite(X, Y)

print(uf_tree._size)

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

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            if self.parent[y] < self.parent[x]:
                x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x
            self._size -= 1

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

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

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


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

uf_tree = UnionFind(N)
for _ in range(M):
    X, Y, Z = map(int, input().split())
    X -= 1; Y -= 1;
    uf_tree.unite(X, Y)

print(uf_tree._size)

Solution (Python):
import sys

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

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

uf = UnionFind(n)

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

print(uf.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 = map(int, input().split())
uf = UnionFind(n)

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

print(uf.group_count())

Solution (Python):
N, M = map(int, input().split())
par = [i for i in range(N+1)]
h = [1 for _ in range(N+1)]

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

def unite(x,y):
    rx = root(x)
    ry = root(y)
    if h[rx] < h[ry]:
        rx, ry = ry, rx
    h[rx] += h[ry]
    par[ry] = rx

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

for i in range(1,N+1):
    par[i] = root(i)

print(len(set(par[1:])))