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, deque
dic = defaultdict(list)

N, M = map(int, input().split())
hint= [-1]*N

for _ in range(M):
    x, y, z = map(int, input().split())
    dic[x].append(y)
    dic[y].append(x)
    hint[x-1]=0
    hint[y-1]=0
    
count = 0
ans=0
for i in range(N):
    if hint[i]==0:
        count+=1
        hint[i]=count
        queue = deque()
        for j in dic[i+1]:
            if hint[j-1]==0:
                queue.append(j)
                hint[j-1]=count
        while queue:
            x = queue.popleft()
            for k in dic[x]:
                if hint[k-1]==0:
                    hint[k-1]=count
                    queue.append(k)        
        continue
    elif hint[i]==-1:
        ans+=1
print(ans+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 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())
      
(n, m), *q = [list(map(int, o.split())) for o in open(0)]
UF = UnionFind(n)
for x, y, _ in q:
    UF.union(x - 1, y - 1)
print(UF.group_count())

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
import marshal


class Graph:
    def __init__(self, n, directed=False, decrement=True, destroy=False, edges=[]):
        self.n = n
        self.directed = directed
        self.decrement = decrement
        self.destroy = destroy
        self.edges = [set() for _ in range(self.n)]
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        for x, y in edges:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].add(y)
        if self.directed == False:
            self.edges[y].add(x)

    def add_adjacent_list(self, i, adjacent_list):
        if self.decrement:
            self.edges[i] = set(map(lambda x: x - 1, adjacent_list))
        else:
            self.edges[i] = set(adjacent_list)

    def bfs(self, start=1, goal=-1, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if self.decrement:
            start -= 1
            goal -= 1
        if not save:
            self.parent = [-1] * self.n
        p, t = start, time
        self.parent[p] = -2
        next_set = deque([(p, t)])

        while next_set:
            p, t = next_set.popleft()
            for q in self.edges[p]:
                if self.parent[q] != -1:
                    continue
                if q == goal:
                    return t + 1
                self.parent[q] = p
                next_set.append((q, t + 1))
        return -1

    def connection_counter(self):
        """
        :return: 連結成分の個数。有効グラフではあまり意味がない。
        """
        cnt = 0
        self.parent = [-1] * self.n
        for start in range(self.n):
            if self.parent[start] == -1:
                cnt += 1
                self.bfs(start + self.decrement, save=True)
        return cnt





N, M = map(int, input().split())
graph = Graph(N, directed=False, decrement=True, destroy=False)
for _ in range(M):
    x, y, z = map(int, input().split())
    graph.add_edge(x, y)

print(graph.connection_counter())

Solution (Python):
from collections import deque

N, M = map(int, input().split())
a = [-1 for _ in range(N)]
visited = [0 for _ in range(N)]
cond = [[[],[]] for _ in range(N)]
count = 0
for _ in range(M):
    x, y, z = map(int, input().split())
    if z % 2 == 0:
        cond[x-1][0].append(y-1)
        cond[y-1][0].append(x-1)
    else:
        cond[x-1][1].append(y-1)
        cond[y-1][1].append(x-1)
for i in range(N):
    if (not cond[i][0] and not cond[i][1]) or visited[i]:
        continue
    else:
        count += 1
        check = deque([(i, 0)])
        while check:
            num, eo = check.popleft()
            visited[num] = 1
            a[num] = eo
            for next in cond[num][0]:
                if visited[next]:
                    continue
                check.append((next, eo))
            for next in cond[num][1]:
                if visited[next]:
                    continue
                check.append((next, (eo+1)%2))
ans = a.count(-1) + count
print(ans)

Solution (Python):
import sys

input = sys.stdin.readline


class UnionFind:
    """Union Find class.

    "Path compression" and "Union by rank" are used.

    References:
        <https://en.wikipedia.org/wiki/Disjoint-set_data_structure>
    """

    def __init__(self, N):
        self.N = N
        self.__make_set()

    def __make_set(self):
        self._parent = list(range(self.N + 1))
        self._rank = [0] * (self.N + 1)
        self._size = [1] * (self.N + 1)

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

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

        if x_root == y_root:
            return

        x_rank = self._rank[x_root]
        y_rank = self._rank[y_root]
        if x_rank > y_rank:
            self._parent[y_root] = x_root
            self._size[x_root] += self._size[y_root]
        elif x_rank < y_rank:
            self._parent[x_root] = y_root
            self._size[y_root] += self._size[x_root]
        else:
            self._parent[y_root] = x_root
            self._rank[x_root] += 1
            self._size[x_root] += self._size[y_root]

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

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


def main():
    N, M = map(int, input().split())
    uf = UnionFind(N)
    for _ in range(M):
        X, Y, _ = map(int, input().split())
        uf.union(X, Y)

    s = set()
    for i in range(1, N + 1):
        s.add(uf.find(i))

    ans = len(s)
    print(ans)


if __name__ == "__main__":
    main()

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

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

  def union(self, u,v):
    p1,p2 = self.find(u),self.find(v)
    if p1==p2: return
    if p1 > p2:
      p1,p2 = p2,p1
    self.parents[p1] += self.parents[p2]
    self.parents[p2] = p1

  def same(self, u,v):
    return self.find(u) == self.find(v)

  def weight(self, u):
    p = self.find(u)
    return -self.parents[p]

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

uf = UF(N+1)
for i in range(M):
  u,v,z = map(int,input().split())
  uf.union(u,v)

ans = 0
for i in range(1, N+1):
  if uf.parents[i] < 0:
    ans += 1

print(ans)

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    
    class UnionFind():
        """
        parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
        find(x):要素xの属するグループの根を返す
        size(x):要素xの属するグループの要素数を返す
        same(x,y):x,yが同じグループに属しているか返す
        重いかも！　　members(x):要素xが属するグループに属する要素をリストで返す
        roots:全ての根の要素を返す
        group_count():グループの数を返す
        重いかも！　all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
        """
        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())
        
    


    mod=10**9+7
    N,M=MI()
    uf=UnionFind(N)
    
    
    for i in range(M):
        x,y,z=MI()
        x-=1
        y-=1
        uf.union(x,y)
        
    print(uf.group_count())
    
    

