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

Solution (Python):
n,m=map(int,input().split())
class UnionFind:
    
    
    __slots__ = ["_size", "_first_idx", "_parents"]
    def __init__(self, size: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [-1] * (size + first_index)
    def find(self, x: int) -> int:
        if self._parents[x] < 0:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]
    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)
    def unite(self, x: int, y: int) -> bool:
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        if self._parents[x] > self._parents[y]:
            x, y = y, x
        self._parents[x] += self._parents[y]
        self._parents[y] = x
        return True
    def size(self, x: int) -> int:
        return -self._parents[self.find(x)]
    def group_count(self) ->int:
        return sum([1 for i in  self._parents if i<0])-self._first_idx
    def connected(self) ->bool:
        return self._parents[self.find(self._first_idx)]==-self._size

uf=UnionFind(n,1)
for i in range(m):
    x,y,z=map(int,input().split())
    uf.unite(x,y)
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 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())
XYZ = [list(map(int, input().split())) for _ in range(m)]

uf = uf = UnionFind(n)

for x, y, z in XYZ:
  x -= 1
  y -= 1
  uf.union(x, y)
  
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 size(self, x):
        return -self.parents[self.find(x)]

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

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

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

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

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

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

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

uf = UnionFind(N)

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


print(uf.group_count())

Solution (Python):
from collections import deque

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

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

visited = [False] * N

ans = 0
for i in range(N):
    if visited[i]:
        continue
    else:
        ans += 1

    q = deque([i])
    while q:
        cur = q.popleft()
        visited[cur] = True

        for next in edge[cur]:
            if visited[next]:
                continue
            visited[next] = True
            q.append(next)

print(ans)

Solution (Python):
from collections import deque

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

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

visited = [False] * N

ans = 0
for i in range(N):
    if visited[i]:
        continue
    else:
        ans += 1

    q = deque([i])
    while q:
        cur = q.pop()
        visited[cur] = True

        for next in edge[cur]:
            if visited[next]:
                continue
            visited[next] = True
            q.append(next)

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**5+1)

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

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

visited = [False] * N

ans = 0
def dfs(x):
    global ans
    if not visited[x]:
        ans += 1
    visited[x] = True

    for x_next in edge[x]:
        if visited[x_next]:
           continue 
        visited[x_next] = True
        dfs(x_next)

for i in range(N):
    dfs(i)

print(ans)

Solution (Python):
class UnionFind():
    '''
    cited from https://note.nkmk.me/python-union-find/
    '''
    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 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 = map(int, input().split())

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

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    from scipy.sparse.csgraph import connected_components  
    from scipy.sparse import csr_matrix
    
    N, M = map(int, input().split())  
    A, B, C = [0] * M, [0] * M, [1] * M  
    
    for i in range(M):
        A[i], B[i] ,_= map(int, input().split())
        A[i] -= 1  
        B[i] -= 1
    
    csr = csr_matrix((C, (A, B)), shape=(N, N))
    
    n, labels = connected_components(csr)
    print(n)

    
resolve()

Solution (Python):

from sys import setrecursionlimit


def find(parent, i):
    t = parent[i]
    if t < 0:
        return i
    t = find(parent, t)
    parent[i] = t
    return t


def unite(parent, i, j):
    i = find(parent, i)
    j = find(parent, j)
    if i == j:
        return
    parent[j] += parent[i]
    parent[i] = j


setrecursionlimit(10 ** 6)

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

parent = [-1] * N
for _ in range(M):
    X, Y, Z = map(int, input().split())
    unite(parent, X - 1, Y - 1)
print(len([x for x in parent if x < 0]))

