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):
class UnionFind:
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.components = n

    def root(self, x):
        if self.p[x] == x:
            return x
        else:
            self.p[x] = self.root(self.p[x])
            return self.p[x]
    
    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            self.p[x] = y
            self.components -= 1
    
    def same(self, x,y):
        return (self.root(x) == self.root(y))
N, M = map(int,input().split())

UF = UnionFind(N)

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

print(UF.components)

Solution (Python):
import networkx as X
n,m=map(int,input().split())
g=X.Graph()
for i in range(n):g.add_node(i+1)
for i in range(m):x,y,z=map(int,input().split());g.add_edge(x,y)
print(X.number_connected_components(g))

Solution (Python):

class UnionFind:
    def __init__(self, n):
        self.par = list(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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        elif self.rank[x] < self.rank[y]:
            x, y = y, x

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

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

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


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

tree = UnionFind(N)
for x, y, z in X:
    tree.unite(x - 1, y - 1)


for x in range(N):
    tree.find(x)

print(len(set(tree.par)))

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(lambda x: int(x)-1, input().split())
    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(lambda x: int(x)-1, input().split())
    uf.union(X, Y)
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 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(lambda x: int(x)-1, input().split())
    uf.union(X, Y)
ans = [uf.find(x) for x in uf.roots()]
print(len(set(ans)))

Solution (Python):

from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.size[x] < self.size[y]:
                x,y = y,x
            self.parents[y] = x
            self.size[x] += self.size[y]

def main():
    N, M = map(int, input().split())
    uf = UnionFind(N)
    for _ in range(M):
        X, Y, Z = map(lambda x: int(x)-1, input().split())
        uf.union(X, Y)
    
    ans = [uf.find(x) for x in uf.parents]
    print(len(set(ans)))

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 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())
  uf.union(X-1, Y-1)

print(uf.group_count())

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
n,m = map(int, input().split())

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

ans = [-1]*n
def hoge(parent, pos):
  for i in rel[pos]:
    if ans[i] >= 0:
      continue
    ans[i] = pos
    hoge(pos, i)
  return

cnt = 0
for i in range(n):
  if ans[i] < 0:
    hoge(0, i)
    cnt += 1

print(cnt)

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


def read():
    N, M = map(int, input().strip().split())
    XYZ = []
    for i in range(M):
        x, y, z = map(int, input().strip().split())
        XYZ.append((x, y, z))
    return N, M, XYZ


class UnionFind():
    """Union-Find木の実装
    """

    def __init__(self, n):
        self.n = n
        self.parent = [x for x in range(n)]

    def find(self, x):
        """要素xが所属するグループを返す
        """
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def union(self, x, y):
        """要素x, yがそれぞれ所属するグループを併合する
        """
        x = self.find(x)
        y = self.find(y)
        if x > y:
            x, y = y, x
        self.parent[y] = x

    def parents(self):
        return [self.find(x) for x in range(self.n)]


def solve(N, M, XYZ):
    uf = UnionFind(N)
    for x, y, z in XYZ:
        uf.union(x-1, y-1)
    C = Counter(uf.parents())
    return len(C)


if __name__ == '__main__':
    inputs = read()
    print(solve(*inputs))

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

card = [[] for _ in range(n)]

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

checked = [False] * n

count = 0
for i in range(n):
    if checked[i]:
        continue
    count += 1
    q = [i]
    while q:
        j = q.pop()
        checked[j] = True
        for k in card[j]:
            if not checked[k]:
                q.append(k)
print (count)

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

card = [[] for _ in range(n)]

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

checked = [False] * n

count = 0
from collections import deque
for i in range(n):
    if checked[i]:
        continue
    count += 1
    q = deque([i])
    while q:
        j = q.popleft()
        checked[j] = True
        for k in card[j]:
            if not checked[k]:
                q.append(k)
print (count)

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

card = [[] for _ in range(n)]

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

checked = [False] * n

count = 0
import queue
q = queue.Queue()
for i in range(n):
    if checked[i]:
        continue
    count += 1
    q.put(i)
    while not q.empty():
        j = q.get()
        checked[j] = True
        for k in card[j]:
            if not checked[k]:
                q.put(k)

print (count)

Solution (Python):
def main():
    n,m = map(int,input().split())
    cards = [-1 for i in range(n)]
    mg = {}
    for i in range(n):
        mg[i+1] = []
    for i in range(m):
        x,y,z = map(int,input().split())
        mg[x].append(y)
        mg[y].append(x)
    ans = 0
    for i in range(n):
        if cards[i]==-1:
            ans += 1
            cards[i] = 0
            que = [i]
            while len(que)>0:
                s = que.pop(0)
                for v in mg[s+1]:
                    if cards[v-1] == 0:
                        continue
                    cards[v-1] = 0
                    que.append(v-1)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque


