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):
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        
        
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        
        self.prev = defaultdict(lambda: None)

        
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


g = Graph()
N, M = [int(i) for i in input().split()]
magic = [1 for i in range(N)]

for i in range(M):
    u, v, w = [int(i) for i in input().split()]
    g.add_edge(u-1, v-1, w)
    g.add_edge(v-1, u-1, w)
    magic[u-1] = 0
    magic[v-1] = 0
ans = sum(magic)

d = Dijkstra(g, 0)

for i in range(N):
    if magic[i] == 0:
        d = Dijkstra(g, i)
        ans += 1
        for j in d.dist.keys():
            
            magic[j] = 1

print(ans)

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

    def root(self, A):
        if (self.Parent[A] < 0):
            return A
        else:
            self.Parent[A] = self.root(self.Parent[A])
            return self.Parent[A]
    def size(self, A):
        return int(-1 * self.Parent[self.root(A)])


    def connect(self, A, B):
        A = self.root(A)
        B = self.root(B)
        if (A == B):
            return False

        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())
X = [-1 for _ in range(M)]
Y = [-1 for _ in range(M)]
Z = [-1 for _ in range(M)]

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

ans = N

uni = Union(N)

for i in range(M):
    uni.connect(X[i], Y[i])

parents = []

for i in range(N):
    parents.append(uni.root(i))
print(len(set(parents)))

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

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7


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

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

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

        
        if x == y:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

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

    
    def is_tree(self, x):
        return self.tree[self.find(x)]

    
    def len(self):
        res = set()
        for i in range(self.n+1):
            res.add(self.find(i))
        
        return len(res) - 1

N,M=MAP()
uf=UnionFind(N)
for i in range(M):
    x,y,z=MAP()
    if not uf.same(x, y):
        uf.union(x, y)

print(uf.len())

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

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

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

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

    
    def size(self,x):
        q = UnionFind.find(self,x)
        return self.count[q]
n, m = map(int,input().split())
u = UnionFind(n)
ans = 0
for i in range(m):
    x,y,z = map(int,input().split())
    x -= 1
    y -= 1

    u.union(x,y)

for i in range(n):
    if u.par[i] == i:
        ans += 1

