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 bisect
import sys
input = sys.stdin.readline
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 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)]
for i in range(m):
  x,y,z=map(int,input().split())
  unite(x-1,y-1)
par.sort()
print(bisect.bisect_left(par,0))

Solution (Python):
import collections
import sys
sys.setrecursionlimit(100000)
def root(X):
	if cards[X]==X:
		return X
	else:
		cards[X]=root(cards[X])
		return cards[X]
def unite(X,Y):
	x=root(X)
	y=root(Y)
	if x==y:
		return
	else:
		cards[x]=y
def same(X,Y):
	return root(X)==root(Y)
def show(x):
	print(cards[x])
		
N,M=[int(i) for i in input().split()]
cards=[i for i in range(N+1)]
for i in range(M):
	X,Y,Z=[int(i) for i in input().split()]
	if same(X,Y):
		pass
	else:
		unite(X,Y)
a=[]
for i in range(1,N+1):
	a.append(root(cards[i]))
print(len(set(a)))

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

n, m = map(int, input().split())
t = [[] for i in range(n)]
c = [-1 for i in range(n)]
for line in sys.stdin:
    x, y ,z = map(int, line.split())
    x -= 1
    y -= 1
    t[x].append(y)
    t[y].append(x)


def dfs(num, depth):
    if c[num] != -1:
        return
    else:
        c[num] = depth
    for i in t[num]:
        dfs(i, depth)


cnt = 0
for i in range(n):
    if c[i] == -1:
        cnt += 1
        dfs(i, cnt)

