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

sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None





class UnionFind():
    '''
    UnionFind木

    Parameters
    --------
        n (int): UnionFind木のサイズ

    Methods
    --------
        unite(x: int, y: int) -> None
            ノード x とノード y を結合する
        same(x: int, y: int) -> bool
            ノード x とノード y が同じ集合に属するか判定する
        size(x: int) -> int
            ノード x を含む集合の要素数を返す

    '''

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

    def unite(self, x: int, y: int) -> bool:
        '''x と y を結合'''
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False  
        elif self._data[x] > self._data[y]:
            x, y = y, x  
        self._data[x] += self._data[y]
        self._data[y] = x
        return True

    def root(self, x: int) -> int:
        '''ノード x の親を返す'''
        while self._data[x] >= 0:
            x = self._data[x]
        return x

    def same(self, x: int, y: int) -> bool:
        '''x と y が同じグループに属するか判定'''
        return self.root(x) == self.root(y)

    def size(self, x: int) -> int:
        '''x を含むグループのノード数を返す'''
        return self._data[self.root(x)]




class QuickFind():
    def __init__(self, n):
        self.i2g = [i for i in range(n)]  
        self.g2i = [[i]for i in range(n)]  

    def unite(self, ia, ib):
        '''アイテム ia の所属するグループとアイテム ib の所属するグループを 1 つにする'''
        
        if self.same(ia, ib):
            return
        
        if len(self.g2i[self.i2g[ia]]) < len(self.g2i[self.i2g[ib]]):
            ia, ib = ib, ia
        ga, gb = self.i2g[ia], self.i2g[ib]
        
        for j in self.g2i[gb]:
            self.i2g[j] = ga
        self.g2i[ga].extend(self.g2i[gb])
        self.g2i[gb] = []


    def same(self, ia, ib):
        '''アイテム ia とアイテム ib は同じグループに所属しているか？'''
        return self.i2g[ia] == self.i2g[ib]

    def size(self, x: int) -> int:
        '''アイテム x の属する集合のサイズを返す'''
        return len(self.g2i[self.i2g[x]])

    def group(self, x: int) -> list:
        '''アイテム x の属する集合を返す'''
        return self.g2i[self.i2g[x]]

    def __str__(self):
        '''デバッグ用出力'''
        return str([self.g2i[i] for i in range(len(self.g2i))if len(self.g2i[i]) != 0])


def benchmark():
    import random
    N = 10**6
    uf = UnionFind(N)
    a = [(random.randint(0, 1), random.randint(0, N - 1), random.randint(0, N - 1)) for i in range(N)]
    for t, x, y in a:
        if t == 0:
            uf.unite(x, y)
        else:
            uf.same(x, y)



def AOJ_DSL_1_A():
    """http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A&lang=jp"""
    n, q = mi()
    uf = UnionFind(n)
    for _ in range(q):
        t, x, y = mi()
        if t == 0:
            uf.unite(x, y)
        else:
            if uf.same(x, y):
                print(1)
            else:
                print(0)



def ABC120_D():
    """https://atcoder.jp/contests/abc120/submissions/6094323"""
    n, m = mi()
    a = [0] * m
    b = [0] * m
    for i in range(m):
        a[i], b[i] = mi()

    uf = UnionFind(n)
    ans = [0] * (m + 1)
    ans[m] = n * (n - 1) // 2

    for i in range(m - 1, -1, -1):
        a[i] -= 1
        b[i] -= 1
        ans[i] = ans[i + 1]
        if uf.same(a[i], b[i]):
            continue

        x = uf.size(a[i])
        y = uf.size(b[i])
        ans[i] -= x * y

        uf.unite(a[i], b[i])

    for i in range(1, m + 1):
        print(ans[i])





def ABC126_E():
    """https://atcoder.jp/contests/abc126/submissions/6094497"""
    N, M = mi()
    uf = UnionFind(N)
    for i in range(M):
        _X, _Y, _Z = mi()
        uf.unite(_X - 1, _Y - 1)
    ans = 0
    for i in range(N):
        if uf.root(i) == i:
            ans += 1
    print(ans)