main()

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

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

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

N, M = [int(_) for _ in input().split()]
uf = UnionFind(N)

for i in range(M):
    X, Y, Z = [int(_) for _ in input().split()]
    uf.union(X-1, Y-1)

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

Solution (Python):







"""
Union-find data structure.
"""

from networkx.utils import groups


class UnionFind:
    """Union-find data structure.

    Each unionFind instance X maintains a family of disjoint sets of
    hashable objects, supporting the following two methods:

    - X[item] returns a name for the set containing the given item.
      Each set is named by an arbitrarily-chosen one of its members; as
      long as the set remains unchanged it will keep the same name. If
      the item is not yet part of a set in X, a new singleton set is
      created for it.

    - X.union(item1, item2, ...) merges the sets containing each item
      into a single larger set.  If any item is not yet part of a set
      in X, it is added to X as one of the members of the merged set.

      Union-find data structure. Based on Josiah Carlson's code,
      http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
      with significant additional changes by D. Eppstein.
      http://www.ics.uci.edu/~eppstein/PADS/UnionFind.py

    """

    def __init__(self, elements=None):
        """Create a new empty union-find structure.

        If *elements* is an iterable, this structure will be initialized
        with the discrete partition on the given set of elements.

        """
        if elements is None:
            elements = ()
        self.parents = {}
        self.weights = {}
        for x in elements:
            self.weights[x] = 1
            self.parents[x] = x

    def __getitem__(self, object):
        """Find and return the name of the set containing the object."""

        
        if object not in self.parents:
            self.parents[object] = object
            self.weights[object] = 1
            return object

        
        path = [object]
        root = self.parents[object]
        while root != path[-1]:
            path.append(root)
            root = self.parents[root]

        
        for ancestor in path:
            self.parents[ancestor] = root
        return root

    def __iter__(self):
        """Iterate through all items ever found or unioned by this structure.

        """
        return iter(self.parents)

    def to_sets(self):
        """Iterates over the sets stored in this structure.

        For example::

            >>> partition = UnionFind('xyz')
            >>> sorted(map(sorted, partition.to_sets()))
            [['x'], ['y'], ['z']]
            >>> partition.union('x', 'y')
            >>> sorted(map(sorted, partition.to_sets()))
            [['x', 'y'], ['z']]

        """
        
        for x in self.parents.keys():
            _ = self[x]  

        
        for block in groups(self.parents).values():
            yield block

    def union(self, *objects):
        """Find the sets containing the objects and merge them all."""
        roots = [self[x] for x in objects]
        
        heaviest = max(roots, key=lambda r: self.weights[r])
        for r in roots:
            if r != heaviest:
                self.weights[heaviest] += self.weights[r]
                self.parents[r] = heaviest


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

    u = UnionFind(range(1, N + 1))

    for x, y, z in XYZ:
        u.union(x, y)

    print(len(list(u.to_sets())))


main()