print(cnt)

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

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


    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.sizes[y] += self.sizes[x]
        else:
            self.parent[y] = x
            self.sizes[x] += self.sizes[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 size(self, x):
        return self.sizes[self.find(x)]

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

u = UnionFind(N)

for m in range(M):
    xyz = [int(i)-1 for i in input().split()]
    u.unite(xyz[0],xyz[1])

for n in range(N):
    u.root(n)

print(len(list(set(u.parent))))

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

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


    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.sizes[y] += self.sizes[x]
        else:
            self.parent[y] = x
            self.sizes[x] += self.sizes[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 size(self, x):
        return self.sizes[self.find(x)]

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

u = UnionFind(N)

for m in range(M):
    xyz = [int(i)-1 for i in input().split()]
    u.unite(xyz[0],xyz[1])

for n in range(N):
    u.root(n)

print(len(list(set(u.parent))))

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n)
        self.total = 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 same_check(self, x, y):
        return self.find(x) == self.find(y)
    def unite(self, x, y):
        if self.same_check(x, y):
            return
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.total -= 1
        else:
            self.par[y] = x
            self.total -= 1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
n,m = map(int, input().split())
union = UnionFind(n)
for i in range(m):
    x,y,z = map(int, input().split())
    union.unite(x-1, y-1)
print(union.total)

Solution (Python):
def c_show(graph,x):
    seen = set()
    nodes = set([x])
    while nodes:
        cur = nodes.pop()
        seen.add(cur)
        nodes |= set(graph[cur]) - seen
    return seen

def c_cnt(graph,n): 
    done = set()
    cnt = 0
    for x in range(n):
        if x not in done:
            done |= c_show(graph,x)
            cnt += 1
    return cnt
  
n,m = map(int, input().split())
g = [list() for _ in range(n)]
for _ in range(m):
    x,y,z = map(int, input().split())
    g[x-1].append(y-1)
    g[y-1].append(x-1)
print(c_cnt(g,n))

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

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


def dfs(num, depth):
    if c[num] != -1:
        return
    else:
        c[num] = depth
    for i in t[num]:
        dfs(i, depth)


cnt = 0
for i in range(n):
    if c[i] == -1:
        cnt += 1
        dfs(i, cnt)

print(max(c))

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

par = [i for i in range(n+1)]
rank = [0] * (n+1)

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

def unite(x,y):
  root_x = find(x)
  root_y = find(y)
  if rank[root_x] != rank[root_y]:
    par[min(root_x,root_y)] = max(root_x,root_y)
  else:
    par[root_y] = root_x
    rank[root_x] += 1


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

for i in range(n):
  roo.append(find(i+1))

print(len(set(roo))-1)

Solution (Python):
from collections import deque

def solve():
    N, M = [int(_) for _ in raw_input().split()]
    to = [ [] for i in range(N) ]
    for i in range(M):
        Xi, Yi, Zi = [int(_) for _ in raw_input().split()]
        Xi -= 1
        Yi -= 1
        to[Xi].append(Yi)
        to[Yi].append(Xi)
    union = [None] * N
    que = deque()
    union_cnt = 0
    for i in range(N):
        if union[i] is not None:
            continue
        union_cnt += 1
        
        que.append(i)
        while len(que) > 0:
            vi = que.popleft()
            union[vi] = union_cnt
            for j in range(len(to[vi])):
                fri = to[vi][j]
                if union[fri] is not None:
                    continue
                union[fri] = union_cnt
                que.append(fri)
    print str(union_cnt)

if __name__ == '__main__':
    solve()

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


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


def uni(x,y):
    rx = root(x)
    ry = root(y)
    c[ry] = rx


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

for i in range(n):
    root(i)

print(len(set(c)))

Solution (Python):
class UnionFind():
    def __init__(self, N):
        
        self.table = [-1] * (N+1)      
        self.sizetable = [1] * (N+1) 
    def root(self, x): 
        while self.table[x] >= 0: 
            x = self.table[x]
        return x
    def unite(self, x, y): 
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry: 
            
            if self.sizetable[rx] < self.sizetable[ry]:
                rx, ry = ry, rx
            self.sizetable[rx] += self.sizetable[ry] 
            self.sizetable[ry] = 0 
            self.table[ry] = rx      
        return
    def same(self, x, y): 
        return self.root(x) == self.root(y)
    def size(self, x): 
        return self.sizetable[self.root(x)]
    

N, M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
    ui, vi, wi = map(int, input().split())
    uf.unite(ui, vi)
print(sum([t > 0 for t in uf.sizetable[1:]]))

Solution (Python):
class UnionFind():
    def __init__(self,size):
        self.table=[-1]*size
    def root(self,x):
        while self.table[x]>=0:
            x=self.table[x]
        return x
    def unite(self,x,y):
        s1=self.root(x)
        s2=self.root(y)
        if s1!=s2:
            if self.table[s1]>self.table[s2]:
                s1,s2=s2,s1
            self.table[s1]+=self.table[s2]
            self.table[s2]=s1
        return
    def same(self,x,y):
        return self.root(x)==self.root(y)
    def size(self,x):
        return -self.table[self.root(x)]
    

N, M = map(int, input().split())
uf = UnionFind(N+1)
for i in range(M):
    ui, vi, wi = map(int, input().split())
    uf.unite(ui, vi)
print(sum([t < 0 for t in uf.table[1:]]))

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

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

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

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

    def ans(self):
        print(len(set(self.par))-1)

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

for i in range(m):
    a,b,c=map(int,input().split())
    uf.union(a,b)

for i in range(1,n+1):
    uf.find(i)
uf.ans()

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

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

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

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

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

tree = UnionFindTree(N)

for i in range(1, M+1):
    x, y, w = map(int, input().split())
    tree.union(x, y)

root_list = []

for i in range(1, N+1):
    root_list.append(tree.find(i))

root_list = list(set(root_list))

print(len(root_list))

Solution (Python):
class DisjointSet:
    def __init__(self):
        self.rank = {}
        self.p = {}

    def makeSet(self, x):
        self.p[x] = x
        self.rank[x] = 0

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

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if x == y:
            return
        if(self.rank[x] > self.rank[y]):
            self.p[y] = x
        else:
            self.p[x] = y
            if(self.rank[x] == self.rank[y]):
                self.rank[y] += 1

    def findSet(self, x):
        if(x != self.p[x]):
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]



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

ds = DisjointSet()
for i in range(N):
    ds.makeSet(i+1)

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

ans = set()

for i in range(1, N+1):
    a = ds.findSet(i)
    ans.add(a)