N,M=list(map(int,input().split()))
graph=[[] for _ in range(N+1)]
for _ in range(M):
    a,b,c=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    

seen=[False]*(N+1)


count=0

for i in range(1,N+1):
    if seen[i]==False:
        seen[i]=True
        S=deque([i])
        
        while S:
            v=S.popleft()
            
            for i in graph[v]:
                if seen[i]==False:
                    seen[i]=True
                    S.append(i)
        count+=1

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

def solve():
    N,M = map(int,input().split())
    uf = UnionFind(N)
    for i in range(M):
        x,y,z = map(int,input().split())
        x -= 1
        y -= 1
        uf.unite(x,y)
    
    st = set()

    for i in range(N):
        st.add(uf.find(i))
    
    print(len(st))
    
if __name__ == '__main__':
    solve()

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 num_roots(self):
    return len([i for i, x in enumerate(self.parents) if x < 0])

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

  def num_members(self,x):
    return abs(self.parents[self.find(x)])

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

N, M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
  a,b,c = map(int, input().split())
  uf.union(a-1,b-1)

print(uf.num_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 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 num_roots(self):
    return len([i for i, x in enumerate(self.parents) if x < 0])

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

  def num_members(self,x):
    return abs(self.parents[self.find(x)])

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

N, M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
  a,b,c = map(int, input().split())
  uf.union(a-1,b-1)

print(uf.num_roots())

Solution (Python):
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(M):
  a,b,c = map(int, input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)

from collections import deque

ans = 0
visited = [False]*N
d = deque()
for i in range(N):
  if visited[i]==False:
    visited[i]=True
    d.append(i)
    while len(d)>0:
      v = d.popleft()
      for w in edge[v]:
        if visited[w]==False:
          visited[w]=True
          d.append(w)
    ans += 1
print(ans)

Solution (Python):
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(M):
  a,b,c = map(int, input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)

from collections import deque

ans = 0
visited = [False]*N
d = deque()
for i in range(N):
  if visited[i]==False:
    visited[i]=True
    d.append(i)
    while len(d)>0:
      v = d.popleft()
      for w in edge[v]:
        if visited[w]==False:
          visited[w]=True
          d.append(w)
    ans += 1
print(ans)

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

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

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

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

    if x == y:
      return

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

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

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

uf = UnionFind(N)

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

Solution (Python):
def find(x):
    while x!=T[x][0]:
        x = T[x][0]
    return x
def union(x,y):
    ax = find(x)
    ay = find(y)
    if T[ax][1]>T[ay][1]:
        T[ay][0] = ax
    elif T[ax][1]==T[ay][1]:
        T[ay][0] = ax
        T[ax][1] += 1
    else:
        T[ax][0] = ay
N,M = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(M)]
T = {i:[i,1] for i in range(1,N+1)}
for j in range(M):
    x,y = A[j][0],A[j][1]
    union(x,y)
B = [0 for _ in range(N+1)]
for i in range(1,N+1):
    B[i] = find(i)
C = {}
for i in range(1,N+1):
    b = B[i]
    if b not in C:
        C[b] = 0
    C[b] += 1
print(len(C))

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(M):
  a,b,c = map(int, input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)

def dfs(v):
  if len(edge[v])==0:
    return 0
  for u in edge[v]:
    if visited[u]==False:
      visited[u]=True
      dfs(u)
  return 0

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

Solution (Python):
N, M, *X = map(int, open(0).read().split())


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

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

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

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

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

    def num_union(self):
        return self.u


u = UnionFind(N)
for x, y, z in zip(*[iter(X)]*3):
    u.unite(x-1, y-1)
print(u.num_union())

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

par = [0] * n
rank = [0] * n


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


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

def unite(x , y):
    rx = find(x)
    ry = find(y)
    
    if rx == ry:
        return
    
    if rank[rx] < rank[ry]:
        par[rx] = ry
    elif rank[rx] > rank[ry]:
        par[ry] = rx
    else:
        par[ry] = x
        rank[rx] += 1
        
for i in range(m):
    x,y,z = map(int, input().split())
    
    unite(x-1,y-1)
    
from collections import Counter
c = [find(i) for i in range(n)]

print(len(Counter(c)))

Solution (Python):


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
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 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=MI()
u=UnionFind(n)
for i in range(m):
    a,b,c=MI()
    u.union(a-1,b-1)
print(u.group_count())

Solution (Python):

from typing import Set