def ABC131_F():
    """https://atcoder.jp/contests/abc131/submissions/6094709"""
    from collections import defaultdict
    MAX = 100010
    uf = UnionFind(2 * MAX)
    N = ii()
    for i in range(N):
        x, y = mi()
        uf.unite(x, y + MAX)

    mx = defaultdict(int)
    for i in range(MAX):
        mx[uf.root(i)] += 1
    my = defaultdict(int)
    for i in range(MAX, 2 * MAX):
        my[uf.root(i)] += 1
    ans = 0
    for i in range(2 * MAX):
        ans += mx[i] * my[i]
    print(ans - N)



def ATC001B():
    N, Q = mi()
    ANS = ["No", "Yes"]
    uf = QuickFind(N)
    for _ in range(Q):
        P, A, B = mi()
        if P == 0:
            uf.unite(A, B)
        elif P == 1:
            print(uf.group(A))
            print(ANS[uf.same(A, B)])

if __name__ == '__main__':
    
    
    ABC126_E()

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

n,m,*l=map(int,open(0).read().split())
graph=[[]*n for _ in range(n)]
unvis={i:True for i in range(n)}

def dfs(x):
	for y in graph[x]:
		if unvis[y]:
			unvis[y]=False
			dfs(y)
			
for i,j in zip(l[::3],l[1::3]):
	graph[i-1].append(j-1)
	graph[j-1].append(i-1)

ans=0
for x in range(n):
	if unvis[x]:
		unvis[x]=False
		dfs(x)
		ans+=1
print(ans)

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

n,m,*l=map(int,open(0).read().split())
graph=[[]*n for _ in range(n)]
unvis=[True]*n

def dfs(x):
	for y in graph[x]:
		if unvis[y]:
			unvis[y]=False
			dfs(y)
			
for i,j in zip(l[::3],l[1::3]):
	graph[i-1].append(j-1)
	graph[j-1].append(i-1)

ans=0
for x in range(n):
	if unvis[x]:
		unvis[x]=False
		dfs(x)
		ans+=1
print(ans)

Solution (Python):
from functools import lru_cache
import sys
sys.setrecursionlimit(10**7)

n,m,*l=map(int,open(0).read().split())
graph=[[]*n for _ in range(n)]
unvis=[True]*n

@lru_cache(maxsize=None)
def dfs(x):
	for y in graph[x]:
		if unvis[y]:
			unvis[y]=False
			dfs(y)
			
for i,j in zip(l[::3],l[1::3]):
	graph[i-1].append(j-1)
	graph[j-1].append(i-1)

ans=0
for x in range(n):
	if unvis[x]:
		unvis[x]=False
		dfs(x)
		ans+=1
print(ans)

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

	def find(self, x):
		if(self.root[x] < 0):
			return x
		else:
			self.root[x] = self.find(self.root[x])
			return self.root[x]
			
	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if(x == y):
			return 0
		elif(self.rank[x] > self.rank[y]):
			self.root[x] += self.root[y]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			self.root[x] = y
			if(self.rank[x] == self.rank[y]):
				self.rank[y] += 1
	
	def f(self, x):
		return self.root[x] < 0
		
n,m,*l=map(int,open(0).read().split())
uf=UnionFind(n)
for i,j in zip(l[::3],l[1::3]):
	uf.unite(i,j)
print(sum(uf.f(i) for i in range(1,n+1)))

Solution (Python):

import sys

sys.setrecursionlimit(10 ** 9)


def dfs(v: int) -> None:
    for u in G[v]:
        if not visited[u]:
            visited[u] = color
            dfs(u)


def main():
    global G, visited, color
    N, M, *X = map(int, open(0).read().split())
    G = [[] for _ in range(N + 1)]
    for v, u in zip(X[::3], X[1::3]):
        G[v].append(u), G[u].append(v)
    visited, color = [0] * (N + 1), 1
    for v in range(1, N + 1):
        if not visited[v]:
            visited[v] = color
            dfs(v)
            color += 1
    ans = color - 1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

def dfs(start: int) -> None:
    stack = [start]
    while stack:
        v = stack.pop()
        for u in G[v]:
            if not visited[u]:
                visited[u] = color
                stack.append(u)


def main():
    global G, visited, color
    N, M, *X = map(int, open(0).read().split())
    G = [[] for _ in range(N + 1)]
    for v, u in zip(X[::3], X[1::3]):
        G[v].append(u), G[u].append(v)
    visited, color = [0] * (N + 1), 1
    for v in range(1, N + 1):
        if not visited[v]:
            visited[v] = color
            dfs(v)
            color += 1
    ans = color - 1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

import sys

sys.setrecursionlimit(10 ** 7)


