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

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

def main():
    n,m = map(int,input().split())
    li = [list(map(int,input().split())) for _ in range(m)]

    roots = [[] for _ in range(n)]
    for x,y,z in li:
        roots[x-1].append(y-1)
        roots[y-1].append(x-1)

    ans = 0
    count = 0
    group = [-1] * n

    for i in range(n):
        if group[i] == -1:
            stack = [i]
            while stack:
                label = stack.pop(-1)
                for j in roots[label]:
                    if group[j] == -1:
                        group[j] = ans
                        stack.append(j)
            ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.N      = N
        self.depth  = [0] * N
        self.parent = list(range(N))

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

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

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

    def is_root(self, x):
        return x == self.find(x)

    def num_tree(self):
        return sum([self.is_root(i) for i in range(self.N)])


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

T = UnionFind(N)

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

print(T.num_tree())

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.depth  = [0] * n
        self.parent = list(range(n))

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

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

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

    def is_root(self, x):
        return x == self.find(x)


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

T = UnionFind(N)

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

print(sum([T.is_root(i) for i in range(N)]))

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.depth  = [0] * n
        self.parent = list(range(n))

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

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

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

    def size(self, x):
        return self.depth[self.ind(x)]


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

T = UnionFind(N)

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

print(sum([1 for i in range(N) if T.find(i) == i]))

Solution (Python):
class UnionFind:

    def __init__(self, n):
        
        self.parent, self.depth = [-1] * n, [0] * n

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

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

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

        if self.depth[x] > self.depth[y]:
            self.parent[x] += self.parent[y]
            self.parent[y] = x
        else:
            self.parent[y] += self.parent[x]
            self.parent[x] = y
            if self.depth[x] == self.depth[y]:
                self.depth[y] += 1

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

    def numTree(self):
        return sum([1 for p in self.parent if p < 0])


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

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

print(U.numTree())

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


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


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


    def groupsize(self):
        self.cnt = 0
        for i, x in enumerate(self.parent):
            if x == i:
                self.cnt += 1
        return self.cnt


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

for i in range(M):
    uf.unite(A[i][0]-1, A[i][1]-1)

print(uf.groupsize())