Solution (Python):
class UnionFind:
    def __init__(self,N):
        self.root = list(range(N))
        self.size = [1] * (N)
        
    def find_root(self,x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x
    
    def merge(self,x,y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        sx,sy = self.size[x],self.size[y]
        if sx < sy:
            self.root[x] = y
            self.size[y] += sx
        else:
            self.root[y] = x
            self.size[x] += sy


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

uf = UnionFind(n)

answer = []
find_root = uf.find_root
merge = uf.merge
for i in range(m):
    x, y, z = xyz[i][0]-1, xyz[i][1]-1, xyz[i][2]
    merge(x,y)
s = set([])
for i in range(n):
    s.add(uf.find_root(i))
print(len(s))

Solution (Python):
import queue

n, m = list(map(int, input().split()))
dic = {}  
count = 0
q = queue.Queue()

for i in range(m):
  a, b, c = list(map(int, input().split()))
  if not a-1 in dic:
    dic[a-1]=[b-1]
  else:
    dic[a-1].append(b-1)
  
  if not b-1 in dic:
    dic[b-1]=[a-1]
  else:
    dic[b-1].append(a-1)

dp = [0]*n



for i in range(n):
  if dp[i]==0:
    count += 1
    dp[i]=count
    if i in dic:
      for j in dic[i]:
        dp[j]=count
        q.put(j)
    
    while not q.empty():
      temp = q.get()
      
      if temp in dic:
        for j in dic[temp]:
          if dp[j] == 0:
            dp[j]=count
            q.put(j)

print(count)

Solution (Python):
import sys
from io import StringIO
import unittest
import os


sys.setrecursionlimit(999999999)


class UnionFind:
    def __init__(self, n):
        """
        コンストラクタ
        :要素数 n:
        """
        self.n = n
        
        
        
        self.parents = [-1] * n

    def getroot(self, x):
        """
        所属する集合(ルートの番号)を取得する。
        :調査する要素 x:
        """
        
        if self.parents[x] < 0:
            return x
        else:
            
            
            self.parents[x] = self.getroot(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """
        2つの要素が所属する集合をを同じ集合に結合する。
        :結合する要素(1つ目) x:
        :結合する要素(2つ目) y:
        """
        
        x = self.getroot(x)
        y = self.getroot(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):
        """
        指定した集合に属する要素数を取得する。
        :調査する集合 x:
        """
        
        return -self.parents[self.getroot(x)]

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

    def members(self, x):
        root = self.getroot(x)
        return [i for i in range(self.n) if self.getroot(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 resolve(test_def_name=""):
    
    
    
    
    
    

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

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

    
    uf = UnionFind(n + 1)
    
    for rule in rules:
        uf.union(rule[0], rule[1])

    
    print(uf.group_count() - 1)



class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3 1
1 2 1"""
        output = """2"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """6 5
1 2 1
2 3 2
1 3 3
4 5 4
5 6 5"""
        output = """2"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """100000 1
1 100000 100"""
        output = """99999"""
        self.assertIO(test_input, output)

    
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)



if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        
        resolve()

    else:
        
        unittest.main()

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


class UnionFind():
    def __init__(self, N):
        self._parent = [n for n in range(0, N)]
        self._size = [1] * N

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

    def unite(self, x, y):
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()

def main():
    N,M = mi()
    U = UnionFind(2*N+1)

    for i in range(1,N+1):
        U.unite(i,N+i)

    minus = 0
    for i in range(M):
        x,y,z = mi()
        U.unite(x,y)

    print(U.calc_group_num() - 1)




if __name__ == "__main__":
  main()

Solution (Python):
from collections import deque
N, M = map(int, input().split())
Clear = [-1]*N
T = [[] for _ in range(N)]
ans = 0
for i in range(M):
    X, Y, Z = map(int, input().split())
    X -= 1
    Y -= 1
    T[X].append(Y)
    T[Y].append(X)

for i in range(N):
    if Clear[i] == -1:
        ans += 1
        Clear[i] = 1
        P = deque([i])
        while(len(P) > 0):
            t = P.popleft()
            for j in T[t]:
                if Clear[j] == -1:
                    Clear[j] = 1
                    P.append(j)
print(ans)

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


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 main():
    N, M, *XYZ = map(int, read().split())
    uf = UnionFind(N)
    for x, y, z in zip(XYZ[::3], XYZ[1::3], XYZ[2::3]):
        uf.union(x - 1, y - 1)

    print(uf.group_count())
    return


if __name__ == '__main__':
    main()

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 same(self, x, y):
        return self.find(x) == self.find(y)

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

print(uf.group_count())

Solution (Python):



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

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

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

    def count(self, x):
        return -self.root[self.find(x)]

if __name__ == '__main__':
    n, m = map(int, input().split())
    uf = UnionFind(n)

    for _ in range(m):
        xi, yi, zi = map(int, input().split())
        xi -= 1
        yi -= 1
        uf.unite(xi, yi)

    count = 0
    for i in range(n):
        if uf.root[i] < 0:
            count += 1
    print(count)

Solution (Python):
import sys
import itertools

import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


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

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

visited = [False for _ in range(N)]
def dfs(v):
    if visited[v]:
        return False
    visited[v] = True
    for u in adj[v]:
        dfs(u)
    return True


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

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



n,m = map(int, input().split())
from collections import defaultdict
ns = defaultdict(set)
for i in range(m):
    x,y,z = map(int, input().split())
    x -= 1
    y -= 1
    ns[x].add(y)
    ns[y].add(x)
    
seen = [False]*n
ans = 0
for start in range(n):
    if seen[start]:
        continue
    q = [(start, -1)]
    seen[start] = True
    val = None
    while q:
        u, prev = q.pop()
        for v in ns[u]:
            if v==prev:
                continue
            if seen[v]:
                val = 1
            else:
                seen[v] = True
                q.append((v, u))
    if val is None:
        val = 1
    ans += val
print(ans)

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

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n)
        self.size = [1] * (n)
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        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 all_find(self):
        for n in range(len(self.par)):
            self.find(n)

uf = UnionFind(n)

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

root = set([])

for i in range(n):
    root.add(uf.find(i))

print(len(root))

Solution (Python):
from collections import Counter

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

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n)
        self.size = [1] * (n)
    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        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 all_find(self):
        for n in range(len(self.par)):
            self.find(n)

uf = UnionFind(n)

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

root = set([])

for i in range(n):
    root.add(uf.find(i))

print(len(root))

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]


n, m = map(int, input().split())
xyz = sorted([list(map(int, input().split())) for _ in range(m)])

uf = Unionfind(n)
for x, y, z in xyz:
    uf.union(x - 1, y - 1)
print(len(uf.roots()))

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

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

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


n, m = map(int, input().split())
xyz = sorted([list(map(int, input().split())) for _ in range(m)])

uf = Unionfind(n)
for x, y, z in xyz:
    uf.union(x - 1, y - 1)
print(len(uf.roots()))

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 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 same(self, x, y):
        return self.find(x) == self.find(y)

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

query = []

for i in range(M):
    a, b, c = getNM()
    query.append([a, b, c])

U = UnionFind(N)
for i in query:
    U.union(i[0] - 1, i[1] - 1)

print(U.group_count())

Solution (Python):
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline



def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


class UnionFind:

    def __init__(self, N: int):
        
        
        self.d = [-1 for _ in range(N)]

    def root(self, x: int) -> int:
        if self.d[x] < 0:
            return x
        self.d[x] = self.root(self.d[x])
        return self.d[x]

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

    def same(self, x: int, y: int) -> bool:
        return self.root(x) == self.root(y)

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

    def show(self):
        m = {}
        for n in range(len(self.d)):
            r = self.root(n)

            if r not in m:
                m[r] = [n]
            else:
                m[r].append(n)

        print("root -> childs")
        print("---------------------")
        for key in m:
            print("{} -> {}".format(key, m[key]))


def main():
    n, m = geta(int)

    uf = UnionFind(2*n)

    ans = n

    for _ in range(m):
        x, y, z = geta(int)

        united = False
        if z & 1 == 0:
            united = uf.unite(2*x-2, 2*y-2) and uf.unite(2*x-1, 2*y-1)
        else:
            united = uf.unite(2*x-2, 2*y-1) and uf.unite(2*x-1, 2*y-2)

        if united:
            ans -= 1

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):


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

def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True


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


def size(x):
    return -par[find(x)]


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


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

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

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

Solution (Python):
class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.ranks = [0 for _ in range(n)]

    def root(self, node):
        parent_node = self.parents[node]
        if parent_node == node:
            return node
        root_node = self.root(parent_node)
        self.parents[node] = root_node  
        return root_node

    def union(self, one_node, other_node):
        one_root = self.root(one_node)
        other_root = self.root(other_node)
        if one_root == other_root:
            return
        if self.ranks[one_root] < self.ranks[other_root]:
            self.parents[one_root] = other_root
        else:
            self.parents[other_root] = one_root
            if self.ranks[one_root] == self.ranks[other_root]:
                self.ranks[one_root] += 1


def main():
    N, M = list(map(int, input().split(' ')))
    tree = UnionFind(N)
    for _ in range(M):
        x, y, _ = list(map(int, input().split(' ')))
        tree.union(x - 1, y - 1)
    roots = list(map(lambda n: tree.root(n), range(N)))
    print(len(set(roots)))


if __name__ == '__main__':
    main()