class UnionFind(object):
    """docstring for UnionFind"""

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

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

    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(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 is_root(self, x):
        return self.v[x] < 0

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


def solve(N: int, M: int, X: "List[int]", Y: "List[int]", Z: "List[int]"):
    uf = UnionFind(N)
    for x, y, z in zip(X, Y, Z):
        uf.unite(x - 1, y - 1)

    print(sum(1 for i in range(N) if uf.is_root(i)))

    return




def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    X = [int()] * (M)  
    Y = [int()] * (M)  
    Z = [int()] * (M)  
    for i in range(M):
        X[i] = int(next(tokens))
        Y[i] = int(next(tokens))
        Z[i] = int(next(tokens))
    solve(N, M, X, Y, Z)


if __name__ == '__main__':
    main()

Solution (Python):

import sys

sys.setrecursionlimit(10 ** 7)


class UnionFind(object):
    """docstring for UnionFind"""

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

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

    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(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 is_root(self, x):
        return self.v[x] < 0

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


def solve(N: int, M: int, X: "List[int]", Y: "List[int]", Z: "List[int]"):
    uf = UnionFind(N)
    for x, y, z in zip(X, Y, Z):
        uf.unite(x - 1, y - 1)

    print(sum(1 for i in range(N) if uf.is_root(i)))

    return




def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    X = [int()] * (M)  
    Y = [int()] * (M)  
    Z = [int()] * (M)  
    for i in range(M):
        X[i] = int(next(tokens))
        Y[i] = int(next(tokens))
        Z[i] = int(next(tokens))
    solve(N, M, X, Y, Z)


if __name__ == '__main__':
    main()

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())
UF=UnionFind(n)
for i in range(m):
    a,b,c=map(int,input().split())
    UF.Unite(a-1,b-1)
s=set()
for i in range(n):
    s.add(UF.Find_Root(i))
print(len(s))

Solution (Python):
N, M = map(int, input().split())
graph = {}
visited = {}
for v in range(1,N+1):
    graph[v] = []
    visited[v] = False

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

def dfs(v):
    Q = [v]
    visited[v] = True
    while Q:
        v = Q.pop()
        for u in graph[v]:
            if not visited[u]:
                visited[u] = True
                Q.append(u)

count = 0
for i in range(1,N+1):
    if not visited[i]:
        dfs(i)
        count += 1
print(count)

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())
    x, y = x-1, y-1
    graph[x].append(y)
    graph[y].append(x)
visited = [False for i in range(N)]
def dfs(v):
    Q = []
    visited[v] = True
    Q.append(v)
    while len(Q) > 0:
        v = Q.pop()
        for u in graph[v]:
            if not visited[u]:
                visited[u] = True
                Q.append(u)

count = 0
for i in range(N):
    if not visited[i]:
        dfs(i)
        count += 1
print(count)

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

a = input().split()
N = int(a[0])
M = int(a[1])

l = []
f = []
for i in range(N):
	temp = []
	l.append(temp)
	f.append(0)

for i in range(M):
	b = input().split()
	X = int(b[0]) - 1
	Y = int(b[1]) - 1
	l[X].append(Y)
	l[Y].append(X)

def search(cnt, li, flag, num):
	if(flag[num] == 0):
		flag[num] = cnt
		if(len(li[num]) != 0):
			for i in range(len(li[num])):
				search(cnt, li, flag, li[num][i])
		
cnt = 0
for i in range(N):
	if(f[i] == 0):
		cnt += 1
		search(cnt, l, f, i)			
print(cnt)

Solution (Python):

import sys

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

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

def solve(N: int, M: int, X: "List[int]", Y: "List[int]", Z: "List[int]"):
    uf = UnionFind(N)
    for i in range(M):
        uf.unite(X[i], Y[i])
    v = []
    for i in range(N):
        v.append(uf.find_root(i))
    print(len(set(v)))
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    X = [int()] * (M)  
    Y = [int()] * (M)  
    Z = [int()] * (M)  
    for i in range(M):
        X[i] = int(next(tokens)) - 1
        Y[i] = int(next(tokens)) - 1
        Z[i] = int(next(tokens)) % 2
    solve(N, M, X, Y, Z)

if __name__ == '__main__':
    main()