class UnionFind:
    """Union-Find: O(α(N))"""

    __slots__ = ["_data_size", "_first_idx", "_parents"]

    def __init__(self, data_size: int, is_zero_origin: bool = True) -> None:
        self._data_size = data_size
        self._first_idx = 0 if is_zero_origin else 1
        self._parents = [-1] * (data_size + self._first_idx)

    def __getitem__(self, x: int) -> int:
        """Find the group (root) of vertex x."""
        if self._parents[x] < 0:
            return x
        self._parents[x] = self[self._parents[x]]
        return self._parents[x]

    def __len__(self) -> int:
        """Count the number of groups (roots)."""
        return len(self.groups)

    @property
    def groups(self) -> Set[int]:
        """Return the set of groups (roots)."""
        return {
            self[x] for x in range(self._first_idx, self._data_size + self._first_idx)
        }

    def is_connected(self, x: int, y: int) -> bool:
        """Return whether two vertices x and y are connected or not."""
        return self[x] == self[y]

    def unite(self, x: int, y: int) -> None:
        """Unite two groups of vertices x and y."""
        x, y = self[x], self[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 main():
    N, _, *X = map(int, open(0).read().split())
    tree = UnionFind(N, is_zero_origin=False)
    for x, y, _ in zip(*[iter(X)] * 3):
        tree.unite(x, y)
    print(len(tree))


if __name__ == "__main__":
    main()

Solution (Python):

from typing import List


def main():
    def dfs(source: int) -> None:
        stack = [source]
        is_visited[source] = True
        while stack:
            u = stack.pop()
            for v in graph[u]:
                if is_visited[v]:
                    continue
                is_visited[v] = True
                stack.append(v)

    N, M, *X = map(int, open(0).read().split())
    graph: List[List[int]] = [[] for _ in range(N + 1)]
    for x, y, _ in zip(*[iter(X)] * 3):
        graph[x].append(y), graph[y].append(x)

    is_visited = [False] * (N + 1)
    res = 0
    for i in range(1, N + 1):
        if is_visited[i]:
            continue
        res += 1
        dfs(i)
    print(res)


if __name__ == "__main__":
    main()

Solution (Python):
N, M = map(int, input().split())
G = [[] for _ in range(N)]

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

lst = []
visited = [0]*N
for i in range(N):
    if visited[i] == 1:continue
    temp = [i]
    lst1 = [i]
    visited[i] = 1
    while temp:
        p = temp.pop()
        for q in G[p]:
            if visited[q] == 0:
                visited[q] = 1
                lst1.append(q)
                temp.append(q)
    if lst1 != []:lst.append(lst1)
    
print(len(lst))

Solution (Python):


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

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

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

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

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

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

N,M=map(int,input().split())
UN=UnionFind(N)
for _ in range(M):
    s,t,u = map(int,input().split())
    UN.Unite(s,t)
    

ans=0
for i in UN.root:
    if i<0:
        ans +=1
print(ans-1)

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

class UnionFind():
    def __init__(self, n):
        self.li = list(range(n))
    def root(self, x):
        if self.li[x]==x:
            return x
        self.li[x] = self.root(self.li[x])
        return self.li[x]
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx==ry:
            return
        self.li[ry] = rx
    def same(self, x, y):
        return self.root(x)==self.root(y)

uf = UnionFind(n)
for x, y in xy:
    uf.unite(x, y)
for i in range(n):
    uf.root(i)
print(len(set(uf.li)))

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

n,m=map(int,input().split())
a=[list(map(int,input().split())) for i in range(m)]
u=UnionFind(n)
for i in range(m):
    u.union(a[i][0]-1,a[i][1]-1)
print(u.group_count())

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

def find(x):
    if par[x]<0:
        return x
    else:
        par[x]=find(par[x])
        return 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)
    
def size(x):
    return -par[find(x)]

N,M=map(int,input().split())
par=[-1]*N
for _ in range(M):
    a,b,c=map(int,input().split())
    union(a-1,b-1)
ans=0
for i in par:
    if i<0:
        ans+=1
print(ans)

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

def find(x):
    if par[x]<0:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def union(x,y):
    p,q=find(x),find(y)
    if p==q:
        return
    if p>q:
        p,q=q,p
    par[p]+=par[q]
    par[q]=p   

for _ in range(M):
    X,Y,_=map(int,input().split())
    X,Y=X-1,Y-1
    union(X,Y)
ans=0
for i in range(N):
    if par[i]<0:
        ans+=1
print(ans)

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

import networkx as nx

G=nx.Graph()

for i in range (1, N+1):
	G.add_node(i)

for i in range (0, M):
	A, B, C = map(int, input().split())
	G.add_edge(A,B)

print(nx.number_connected_components(G))