Solution (Python):
"""
UnionFind木を使う。
Ai,Aj,Zの情報が与えられたら、Ai,AjをUniteする。
同じグループにいるA同士は連鎖関係に合って、グループ内の一つでも数字がわかれば連鎖的に同グループのAの値もわかる。
この問題の問に対する答えは、グループの数となる。
"""
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.size = [1]*(n+1)
    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 unite(self,x,y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            return
        if self.size[xRoot]>self.size[yRoot]:
            self.parents[yRoot] = xRoot
            self.size[xRoot] += self.size[yRoot]
            self.size[yRoot] = 0
        else:
            self.parents[xRoot] = yRoot
            self.size[yRoot] += self.size[xRoot]
            self.size[xRoot] = 0

N,M = map(int,input().split())
tree = UnionFind(N)
for _ in range(M):
    x,y,z = map(int,input().split())
    tree.unite(x,y)
print(N-tree.size.count(0))

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()

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 _ in range(m):
        x,y,z=map(int, input().split())
        uf.union(x-1,y-1)
    print(uf.group_count())




 
if __name__=='__main__':
    main()

Solution (Python):
class UnionFind:

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


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


    def root(self, x):
        path = []
        while self.par[x] >= 0:
            path.append(x)
            x = self.par[x]
        for y in path:
            self.par[y] = x
        return x


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


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


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

a = [0] * n
for i in range(n):
    a[uni.root(i)] = 1

print(sum(a))

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

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

class Union_Find:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.rank = [1 for i in range(n)]
    
    def find(self,x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])
    
    def unite(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        else:
            if self.rank[px] == self.rank[py]:
                self.parent[py] = px
                self.rank[px] += 1
            elif self.rank[px] > self.rank[py]:
                self.parent[py] = px
            else:
                self.parent[px] = py
uftree = Union_Find(N+1)

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

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

print(result)

Solution (Python):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

INF = 10**18
eps = 10**-7

N,Q = map(int,readline().split())


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

rank = [0]*(N+1)

size = [1]*(N+1)


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


def unite(x,y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y              
        size[y] += size[x]      
    else:
        par[y] = x              
        size[x] += size[y]      
        if rank[x] == rank[y]:
            rank[x] += 1
 
for i in range(Q):
    x,y,z = map(int,readline().split())
    unite(x,y)

ans = [0]*(N+1)
for i in par:
    ans[root(i)] += 1

aaa = 0
for i in range(N+1):
    if ans[i] > 0:
        aaa += 1
print(aaa-1)

Solution (Python):
import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue



sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().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())


def main():
    n, m = ns()
    uf = UnionFind(n)

    for _ in range(m):
        x, y, z = ns()
        uf.union(x - 1, y - 1)

    ans = uf.group_count()
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import re
import math
import collections
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue



sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().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())


def main():
    n, m = ns()
    uf = UnionFind(n)

    for _ in range(m):
        x, y, z = ns()
        uf.union(x - 1, y - 1)

    ans = uf.group_count()
    print(ans)


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

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

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

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

Solution (Python):
a = [int(s) for s in input().split()]
g = {i: [] for i in range(1, a[0] + 1)}

for i in range(a[1]):
    c = [int(s) for s in input().split()]
    g[c[0]].append(c[1])
    g[c[1]].append(c[0])

j = 0
d = {i: False for i in range(1, a[0] + 1)}

for i in range(1, a[0] + 1):
    if d[i] == False:
        j += 1 
        d[i] = True
        if g[i] != []:
            Q = [i]
            while(Q != []):
                r = Q.pop(0)
                if g[r] != []:
                    for m in g[r]:
                        if d[m] == False:
                            d[m] = True
                            Q.append(m)
print(j)

Solution (Python):

import sys 
sys.setrecursionlimit(10**6)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

def union(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 = map(int,readline().split())
par = [-1]*(N+1)
for i in range(M):
    x,y,z = map(int,readline().split())
    union(x,y)
print(sum(1 for i in par[1:] if i < 0))

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())
XYZs = [list(map(lambda x: int(x)-1, input().split())) for _ in range(M)]

uf = UnionFind(N)

for XYZ in XYZs:
    uf.union(XYZ[0], XYZ[1])

print(uf.group_count())

Solution (Python):
import sys
from collections import defaultdict


def input():
    return sys.stdin.readline().rstrip()


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())
        uf.union(x-1,y-1)

    print(uf.group_count())



if __name__ == "__main__":
    main()

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

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

def uf_find(x):
    while uf[x]!=x:
        x=uf[x]
    return x

for i in range(m):
    x,y,z=map(int,input().split())
    a,b=uf_find(x),uf_find(y)
    if a>b:
        a,b=b,a
    uf[b]=a

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

Solution (Python):
import sys
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007



def main():
	
	n, m = tin()
	
	is_open=[-1]*n
	graph = [[] for _ in range(n)]
	for _ in range(m):
		x, y, _ = tin()
		graph[x-1].append(y-1)
		graph[y-1].append(x-1)
		
	ret = 0
	for i in range(n):
		if is_open[i] > 0:
			continue
		ret += 1
		q=collections.deque()
		q.append(i)
		is_open[i] = 1
		while q:
			pos = q.pop()
			for t in graph[pos]:
				if is_open[t] > 0:
					continue
				is_open[t] = 1
				q.append(t)
	return ret
		
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

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


class UF:
    def __init__(self, n):
        self.n = n
        self.g = list(range(n))
        self.vertices = list(range(n))

    def union(self, i0, i1):
        g0, g1 = self.find(i0), self.find(i1)
        g0, g1 = min(g0, g1), max(g0, g1)
        self.g[g1] = g0

    def find(self, i):
        path = []
        while self.g[i] != i:
            path.append(i)
            i = self.g[i]

        for j in path:
            self.g[j] = i

        return i

uf = UF(n)

for x, y in xy:
    uf.union(x, y)

g = set()
for x in range(n):
    g.add(uf.find(x))

answer = len(g)
print(answer)