Solution (Python):
def solve(string):
    n, m, *xyz = map(int, string.split())
    t = [-1] * (n + 1)

    def union(r1, r2):
        if r1 != r2:
            t[max(r1, r2)] = min(r1, r2)

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

    for x, y, _ in zip(*[iter(xyz)] * 3):
        union(find(x), find(y))
    return str(t.count(-1) - 1)


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(m)])))

Solution (Python):
def solve(string):
    n, m, *xyz = map(int, string.split())
    t = [-1] * (n + 1)

    def union(r1, r2):
        if r1 != r2:
            t[max(r1, r2)] = min(r1, r2)

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

    for x, y, z in zip(*[iter(xyz)] * 3):
        union(find(x), find(y))
    return str(t[1:].count(-1))


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(m)])))

Solution (Python):
def solve(string):
    n, m, *xyz = map(int, string.split())
    t = [-1] * (n + 1)
    for x, y, z in zip(*[iter(xyz)] * 3):

        def union(r1, r2):
            if r1 != r2:
                t[max(r1, r2)] = min(r1, r2)

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

        union(find(x), find(y))
    return str(t[1:].count(-1))


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(m)])))

Solution (Python):
def solve(string):
    n, m, *xyz = map(int, string.split())
    t = [-1] * (n + 1)
    for x, y, z in zip(*[iter(xyz)] * 3):

        def union(r1, r2):
            new_root = min(r1, r2)
            if r1 != r2:
                t[max(r1, r2)] = new_root

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

        union(find(x), find(y))
    return str(t[1:].count(-1))


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(m)])))

Solution (Python):
from scipy.sparse import csr_matrix as csr
from scipy.sparse.csgraph import connected_components as cc


def solve(string):
    n, m, *xyz = map(int, string.split())
    return str(cc(csr(([1] * m, (xyz[::3], xyz[1::3])), shape=(n + 1, n + 1)))[0] - 1)


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(m)])))

Solution (Python):
def solve(string):
    n, m, *xyz = map(int, string.split())
    t = [-1] * (n + 1)
    for x, y, z in zip(*[iter(xyz)] * 3):

        def update(x, y):
            r1, p1 = x
            r2, p2 = y
            new_root = min(r1, r2)
            if r1 != r2:
                p2.append(max(r1, r2))
            for p in p1:
                t[p] = new_root
            for p in p2:
                t[p] = new_root

        def get_root(x):
            path = [x]
            curr = t[x]
            while curr != -1:
                path.append(curr)
                curr = t[curr]
            root = path.pop()
            return root, path

        update(get_root(x), get_root(y))
    return str(t[1:].count(-1))


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(m)])))

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
a=[[] for i in range(n)]
for i in range(m):
    u,v,w=map(int,input().split())
    a[u-1].append((v-1,w))
    a[v-1].append((u-1,w))
b=[None for i in range(n)]
def k(v,dis):
    b[v]=dis
    for next_v,w in a[v]:
        if b[next_v]!=None:
            continue
        if w%2==0:
            k(next_v,dis)
        else:
            k(next_v,1-dis)
c2=0
for i in range(n):
    if b[i]==None:
        k(i,0)
        c2+=1
print(c2)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
from math import factorial, ceil, floor
from bisect import bisect_right as bsr
from operator import itemgetter as ig
from collections import defaultdict as dd
from collections import deque, Counter as cnt


args = None
INF = float("inf")
MOD = int(1e9 + 7)
def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]
def nlist(n, v):
    if not n: return v.copy()
    return [nlist(n[1:], v) for _ in range(n[0])]


class UFT:
    def __init__(self, n):
        self.height = [1] * n
        self.group = [-1] * n
    def root(self, v):
        if self.group[v] < 0:
            return v
        self.group[v] = self.root(self.group[v])
        return self.group[v]
    def size(self, v):
        return - self.group[self.root(v)]
    def equal(self, v1, v2):
        v1, v2 = self.root(v1), self.root(v2)
        return v1 == v2
    def merge(self, v1, v2):
        v1, v2 = self.root(v1), self.root(v2)
        if self.equal(v1, v2):
            return False
        if self.height[v1] < self.height[v2]:
            self.group[v2] += self.group[v1]
            self.group[v1] = v2
            self.height[v2] = max(self.height[v1] + 1, self.height[v2])
        else:
            self.group[v1] += self.group[v2]
            self.group[v2] = v1
            self.height[v1] = max(self.height[v1], self.height[v2] + 1)
        return True