print(len(ans))

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_root(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find_root(self.par[x])
        return self.par[x]
    
    def union(self, x, y):
        x_root = self.find_root(x)
        y_root = self.find_root(y)
        if x_root != y_root:
            if self.rank[x_root] < self.rank[y_root]:
                x_root, y_root = y_root, x_root
            if self.rank[x_root] == self.rank[y_root]:
                self.rank[x_root] += 1
            self.par[y_root] = x_root
            
    def is_same(self, x, y):
        x_root = self.find_root(x)
        y_root = self.find_root(y)
        return x_root == y_root
    def num(self):
        c=set()
        for i in range(len(u.par)):
            c.add(self.find_root(i))
        return len(c)
    
n,m=map(int,input().split())
xyz=[list(map(int,input().split())) for _ in range(m)]
xy=[[x-1,y-1] for x,y,z in xyz]
u=UnionFind(n)
for x,y in xy:
    u.union(x,y)
print(u.num())

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_root(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find_root(self.par[x])
        return self.par[x]
    
    def union(self, x, y):
        x_root = self.find_root(x)
        y_root = self.find_root(y)
        if x_root != y_root:
            if self.rank[x_root] < self.rank[y_root]:
                x_root, y_root = y_root, x_root
            if self.rank[x_root] == self.rank[y_root]:
                self.rank[x_root] += 1
            self.par[y_root] = x_root
            
    def is_same(self, x, y):
        x_root = self.find_root(x)
        y_root = self.find_root(y)
        return x_root == y_root
    
n,m=map(int,input().split())
xyz=[list(map(int,input().split())) for _ in range(m)]
xy=[[x-1,y-1] for x,y,z in xyz]
u=UnionFind(n)
for x,y in xy:
    u.union(x,y)
res=[]
for i in range(n):
    res.append(u.find_root(i))
print(len(set(res)))

Solution (Python):

"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""


"""
Created on Sat Apr 13 09:53:12 2019

@author: Owner
"""
import numpy as np
import sys
import collections
import scipy.misc
import math
from operator import itemgetter
import itertools
import copy
import bisect


def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   

def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


"""
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())


dp = np.zeros((N+1, 4,4,4))
    
all(nstr.count(c) for c in '753')


ABT = zip(A, B, totAB)
result = 0

sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)


(x >> i) & 1


dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break

add = 1 
res = 0
sums = [0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
for i in range(0, len(nums), 2):
    left = i
    right = min(i+add, len(nums))
    tmp = sums[right] - sums[left]
    res = max(tmp, res)


li, ri = bisect.bisect_left(p_ac, l[i]-1), bisect.bisect_right(p_ac, r[i]-1)    


org_list = [3, 1, 4, 5, 2]
new_list = sorted(org_list)
print(org_list)
print(new_list)




    for h in range(0,H):
        for w in range(0,W):
            if h == 0 and w == 0:
                pass
            elif h == 0:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h-1][W-w]+1)
            elif w == 0:   
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1)
            else:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1, D[H-h-1][W-w]+1, D[H-h][W-w]+2)
            d_max = max(D[H-h-1][W-w-1], d_max)

"""

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

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

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

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]
    
N, M = list(map(int, input().split()))
X = [0]*M
Y = [0]*M
Z = [0]*M

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


def main(): 
    uf = UnionFind(N)
    for m in range(M):
        uf.union(X[m]-1, Y[m]-1)
    num = set()
    for n in range(N):
        num.add(uf.find(n))        
        
    print(len(num))
                
                
if __name__ == '__main__':
    main()

Solution (Python):
import sys


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

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

    def unite(self, x, y):
        if self.is_same(x, y):
            return
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.root[rx] = ry
        else:
            self.root[ry] = rx
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

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

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    uft = UnionFind(N)
    for _ in range(M):
        x, y, _ = map(int, input().split())
        uft.unite(x-1, y-1)

    root = set()
    for i in range(N):
        root.add(uft.find(i))

    return len(root)


if __name__ == '__main__':
    print(main())

Solution (Python):
n, m = map(int, input().split())
parent = [i for i in range(n + 1)]
rank = [0] * (n + 1)
s = set()

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

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

for i in range(m):
    x, y, z = map(int, input().split())
    union(x, y)
for i in range(1, n + 1):
    s.add(find(i))
print(len(s))

Solution (Python):
n,m = (int(i) for i in input().split())
par,rank,q = [i for i in range(n+1)],[0 for i in range(n+1)],set()
def root(x):
	if par[x]!=x: par[x] = root(par[x])
	return par[x]
def unite(x,y):
	x2,y2 = root(x),root(y)
	if x2!=y2:
		if rank[x2]<rank[y2]: par[x2] = y2
		else: par[y2] = x2
		if rank[x2]==rank[y2]: rank[x2]+=1
for i in range(m):
    x,y,z = (int(i) for i in input().split())
    unite(x,y)
for i in range(1,n+1): q.add(root(i))
print(len(q))

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

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

def root(x):
	while parent[x] >= 0:
		x = parent[x]
	return x

def unite(x,y):
	root_x = root(x)
	root_y = root(y)

	if root_x != root_y :
		if parent[root_x] > parent[root_y] :
			parent[root_x]=root_y
		else :
			if parent[root_x] == parent[root_y] :
				parent[root_x] -= 1
			parent[root_y] = root_x
    
	return

for _ in range(M) :
	X, Y, Z = map(int, input().split())
	unite(X, Y)
	
print(sum(i < 0 for i in parent) - 1)

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_root(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find_root(self.par[x])
        return self.par[x]
    
    def union(self, x, y):
        x_root = self.find_root(x)
        y_root = self.find_root(y)
        if x_root != y_root:
            if self.rank[x_root] < self.rank[y_root]:
                x_root, y_root = y_root, x_root
            if self.rank[x_root] == self.rank[y_root]:
                self.rank[x_root] += 1
            self.par[y_root] = x_root
            
    def is_same(self, x, y):
        x_root = self.find_root(x)
        y_root = self.find_root(y)
        return x_root == y_root
        
N, M = map(int, input().split())
X = [ list(map(int, input().split())) for _ in range(M)]

uf = UnionFind(N)
for x in X:
    uf.union(x[0]-1, x[1]-1)
    
roots = [ uf.find_root(i) for i in range(N)]
print(len(set(roots)))

Solution (Python):
class Node:
    def __init__(self, val):
        self.num = val
        self.val = val
        self.is_parent = True
        self.parent = None
        self.childs = []

    def show(self):
        print(self.num, end=" ")
        print(self.is_parent, end=" ")
        for child in self.childs:
            print(child.num, end=" ")

def root(node):
    depth = 0
    while node.parent != None:
        node = node.parent
        depth += 1
    return node, depth

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

roots = [Node(i) for i in range(N)]
count = N

for i in range(M):
    x, y, z = map(int, input().split())
    x = roots[x-1]
    y = roots[y-1]
    if x.is_parent and y.is_parent:
            y.is_parent = False
            y.parent = x
            count -= 1
            x.childs.append(y)
    else:
        root_x, depth_x = root(x)
        root_y, depth_y = root(y)
        if root_x != root_y:
            if depth_x >= depth_y:
                root_y.is_parent = False
                root_y.parent = root_x
                count -= 1
                root_x.childs.append(root_y)
            else:
                root_x.is_parent = False
                root_x.parent = root_y
                count -= 1
                root_y.childs.append(root_x)

print(count)

Solution (Python):
import collections

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

checked=[False]*n
way=[[] for i in range(n)]
for i in range(m):
  x,y,z=list(map(int,input().split()))
  x-=1
  y-=1
  way[x].append(y)
  way[y].append(x)
ans=0

for i in range(n):
  if checked[i]==False:
    
    q=collections.deque()
    q.append(i)
    while len(q)>0:
      c=q.popleft()
      for i in way[c]:
        if not checked[i]:
          checked[i]=True
          q.append(i)
    ans+=1
print(ans)

Solution (Python):
n, m = [int(item) for item in input().split()]
xyz = [[int(item) for item in input().split()] for _ in range(m)]

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

UF = UnionFind(n)
for x, y, z in xyz:
    x -= 1
    y -= 1
    if not UF.same_check(x, y):
        UF.union(x, y)

s = set() 
for i in range(n):
    s.add(UF.find(i))
    
print(len(s))

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

class UniteFind:
    def __init__(self, N):
        self.par = [i for i in range(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 unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return
        self.par[ry] = rx

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


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

for _ in range(M):
    x, y, _ = map(int, input().split())
    rf.unite(x-1, y-1)

m = {i: -1 for i in range(N)}
ans = 0

for i in range(N):
    if m[rf.root(i)] == -1:
        m[rf.root(i)] = 1
        ans += 1

print(ans)

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

p = list(range(n))


def find(x):
    if p[x] != x:
        p[x] = find(p[x])
    return p[x]


def union(x, y):
    x, y = find(x), find(y)
    p[x] = p[y] = min(x, y)


for _ in range(m):
    x, y, z = [int(i) - 1 for i in input().split()]
    if find(x) != find(y):
        union(x, y)

ans = set()
for i in range(n):
    find(i)
print(len(set(p)))

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

p = list(range(n))


def find(x):
    if p[x] != x:
        p[x] = find(p[x])
    return p[x]


def union(x, y):
    x, y = find(x), find(y)
    p[x] = p[y] = min(x, y)


for _ in range(m):
    x, y, z = [int(i) - 1 for i in input().split()]
    if find(x) != find(y):
        union(x, y)

ans = set()
for i in range(n):
    find(i)
print(len(set(p)))

Solution (Python):
n,m = map(int,input().split())
graph = [[] for i in range(n)]
for i in range(m):
    x,y,z = map(int,input().split())
    graph[x-1].append(y-1)
    graph[y-1].append(x-1)
check = [True]*n
count = 0
for i in range(n):
    if check[i]:
        count += 1
        stack = []
        stack.append(i)
        check[i] = False
        while stack:
            p = stack.pop()
            for j in graph[p]:
                if check[j]:
                    stack.append(j)
                    check[j] = False
    else:
        continue

print(count)

Solution (Python):
from scipy.sparse import*
n,m,*t=map(int,open(0).read().split())
print(csgraph.connected_components(csr_matrix(([1]*m,(t[::3],t[1::3])),[n+1]*2))[0]-1)

Solution (Python):
from scipy.sparse import*;n,m,*t=map(int,open(0).read().split());print(csgraph.connected_components(csr_matrix(([1]*m,(t[::3],t[1::3])),[n+1]*2))[0]-1)

Solution (Python):
from scipy.sparse import*;n,m,*t=map(int,open(0).read().split());t=[i-1for i in t];print(csgraph.connected_components(csr_matrix(([1]*m,(t[::3],t[1::3])),[n]*2))[0])

Solution (Python):
class UnionFindTree:
    _node_num = 0
    _parent_list = []
    _tree_len = []
    _num_trees = 0

    def __init__(self, node_num):
        self._node_num = node_num
        self._parent_list = [-1 for i in range(node_num+1)]
        self._tree_len = [0 for i in range(node_num+1)]
        self._num_trees = node_num

    def _root(self, node):
        root = node
        while self._parent_list[root] != -1:
            root = self._parent_list[root]
        return root

    def union(self, x, y):
        xr = self._root(x)
        yr = self._root(y)
        if xr == yr:
            return
        if self._tree_len[xr] < self._tree_len[yr]:
            self._parent_list[xr] = yr
            self._tree_len[yr] += 1
        else:
            self._parent_list[yr] = xr
            self._tree_len[xr] += 1
        self._num_trees -= 1

    def get_num_trees(self):
        return self._num_trees

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

    uft = UnionFindTree(N)
    for i in range(M):
        x, y, z = map(int, input().split())
        uft.union(x, y)
    print(uft.get_num_trees())

if __name__ == '__main__':
    main()

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

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

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

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

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

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


N, M = map(int, input().split())
uf = UnionFind(N)
for _ in range(M):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    uf.unite(x, y)
print(sum(1 for i in range(N) if uf.root(i)))