print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, N):
        
        self.par = [i for i in range(N)]
        return

    def root(self, x):
        if self.par[x] == x:
            return (x)
        else:
            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 union(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if (x == y):
            return False

        self.par[x] = min(x, y)
        self.par[y] = min(x, y)
        return True


def inpl():
    return list(map(int, input().split()))


N, M = inpl()
uf = UnionFind(N)
for i in range(M):
    x, y, z = inpl()
    x -= 1
    y -= 1
    uf.union(x, y)

ans = []
for i in range(N):
    ans.append(uf.root(i))
print(len(set(ans)))

Solution (Python):

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

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

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

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

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

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

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


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

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

Solution (Python):
class UnionFindEx:
    def __init__(self, size):
        
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    
        self.roots[r2] = r1
        return True


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

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

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

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

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

def tuika(l,a,b):
    l[a].append(b)
    l[b].append(a)

for i in range(M):
    X,Y,Z = map(int, input().split())
    if Z%2 == 0:
        tuika(onazi, X, Y)
    else:
        tuika(chigau, X, Y)
        


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

def func(i):
    stack = [i]
    colors[i] = 1

    while stack:
        node = stack.pop()
        for next_node in onazi[node]:
            if colors[next_node]==0:
                stack.append(next_node)
                colors[next_node] = colors[node]

        for next_node in chigau[node]:
            if colors[next_node]==0:
                stack.append(next_node)
                colors[next_node] = - colors[node]

result = 0
for i in range(1,N+1):
    if colors[i] == 0:
        result += 1
        func(i)
print(result)

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

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

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

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


N, M = [int(n) for n in input().split()]
X = [0]*M
Y = [0]*M
Z = [0]*M
UF = UnionFind(N)
adj = [[0, []] for _ in range(N)]
for i in range(M):
    X[i], Y[i], Z[i] = [int(n) for n in input().split()]
    Z[i] %= 2
    X[i] -= 1
    Y[i] -= 1
    UF.union(X[i], Y[i])
s = set([UF.find(0)])
ans = 1

for i in range(1, N):
    tmp = UF.find(i)
    if not(tmp in s):
        ans += 1
        s.add(tmp)
print(ans)

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

    def find(self, x):
        """
        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 と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]


def main():
    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)
    
    s = set(uf.par)
    print(len(s))


if __name__ == '__main__':
    main()

Solution (Python):
def connected_components(graph):
    seen = set()
    def component(n):
        nodes = set([n])
        while nodes:
            n = nodes.pop()
            seen.add(n)
            nodes |= set(graph[n]) - seen
            yield n
    for n in graph:
        if n not in seen:
            yield component(n)

def print_gen(gen):
    print(len([list(x) for x in gen]))

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

print_gen(connected_components(d))

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

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

    def unite(self, x, y):  
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if -self.v[x] < -self.v[y]:  
            x, y = y, x  
        self.v[x] += self.v[y]  
        self.v[y] = x  

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

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

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


N, M = map(int, input().split())
uf = UnionFind(N * 2)
for _ in range(M):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    if z % 2 == 0:
        uf.unite(x, y)
        uf.unite(x + N, y + N)
    else:
        uf.unite(x, y + N)
        uf.unite(x + N, y)



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

Solution (Python):
n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(m)]

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

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

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

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

u = UnionFind(n)
for i in range(m):
    x = a[i][0]
    y = a[i][1]
    z = a[i][2]
    u.union(x, y)

counter = []
for i in range(n+1):
    counter.append(u.find(i))

print(len(list(set(counter[1:]))))

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, XYZ):
    g = defaultdict(dict)
    for x, y, z in XYZ:
        g[x][y] = z % 2
        g[y][x] = z % 2

    ans = 0
    done = set()
    for i in range(1, N+1):
        if i in done:
            continue
        ans += 1
        q = deque([i])
        while q:
            u = q.popleft()
            done.add(u)
            for v in g[u]:
                if v not in done:
                    q.append(v)
                    done.add(v)
    return ans


def main():
    
    N, M = read_int_n()
    XYZ = [read_int_n() for _ in range(M)]
    print(slv(N, M, XYZ))

    
    


if __name__ == '__main__':
    main()

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

import collections

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

connected = collections.defaultdict(list)
for (a, b, _) in triples:
    connected[a].append(b)
    connected[b].append(a)

nodes = set(range(1, N + 1))
seen = set()
cnt = 0

for i in nodes:
    if i not in seen:
        cnt += 1
        stack = [i]
        while stack:
            state = stack.pop()
            for new_state in connected[state]:
                if new_state not in seen:
                    seen.add(new_state)
                    stack.append(new_state)

print(cnt)

Solution (Python):

import sys


class UnionFind(object):
    __slots__ = ["nodes"]

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

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

    def has_same_root(self, x, y) -> bool:
        return self.find(x) == self.find(y)
    
    def size(self, x) -> int:
        return -self.nodes[self.find(x)]

    def unite(self, x: int, y: int) -> None:
        if self.has_same_root(x, y):
            return

        root_x, root_y = self.find(x), self.find(y)
        if self.nodes[root_x] < self.nodes[root_y]:
            bigroot, smallroot = (root_x, root_y)
        else: 
            bigroot, smallroot = (root_y, root_x)
        self.nodes[bigroot] += self.nodes[smallroot]
        self.nodes[smallroot] = bigroot


def solve(N: int, M: int, X: "List[int]", Y: "List[int]", Z: "List[int]"):
    UFT = UnionFind(N)
    for i in range(M):
        UFT.unite(X[i], Y[i])
    cluster = set(UFT.find(i) for i in range(N))
    print(len(cluster))
    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)) - 1
        Y[i] = int(next(tokens)) - 1
        Z[i] = int(next(tokens)) % 2
    solve(N, M, X, Y, Z)

if __name__ == '__main__':
    main()

Solution (Python):
class UnionFind:
    def __init__(self, N):
        
        self.parent = [-1 for _ in range(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):
        A = self.root(A)
        B = self.root(B)

        if A == B:
            return False

        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())
    uni.connect(X-1, Y-1)

dict = {}
for i in range(N):
    r = uni.root(i)
    dict[r] = 1

print(len(dict))

Solution (Python):

import sys

sys.setrecursionlimit(10**6)


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

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

    def 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
        else:
            return False


def solve(N: int, M: int, X: "List[int]", Y: "List[int]", Z: "List[int]"):
    uf = UnionFind(N)
    for i in range(M):
        uf.union(X[i]-1, Y[i]-1)
    cnt = 0
    for elem in uf.table:
        if elem < 0:
            cnt += 1
    print(cnt)

    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 math
from functools import reduce

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]


def get_nums_l():
    return [ int(s) for s in input().split(" ")]


def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

n,m = get_nums_l()

groups = n
node_groups = [ i for i in range(n)]
group_sizes = [ 1 for _ in range(n)]
group_ranks = [ 0 for _ in range(n)]

edges = []
for i in range(m):
    tmp=input().split(" ")
    edges.append([int(tmp[0])-1, int(tmp[1])-1])


def root(i):
    if node_groups[i] == i:
        
        return i
    else:
        
        node_groups[i] = root(node_groups[i])
        
        
        return node_groups[i]

def same(a, b):
    return root(a) == root(b)

def size(i):
    return group_sizes[root(i)]

def unite(a, b):
    global groups

    a = root(a)
    b = root(b)

    if a == b:
        return
    
    
    groups -= 1

    if group_ranks[a] < group_ranks[b]:
        group_sizes[b] += size(a)
        node_groups[a] = b
    else:
        group_sizes[a] += size(b)
        node_groups[b] = a
        if group_ranks[a] == group_ranks[b]:
            group_ranks[a] += 1


for i in range(m-1, -1, -1):
    edge = edges[i]
    
    
    node_1 = edge[0]
    node_2 = edge[1]

    root_1 = root(node_1)
    root_2 = root(node_2)

    unite(root_1, root_2)
print(groups)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

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

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

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

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

n,m = getList()
uf = UnionFind(n)
for i in range(m):
    x, y, _ = getList()
    if not uf.same_check(x,y):
        uf.union(x,y)
        
for i in range(n+1):
    uf.find(i)


print(len(list(set(uf.par[1:]))))

Solution (Python):
from collections import deque
import sys
import math
sys.setrecursionlimit(10**6)
from collections import defaultdict
from collections import Counter
from collections import deque

n,m=map(int,input().split())
par=[i for i in range(n+1)]

def root(x):
    if x==par[x]:
        return x
    else:
        par[x]=root(par[x])
        return par[x]
def connect(x,y):
    rx=root(x)
    ry=root(y)
    if rx==ry:
        0
    else:
        par[rx]=ry
    return

for i in range(m):
    a,b,z=map(int,input().split())
    connect(a,b)

st=set()
for i in range(1,n+1):
    st.add(root(i))
print(len(st))

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 UnionFind():
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.size = [1] * N
        self.N = N

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

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

    
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if self.size[rx] < self.size[ry]:
            self.par[rx] = ry
            self.size[ry] += self.size[rx]
        else:
            self.par[ry] = rx
            self.size[rx] += self.size[ry]
            
import sys
input = sys.stdin.readline

n, m = (int(i) for i in input().split())
xyz = [[int(i)-1 for i in input().split()] for i in range(m)]

uf = UnionFind(n)
for x,y,z in xyz:
    if not uf.same(x,y):
        uf.unite(x,y)

dic = {}
for i in range(n):
    dic[uf.root(i)] = 1

print(len(dic))

Solution (Python):
def func(acc, tmp, N):
    for i in range(tmp,N):
        if acc[i]==0:
            return i
    return -1

N,M=[int(x) for x in input().split()]
con=[[] for i in range(N+1)]
acc=[0 for i in range(N+1)]
for m in range(M):
    X,Y,Z=[int(x) for x in input().split()]
    con[X].append(Y)
    con[Y].append(X)
ans=1
acc[0]=1
acc[1]=1
focus=[1]
L=1
tmp=1
while(L<N):
    newfocus=[]
    if len(focus)==0:
        c=func(acc, tmp, N)
        tmp=c+1
        focus=[c]
        acc[c]=1
        ans+=1
        L+=1
    for f in focus:
        for c in con[f]:
            if acc[c]==0:
                newfocus.append(c)
                acc[c]=1
                L+=1
    focus=newfocus[:]
print(ans)

Solution (Python):
class UnionFind:
    import sys
    sys.setrecursionlimit(100000)

    def __init__(self, n):
        self.parents = [i for i in range(n + 1)]

    def root(self, i):
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.root(self.parents[i])
            return self.parents[i]

    def unite(self, i, j):
        self.parents[self.root(self.parents[i])] = self.root(j)

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


def solve(N, XYZs):
    uf = UnionFind(N)
    for x, y, z in XYZs:
        uf.unite(x, y)
    return len(set([uf.root(i) for i in range(1, N + 1)]))


if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    XYZs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    print(solve(N, XYZs))

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

    def find(self, x):
        while(self.table[x] >= 0):
            x = self.table[x]
        return x

    def union(self, x, y):
        xp = self.find(x)
        yp = self.find(y)
        if xp != yp:
            if self.table[xp] <= self.table[yp]:
                self.table[xp] += self.table[yp]
                self.table[yp] = xp
            else:
                self.table[yp] += self.table[xp]
                self.table[xp] = yp

n, m = map(int, input().split())
clue = Unionfind(n)
for _ in range(m):
    x, y, _ = map(int, input().split())
    clue.union(x-1, y-1)
roots = set()
for i in range(n):
    roots.add(clue.find(i))
print(len(roots))