def main():
    N, M = input(int, int)
    XYZ = input([[int, 3], M])

    uft = UFT(N + 1)
    for x, y, _ in XYZ:
        uft.merge(x, y)

    cnt = 0
    for t in uft.group[1:]:
        if t < 0:
            cnt += 1
    print(cnt)

if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()

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

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


def dfs(u,v):
  for t in G[u]:
    
    if not Visited[t]:
      Visited[t] = True
      dfs(t,u)

Visited = [False for _ in range(N)]
ans = 0
for i in range(N):
  if not Visited[i]:
    Visited[i] = True
    ans += 1
    dfs(i,-1)
print(ans)

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 main():
    import sys
    
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = UnionFind(N)
    for _ in range(M):
        x,y,z = map(int, input().split())
        A.union(x,y)
    answer = []
    for i in range(1,N+1):
        answer.append(A.find(i))
    print(len(set(answer)))    
    
    
    
main()

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

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

    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

uf = UnionFind(N)
for xyz in XYZ:
    uf.union(xyz[0], xyz[1])

set_par = set()
for i in range(1, N+1):
    uf.find(i)
    set_par.add(uf.par[i])
print(len(set_par))

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

N, M = map(int, input().split())
L = [[int(v) - 1 for v in input().split()] for _ in range(M)]

class UnionFind:
    def __init__(self, n):
        self.data = [0] * N
        for i in range(N):
            self.data[i] = i
            
    def get_root(self, x):
        r = self.data[x]
        if r == x:
            return r
        p = self.get_root(r)
        self.data[x] = p
        return p
    
    def unite(self, x, y):
        rx = self.get_root(x)
        ry = self.get_root(y)
        
        if rx != ry:
            self.data[rx] = ry
            
    def same(self, x, y):
        return self.get_root(x) == self.get_root(y)
    
u = UnionFind(N)
for a, b, _ in L:
    u.unite(a, b)
    
s = set()
for i in range(N):
    s.add(u.get_root(i))

print(len(s))

Solution (Python):
import sys
sys.setrecursionlimit(100000)
n , m = map(int,input().split())
g = [i for i in range(n)]
def find(x):
    if g[x] == x:
        return x
    g[x] = find(g[x])
    return g[x]
def union(x,y):
    x = find(x)
    y = find(y)
    if x!=y:
        g[x] = y

for i in range(m):
    xi,yi,zi = map(int,input().split())
    union(xi-1,yi-1)

ans = 0
for i in range(n):
    if find(i) == i:
        ans += 1
print(ans)

Solution (Python):
n,m=map(int,input().split())
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)]

uf=UnionFind(n)
for _ in range(m):
    x,y,z=map(int,input().split())
    uf.Unite(x,y)
ans=set()
for i in range(1,n+1):
    ans.add(uf.Find_Root(i))
print(len(ans))

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]

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

e_list = [[] for i in range(N)]

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

from collections import deque

def BFS(vi,color,color_list):
    Q = deque([vi])
    color_list[vi]=color
    while len(Q)>0:
        v = Q.pop()
        for v1 in e_list[v]:
            if color_list[v1]==-1:
                color_list[v1]=color
                Q.appendleft(v1)

color_list = [-1]*N
color = 0

for i in range(N):
    if color_list[i]==-1:
        BFS(i,color,color_list)
        color+=1

print(color)

Solution (Python):

import collections
import itertools

def getint(): return int(input())
def getints(): return list(map(int, input().split()))



class UnionFind:
    def __init__(self, node_count):
        self.group_count = node_count
        self.par = [-1] * node_count
    def root(self, x):
        if self.par[x] < 0:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]
    def connect(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        self.group_count -= 1
        if self.par[y] < self.par[x]:
            x, y = y, x
        self.par[x] += self.par[y]
        self.par[y] = x
        return True
    def same(self, x, y):
        return self.root(x) == self.root(y)
    def get_size(self, x):
        return -self.par[self.root(x)]
    def get_groupsize(self):
        return self.group_count


n,m=getints()
uf = UnionFind(n)

for i in range(m):
    x,y,_=getints()
    uf.connect(x-1,y-1)

print(uf.group_count)

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())
UF = UnionFind(n)
for i in range(m):
  x, y, z = map(int, input().split())
  UF.Unite(x,y)

print(sum(x<0 for x in UF.root[1:]))

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

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

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

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

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


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

par = [uf.root(i) for i in range(n)]
print(len(set(par)))