Solution (Python):
import sys
sys.setrecursionlimit(100000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *

class UnionFind:

    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.height = [0 for i in range(n)]
        self.size = [1 for i in range(n)]

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

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

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.height[x] < self.height[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = self.par[x]
            self.size[x] += self.size[y]
            if self.height[x] == self.height[x]:
                self.height[x] += 1

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

N, M = map(int, input().split())
xyz = [None] * M
uf = UnionFind(2*N)
for i in range(M):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    if z % 2:
        uf.unite(x, y+N)
        uf.unite(x+N, y)
    else:
        uf.unite(x, y)
        uf.unite(x+N, y+N)
roots = set()
ans = 0
for i in range(N):
    p1, p2 = uf.find(i), uf.find(i+N)
    if p1 not in roots and p2 not in roots:
        roots.add(p1)
        ans += 1
print(ans)

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

    
    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 groupsize(self):
        self.cnt = 0
        for i, x in enumerate(self.par):
            if x == i:
                self.cnt += 1
        return self.cnt
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

N, M = map(int,input().split())
A = [list(map(int,input().split())) for i in range(M)]
uf = UnionFind(N)

for i in range(M):
    uf.union(A[i][0]-1, A[i][1]-1)

print(uf.groupsize())

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

    
    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 groupsize(self):
        self.cnt = 0
        for i, x in enumerate(self.par):
            if x == i:
                self.cnt += 1
        return self.cnt
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

N, M = map(int,input().split())
A = [list(map(int,input().split())) for i in range(M)]
uf = UnionFind(N)

for i in range(M):
    uf.union(A[i][0]-1, A[i][1]-1)

print(uf.groupsize())

Solution (Python):



import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
import math

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

renketu = [dict() for i in range(N)]
for i in range(N):
	renketu[i]["iro"] = -1
	renketu[i]["eda"] = []
for i in range(M):
	renketu[XYZ[i][0] - 1]["eda"].append([XYZ[i][0], XYZ[i][1]])
	renketu[XYZ[i][1] - 1]["eda"].append([XYZ[i][1], XYZ[i][0]])

num = 0
for i in range(N):
	if renketu[i]['iro'] == -1:
		num += 1
		stack = [i]
		
		renketu[i]['iro'] = num
		while len(stack) > 0:
			node = stack.pop()
			for edge in renketu[node]["eda"]:
				if renketu[edge[1] - 1]["iro"] == -1:
					renketu[edge[1] - 1]["iro"] = num
					stack.append(edge[1] - 1)

print(num)

Solution (Python):
from collections import deque
import sys


sys.setrecursionlimit(100000)


class UnionFind:
    def __init__(self, size):
        self.parent = [-1] * (size + 1)  

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

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

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

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

N,M = list(map(int, input().split(" ")))
uf = UnionFind(N)
for _ in range(M):
    x,y,_ = list(map(int, input().split(" ")))
    uf.merge(x,y)
anss = set()
for i in range(1,N+1):
    anss.add(uf.root(i))
print(len(anss))

Solution (Python):
import sys
sys.setrecursionlimit(100000)
n,m=map(int,input().split())
class UnionFind(object):
    def __init__(self, N):
        self.parent = [i for i in range(N)]
 
    def merge(self, a, b):
        pa = self.root(a)
        pb = self.root(b)
        self.parent[pa] = pb
    
    def root(self, x):
        p = self.parent[x]
        if p == x:
            return x
        else:
            r = self.root(p)
            self.parent[x] = r
            return r
u=UnionFind(n)
for i in range(m):
  a,b,c=map(int,input().split())
  if a>b:
    a=g
    g=b
    b=a
  u.merge(a-1,b-1)
a=[0]*n
for i in range(n):
  a[i]=u.root(i)
print(len(set(a)))

Solution (Python):
import sys;sys.setrecursionlimit(10**9)
class u():
  def __init__(self,n):self.n,self.r=[-1]*n,[0]*n
  def f(self,x):
    if self.n[x]<0:return x
    else:self.n[x]=self.f(self.n[x]);return self.n[x]
  def u(self,x,y):
    x,y=self.f(x),self.f(y)
    if x==y:return
    elif self.r[x]>self.r[y]:self.n[x]+=self.n[y];self.n[y]=x
    else:self.n[y]+=self.n[x];self.n[x]=y;self.r[y]+=self.r[x]==self.r[y]
  def s(self,x,y):return self.f(x)==self.f(y)
  def c(self,x):return -self.n[self.f(x)]
n,m=map(int,input().split());u=u(n)
for i in range(m):
  a,b,c=map(int,input().split());a-=1;b-=1
  if not(u.s(a,b)):n-=1;u.u(a,b)
print(n)

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

    def find(self, x):
        """xの属する根を求める"""
        if self.par[x] == x:  
            return x
        else:
            self.par[x] = self.find(self.par[x])  
            return self.par[x]

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

    
    
    


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

parent = [-1] * N
unionfind = UnionFind(N)
for i in range(M):
    xi, yi, zi = map(int, input().split())
    xi -= 1
    yi -= 1
    unionfind.unite(xi, yi)
    parent[yi] = xi



ans_set = set()
for i in range(N):
    ans_set.add(unionfind.find(i))
ans = len(ans_set)


print(ans)

Solution (Python):
def uf_init(n):
    return list(range(n))

def uf_root(uf, x):
    update_node_arr = []
    while(uf[x] != x):
        update_node_arr.append(x)
        x = uf[x]
    for y in update_node_arr:
        uf[y] = x
    return x

def uf_same(uf, x, y):
    return uf_root(uf, x) == uf_root(uf, y)

def uf_unite(uf, x, y):
    x = uf_root(uf, x)
    y = uf_root(uf, y)
    if x == y:
        return
    uf[x] = y

N,M = (int(x) for x in input().split())

uf = uf_init(N)

for _ in range(M):
    X,Y,Z = (int(x) for x in input().split())
    uf_unite(uf, X-1, Y-1)

uf_roots = set()
for i in range(N):
    uf_roots.add(uf_root(uf, i))

print(len(uf_roots))

Solution (Python):
def init(n):
    for i in range(N):
        par[i] = i
        rnk[i] = 0

def find(x):
    if par[x] == x:
        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
    if (rnk[x] < rnk[y]):
        par[x] = y
    else:
        par[y] = x
        if(rnk[x] == rnk[y]):
            rnk[x] += 1
            
N, M = map(int, input().split())

X = [0 for i in range(M)]
Y = [0 for i in range(M)]
Z = [0 for i in range(M)]

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

par = [0 for i in range(N)]
rnk = [0 for i in range(N)]
init(N)

for i in range(M):
    unite(X[i], Y[i])
    
for i in range(N):
  find(i)

print(len(set(par)))

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

def root(x):
  temp = x
  while temp != XY[temp]:
    temp = XY[temp]
  XY[x] = temp
  return temp
for _ in range(M):
  x, y = map(int, input().split()[:2])
  XY[root(x)] = root(y)

print(sum(i == v for i, v in enumerate(XY)) - 1)

Solution (Python):
import sys
input = sys.stdin.readline
n, k = [ int(v) for v in input().split() ]
card_parent = [ i for i in range(n) ]
card_set = [ set([i]) for i in range(n) ]
card_list = set( tuple( int(v)-1 for v in input().split() ) for i in range(k) )

def parent(x,a):
    if card_parent[x] == x:
        return x, a
    else:
        return parent(card_parent[x],a+1)


for i in card_list:
    p, q = i[0], i[1]
    card_parent[p], rank_p = parent(p,0)
    card_parent[q], rank_q = parent(q,0)
    if card_parent[p] != card_parent[q]:
        if rank_p > rank_q:
            card_parent[card_parent[q]] = card_parent[p]
        else:
            card_parent[card_parent[p]] = card_parent[q]




card_parent = [ parent(i,0)[0] for i in range(n) ]

print(len(set(card_parent)))

Solution (Python):

import sys
input = sys.stdin.readline
n, k = [ int(v) for v in input().split() ]
card_parent = [ i for i in range(n) ]
card_set = [ set([i]) for i in range(n) ]
card_list = [ tuple( int(v)-1 for v in input().split() ) for i in range(k) ]

def parent(x,a):
    if card_parent[x] == x:
        return x, a
    else:
        return parent(card_parent[x],a+1)


for i in card_list:
    p, q = i[0], i[1]
    card_parent[p], rank_p = parent(p,0)
    card_parent[q], rank_q = parent(q,0)
    if card_parent[p] != card_parent[q]:
        if rank_p > rank_q:
            card_parent[card_parent[q]] = card_parent[p]
        else:
            card_parent[card_parent[p]] = card_parent[q]




card_parent = [ parent(i,0)[0] for i in range(n) ]

print(len(set(card_parent)))

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
N, M = map(int, input().split())
X = [0] * M
Y = [0] * M
Z = [0] * M 
for i in range(M):
  X[i], Y[i], Z[i] = map(int, input().split())

reach = [[] for _ in range(N)]

for i in range(M) :
    reach[Y[i]-1].append(X[i])
    reach[X[i]-1].append(Y[i])

approach = [False for _ in range(N)]

def change(reach, s):       
    approach[s-1] = True
    for i in reach[s-1]:
        if not approach[i-1] :
            change(reach, i)

ans = 0
for i in range(N) :
    if not approach[i]:
        change(reach, i+1)
        ans += 1

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
N,M = list(map(int,input().split()))
XYZ = [list(map(int,input().split())) for _ in range(M)]

G = [[] for _ in range(N)]
 
for i in XYZ:
    G[i[0]-1].append(i[1])
    G[i[1]-1].append(i[0])
 
check = [False for _ in range(N)]
 
def DFS(G,s):
    check[s-1] = True
    for i in G[s-1]:
        if not check[i-1]:         
            DFS(G,i)
ans = 0
for i in range(N):
    if not check[i]:
        DFS(G,i+1)
        ans += 1

print(ans)

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

class UnionFind:
    def __init__(self, n):
        self.par = list(range(n))
        self.rank = [0] * 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
    
    def get_par(self):
        return self.par

t = UnionFind(N)
for u, v, _ in edges:
    t.unite(u - 1, v - 1)

print(len(set(t.find(x) for x in range(N))))

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

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

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

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

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

    def is_root(self, x):
        return self.parent[x] < 0


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

uf = UnionFind(n)

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

print(sum(uf.is_root(i) for i in range(n)))

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.sz[x] > self.sz[y]:
            x,y = y,x
        self.sz[x] += self.sz[y]
        self.sz[y] = x

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

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

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

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

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
class Node:
    def __init__(self):
        self.next=[]
    def get_data(self,new_next,weight=1):
        self.next.append({new_next:weight})


def BFS():
    total=0
    check_node=tmp_node
    
    now=min(check_node)
    tmp=[now]
    check_node.remove(now)
    ans=N-len(check_node)
    new_tmp=[]
    while len(check_node)>0:
        
        if tmp==[]:
            ans+=1
            tmp.append(check_node[0])
            check_node.remove(check_node[0])
        total+=1
        for each in tmp:
            
            for i in node[each].next:
                k=list(i.keys())[0]
                if k in check_node:
                    
                    new_tmp.append(k)
                    check_node.remove(k)
        
        
        tmp=new_tmp
        new_tmp=[]
    
    
    
    print(ans)


def rec_BFS(i):
    tmp=[list(j.keys())[0] for j in i]
    for each in tmp:
        if not check_node[each]:
            check_node[each]=True
            rec_BFS(node[each].next)






        
        

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

tmp_node=[]
for i in range(M):
    tmp_p,tmp_n,tmp_w=list(map(int,input().split()))
    
    
    
    
    node[tmp_p-1].get_data(tmp_n-1)
    node[tmp_n-1].get_data(tmp_p-1)

s=0
check_node=[False for _ in range(N)]
for i in range(N):
    if not check_node[i]:
        check_node[i]=True
        s+=1
        rec_BFS(node[i].next)
print(s)

Solution (Python):

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)


def lcm(x, y):
    return (x * y) // gcd(x, y)


def isPrime():
    MAX = 10**5
    is_prime = [1] * (MAX+1)
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, MAX+1):
        if is_prime[i]:
            for j in range(i*2, MAX+1, i):
                is_prime[j] = 0
    return is_prime


def makeDivisor(n):
    divisors = []
    for i in range(1, int(n ** 0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors


def makePrime(n):
    factor = []
    tmp = int(n ** 0.5) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            factor.append(num)

    if n > 1:
        factor.append(n)

    return factor


def modPow(a, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        halfP = p // 2
        half = modPow(a, halfP)
        return half * half % mod
    else:
        return a * modPow(a, p-1) % mod


def comb(a, b):
    if b > a - b:
        return comb(a, a-b)
    ansMul = 1
    ansDiv = 1
    for i in range(b):
        ansMul *= a - i
        ansDiv *= i + 1
        ansMul %= mod
        ansDiv %= mod

    ans = ansMul * modPow(ansDiv, mod-2) % mod
    return ans


class UnionFind():

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

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

    def Unite(self, x, y):
        x = self.FindRoot(x)
        y = self.FindRoot(y)

        if x == y:
            return False
        if self.Size(x) < self.Size(y):
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x

        return True

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

    def Size(self, x):
        return -self.root[self.FindRoot(x)]

N, M = map(int, input().split())
X = [0] * M
Y = [0] * M
Z = [0] * M
for i in range(M):
    X[i], Y[i], Z[i] = map(int, input().split())

Uni = UnionFind(N)

for i in range(M):
    Uni.Unite(X[i], Y[i])

roots = set()
for i in range(1, N+1):
    roots.add(Uni.FindRoot(i))

print(len(roots))

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

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


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

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

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

print(ans - 1)

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


class UnionFindNode(object):
    """
    Union-Find構造
    ノードのグループ併合や、所属グループ判定を高速に処理する
    """

    def __init__(self, group_id, parent=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.size_ = 1
        self.rank_ = 1

    def __str__(self):
        template = "UnionFindNode(group_id: {}, \n\tparent: {}, size: {}, rank: {})"
        return template.format(self.group_id_, self.parent_, self.size_,
                               self.rank_)

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        root = self.root()
        return root.group_id_

    def rank(self):
        root = self.root()
        return root.rank_

    def get_size(self):
        root = self.root()
        return root.size_

    def unite(self, unite_node):
        root = self.root()
        unite_root = unite_node.root()

        if root.group_id_ != unite_root.group_id_:
            if root.rank() > unite_root.rank():
                unite_root.parent_ = root
                root.rank_ = max(root.rank_, unite_root.rank_ + 1)
                root.size_ += unite_root.size_

            else:
                root.parent_ = unite_root
                unite_root.rank_ = max(root.rank_ + 1, unite_root.rank_)
                unite_root.size_ += root.size_


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

node_array = [UnionFindNode(i) for i in range(N)]

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

parent = set()

for node in node_array:
    parent.add(node.find())

print(len(parent))

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

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


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



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

if __name__ == '__main__':
	N, M = map(int, input().split())
	uf = UnionFind(N)
	for i in range(M):
		X, Y, Z = map(int, input().split())
		uf.merge(X-1, Y-1)
	
	ans = [ uf.root(i) for i in range(N)]

	print(len(set(ans)))

Solution (Python):
import sys


sys.setrecursionlimit(10**5)


class UnionFind(object):
    def __init__(self, N):
        self.parent = [i for i in range(N)]

    def merge(self, a, b):
        pa = self.root(a)
        pb = self.root(b)
        self.parent[pa] = pb
    
    def root(self, x):
        p = self.parent[x]
        if p == x:
            return x
        else:
            r = self.root(p)
            self.parent[x] = r
            return r


def main():
    N, M = map(int, input().split())

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

    print(len(list(filter(lambda x: x == uf.root(x), range(N)))))


main()

Solution (Python):
N,M=map(int,input().split())
edge=[list(map(int,input().split())) for i in range(M)]
c=[[] for i in range(N)]
for i,j,w in edge:
    c[i-1].append(j-1)
    c[j-1].append(i-1)
a=0
v=[0]*N
import sys
sys.setrecursionlimit(10**6)
def dfs(c,v,p):
    v[p]=1
    for n in c[p]:
        if v[n]==0:
            dfs(c,v,n)
for i in range(N):
    if v[i]==1:
        continue
    dfs(c,v,i)
    a+=1
print(a)

Solution (Python):
class uf_tree():

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

    def indep(self):
        dep =0
        for i in range(self.n):
            if i == self.par[i]:
                dep += 1

        return dep

    def unite(self,child,mas):
        if self.root(child) == self.root(mas):
            return
        else:
            self.par[self.root(child)] = self.root(mas)

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

    def same(self,x,y):
        if self.root(x) == self.root(y):
            return True
        else:
            return False



n,m = map(int,input().split())
uf = uf_tree(n+1)
for i in range(m):
    x,y,z = map(int,input().split())
    uf.unite(x,y)

print(uf.indep()-1)