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



Sample input:
3 1
1 2 1


Sample output:
2

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
nodes = [i for i in range(N)]


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


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


def unite(x, y):
    if not same(x, y):
        nodes[root(x)] = root(y)


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


ans = 0
for i in range(len(nodes)):
    if nodes[i] == i:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().strip().split(" "))

pairs = [set() for i in range(N + 1)]
appeared = set()

for i in range(M):
	x, y, z = map(int, input().strip().split(" "))
	
	pairs[x].add(y)
	pairs[y].add(x)
	
	appeared.add(x)
	appeared.add(y)

count_not_appeared = N - len(appeared)

group_count = 0
while appeared:
	cur = appeared.pop()
	queue = [cur]
	while queue:
		cur = queue.pop()
		for n in pairs[cur]:
			if n in appeared:
				appeared.remove(n)
				queue.append(n)
	group_count += 1

print(count_not_appeared + group_count)

Submission status: Accepted

Solution code:
class UFT(): #Union-find tree class
    def __init__(self, N): 
        self.tree = [int(i) for i in range(N)] 
        self.rank = [0 for i in range(N)]

    def find(self, a):
        if self.tree[a] == a: return a
        else:
            self.tree[a] = self.find(self.tree[a])
            return self.tree[a]

    def unite(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b: return
        if self.rank[a] < self.rank[b]: self.tree[a] = b
        else:
            self.tree[b] = a
            if self.rank[a] == self.rank[b]: self.rank[a] += 1

N, M = map(int, input().split())
parent = UFT(N)
for i in range(M):
    x, y, z = map(int, input().split())
    parent.unite(x-1, y-1)
for i in range(N):
    parent.find(i)

print(len(set(parent.tree)))

Submission status: Accepted

Solution code:
def find(x):
    if root[x] == x:
        return x
    else:
        root[x] = find(root[x])
        return root[x]

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

def unite(x,y):
    x = find(x)
    y = find(y)
    if rank[x] == rank[y]:
        root[y] = x
        rank[x] += 1
    elif rank[x] > rank[y]:
        root[y] = x
    elif rank[x] < rank[y]:
        root[x] = y
    
n,m = map(int, input().split())
root = [i for i in range(n)]
rank = [0 for i in range(n)]

for i in range(m):
    x, y, z = [int(i)-1 for i in input().split()]
    if not same(x,y):
        unite(x,y)
    
for i in range(n):
    find(i)

print(len(list(set(root))))

Submission status: Accepted

Solution code:
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)
n,m=map(int,input().split())
uni = UnionFind(n-1)

for i in range(m):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    uni.union(a,b)
t = set([])
for i in range(n):
    p = uni.find(i)
    t.add(p)
print(len(t))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
xyz = [tuple(int(x) - 1 for x in input().split()) for _ in range(m)]


class UnionFind:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

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

        return self.p[x]

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

    def unite(self, x, y):
        u = self.find_root(x)
        v = self.find_root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

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

uft = UnionFind(n)
for x, y, z in xyz:
    uft.unite(x, y)

p = set()
for i in range(n):
    p.add(uft.find_root(i))

print(len(p))

Submission status: Accepted

Solution code:
def root(x):
    if par[x] == x:
        return x
    else:
        par[x] = root(par[x])
        return par[x]

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

def unite(x, y):
    x = root(x)
    y = root(y)
    if rank[x] == rank[y]:
        par[y] = x
        rank[x] += 1
    elif rank[x] > rank[y]:
        par[y] = x
    elif rank[x] < rank[y]:
        par[x] = y
    
N, M = map(int, input().split())
par = [i for i in range(N)]
rank = [0 for i in range(N)]

for i in range(M):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    if not same(x, y):
        unite(x, y)
    
for i in range(N):
    root(i)

par = list(set(par))
print(len(par))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
l = [list(map(int,input().split())) for _ in range(m)]
g = {}
for i in range(1,n+1):
    g[i] = []
for x,y,z in l:
    g[x].append(y)
    g[y].append(x)

def connected_components(graph):
    seen = set()
    def component(n):
        nodes = set([n])
        while nodes:
            n = nodes.pop()
            seen.add(n)
            nodes |= set(graph[n]) - seen
            yield n
    for n in graph:
        if n not in seen:
            yield component(n)

def print_gen(gen):
    a = [list(x) for x in gen]
    print(len(a))

print_gen(connected_components(g))

Submission status: Accepted

Solution code:
import sys
 
 
class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n
 
    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self._root(self.table[x])
            return self.table[x]
 
    def find(self, x, y):
        return self._root(x) == self._root(y)
 
    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
 
 
n, m = map(int, input().split())
uft = UnionFind(n)
for line in sys.stdin:
    x, y, z = map(int, line.split())
    x -= 1
    y -= 1
    uft.union(x, y)
 
ans = 0
for v in uft.table:
    if v < 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline


    #Union Find

    #xの根を求める
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    #xとyの属する集合の併合
    def unite(x,y):
        x = find(x)
        y = find(y)
        
        if x == y:
            return False
        else:
            #sizeの大きいほうがx
            if par[x] > par[y]:
                x,y = y,x
            par[x] += par[y]
            par[y] = x
            return True

    #xとyが同じ集合に属するかの判定
    def same(x,y):
        return find(x) == find(y)

    #xが属する集合の個数
    def size(x):
        return -par[find(x)]

    n,m = map(int,input().split())
    #初期化
    #根なら-size,子なら親の頂点
    par = [-1]*n

    for i in range(m):
        X,Y,Z = map(int,input().split())
        unite(X-1,Y-1)
    
    tank = set([])
    for i in range(n):
        tank.add(find(i))
    print(len(tank))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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)
N,M=map(int,input().split())
a=UnionFind(N)
for i in range(M):
    X,Y,Z=map(int,input().split())
    if a.same_check(X,Y):
        pass
    else:
        a.union(X,Y)
answer=set()
for i in range(1,N+1):
    answer.add(a.find(i))
print(len(answer))

Submission status: Accepted

Solution code:
#Union Find
import sys
input = sys.stdin.readline
 
n,m = map(int,input().split())

#根なら-size,子なら親の頂点
par = [-1]*n

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x != y:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x

#xとyが同じ集合に属するかの判定
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)
 
tank = set([])
for i in range(n):
    p = find(i)
    tank.add(p)
print(len(tank))

Submission status: Accepted

Solution code:
import sys

class UnionFind():
    def __init__(self, n):
        self.parent = [-1] * n
        
    def root(self, x):
        '''
        Returns index of the root of the union to which x belongs to.
        '''

        if self.parent[x] < 0:
            return x

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

    def size(self, x):
        '''
        Returns the size of the union to which input index belongs.
        '''
        
        return -1 * self.parent[self.root(x)]
    
    def unite(self, x, y):
        '''
        Unite two vertices x and y.\n
        Input:
            x and y: indices of vertices to unite.
        '''

        x, y = self.root(x), self.root(y)

        if x == y:
            return False

        else:
            size_x = - self.size(x)
            size_y = - self.size(y)

            if size_x > size_y:
                x, y = y, x

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

            return True


input = sys.stdin.readline
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)

roots = set()

for i in range(N):
    
    roots.add(uf.root(i))

print(len(roots))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)

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

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

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

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

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

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

ans = set()
for i in range(N):
    ans.add(uf.root(i))
print(len(ans))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)

class UnionFind:
    def __init__(self,N):
        self.par = [i for i in range(N)]
 
    def root(self,x):
        if self.par[x] == x:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]
 
    def unite(self,x,y):
        self.rx = self.root(x)
        self.ry = self.root(y)
        if self.rx == self.ry:
            return
        self.par[self.rx] = self.ry
 
    def same(self,x,y):
        self.rx = self.root(x)
        self.ry = self.root(y)
        return self.rx == self.ry
 
N,M = [int(i) for i in input().split()]
uf = UnionFind(N)
 
for _ in range(M):
    x,y,_ = [int(i)-1 for i in input().split()]
    uf.unite(x,y)
 
ans = set()
for i in range(N):
    ans.add(uf.root(i))
 
print(len(ans))

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
N, M = map(int, input().split())
pair = {}
rank = {}
def root(x):
    if x == pair[x]:
        return x
    else:
        pair[x] = root(pair[x])
    return pair[x]

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
      return
    if rx > ry:
        pair[rx] = pair[ry]
    else:
        pair[ry] = pair[rx]

def same(x, y):
    rx = root(x)
    ry = root(y)
    return rx == ry

for i in range(1, N+1):
    pair.setdefault(i, i)

for i in range(1, N+1):
    rank.setdefault(i, 0)

for i in range(M):
    x, y, z = map(int, input().split())
    if not same(x, y):
        if x < y:
            unite(x, y)
        else:
            unite(y, x)
cnt = set()
for k, y in pair.items():
    y = root(y)
    cnt.add(y)
print(len(cnt))

Submission status: Accepted

Solution code:
class UnionFind:

    def __init__(self, n: int):
        self._n = n
        self._parents = [i for i in range(n)]
        self._rank = [1 for _ in range(n)]

    def unite(self, x: int, y: int) -> None:
        px = self.find(x)
        py = self.find(y)

        # 一致していないときはリンクをつける
        if px != py:
            self._link(px, py)

    def _link(self, x: int, y: int):
        if self._rank[x] < self._rank[y]:
            self._parents[x] = y
        elif self._rank[x] > self._rank[y]:
            self._parents[y] = x
        else:
            self._parents[x] = y
            self._rank[y] += 1

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

    def find(self, x: int) -> int:
        if self._parents[x] == x:
            return x

        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]



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

uf = UnionFind(n)

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

s = set()
for i in range(0, n):
    s.add(uf.find(i))

print(len(s))

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
N, M = map(int, input().split())
pair = {}
rank = {}
def root(x):
    if x == pair[x]:
        return x
    else:
        pair[x] = root(pair[x])
    return pair[x]

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx > ry:
        pair[rx] = pair[ry]
    else:
        pair[ry] = pair[rx]

for i in range(1, N+1):
    pair.setdefault(i, i)

for i in range(1, N+1):
    rank.setdefault(i, 0)

for i in range(M):
    x, y, z = map(int, input().split())
    if x < y:
        unite(x, y)
    else:
        unite(y, x)

cnt = set()
for k, y in pair.items():
    y = root(y)
    cnt.add(y)
print(len(cnt))

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
N, M = map(int, input().split())
pair = {}
rank = {}
def root(x):
    if x == pair[x]:
        return x
    else:
        pair[x] = root(pair[x])
    return pair[x]

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx > ry:
        pair[rx] = pair[ry]
    else:
        pair[ry] = pair[rx]

for i in range(1, N+1):
    pair.setdefault(i, i)

for i in range(1, N+1):
    rank.setdefault(i, 0)

tmp = []
for i in range(M):
    tmp.append(list(map(int, input().split())))
tmp.sort()
for i in range(M):
    x, y = tmp[i][0], tmp[i][1]
    if x < y:
        unite(x, y)
    else:
        unite(y, x)

cnt = set()
for k, y in pair.items():
    y = root(y)
    cnt.add(y)
print(len(cnt))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3.4

# abc126_e

import sys

sys.setrecursionlimit(10**5+4)

def main():
    # input
    n, m = [int(s) for s in input().split()]
    to = [list() for _ in range(n)]
    for _ in range(m):
        x, y, _ = [int(s) for s in input().split()]
        x -= 1
        y -= 1
        to[x].append(y)
        to[y].append(x)
    # get ans
    colors = [None] * n
    counter = 0
    def dfs(cur, c):
        if colors[cur] != None:
            return
        colors[cur] = c
        for i in to[cur]:
            dfs(i, c)
    for i in range(n):
        if colors[i] == None:
            dfs(i, counter)
            counter += 1
    ans = counter
    # output
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
 
    def root(self, i):
        if self.parent[i] == i:
            return i
        else:
            self.parent[i] = self.root(self.parent[i])
            return self.parent[i]
    
    def find(self, x, y):
        return self.root(x) == self.root(y)
 
    def union(self, i, j):
        i = self.root(i)
        j = self.root(j)
        self.parent[j] = i
N, M = map(int, input().split())
tree = UnionFind(N)
for _ in range(M):
    x, y, z = map(int, input().split())
    tree.union(x-1, y-1)
for i in range(N):
    tree.root(i)
print(len(set(tree.parent)))

Submission status: Accepted

Solution code:
import sys
import math 
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()

class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)
        # グループの数を記憶しておく
        self.root_num=n

    def Tree_num(self):
        return self.root_num
    # ノードxのrootノードを見つける
    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):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
            self.root_num-=1

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            self.root_num-=1
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

N,M=na()
UF = UnionFind(N)
for i in range(M):
    x,y,z=na()
    UF.Unite(x,y)

print(UF.Tree_num())

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
XYZ = []
for _ in range(M):
    x,y,z = map(int, input().split())
    XYZ.append((x,y,z))
    
pairs = XYZ[:]
known = [False] * (N)

pairs = sorted(pairs)

# UnionFindの元
class UnionFind:
    def __init__(self, n):
        # n : ノード数（ノード番号は0始まり）
        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 is_group(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

# UnionFindでグループ化
def create_union(edges, v_num):
    # edges: 辺
    # v_num: ノード数
    u = UnionFind(v_num)
    for x,y in edges:
        u.union(x,y)
        
    return [u.find(x) for x in range(v_num)]
     
    
edges = [(x,y) for x,y,z in pairs]

parents = create_union(edges, N+1)
union = set()
for p in parents:
    union.add(p)
union_num = len(union) -1
print(union_num)

Submission status: Accepted

Solution code:
# UnionFind
class UnionFind():
    def __init__(self, n):
        self.nodes = [-1] * n  # nodes[x]: 負なら、絶対値が木の要素数

    def get_root(self, x):
        # nodes[x]が負ならxが根
        if self.nodes[x] < 0:
            return x
        # 根に直接つなぎ直しつつ、親を再帰的に探す
        else:
            self.nodes[x] = self.get_root(self.nodes[x])
            return self.nodes[x]

    def unite(self, x, y):
        root_x = self.get_root(x)
        root_y = self.get_root(y)
        # 根が同じなら変わらない
        # if root_x == root_y:
        # pass
        if root_x != root_y:
            # 大きい木の方につないだほうが計算量が減る
            if self.nodes[root_x] < self.nodes[root_y]:
                big_root = root_x
                small_root = root_y
            else:
                small_root = root_x
                big_root = root_y
            self.nodes[big_root] += self.nodes[small_root]
            self.nodes[small_root] = big_root


N, M = map(int, input().split())
uf = UnionFind(N)
get_root, unite, nodes = uf.get_root, uf.unite, uf.nodes

for _ in range(M):
    x, y, _ = map(int, input().split())
    x -= 1
    y -= 1
    unite(x, y)
ans = 0
for i in range(N):
    if nodes[i] < 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#Union Find
import sys
input = sys.stdin.readline
 
n,m = map(int,input().split())

par = [i for i in range(n)] #親
rank = [0]*n #木の深さ

#木の根を求める
def find(x,par):
    if par[x] == x:
        return x
    else:
        par[x] = par[par[x]]
        return find(par[x],par)

#xとyの属する集合の併合
def unite(x,y,par,rank):
    x = find(x,par)
    y = find(y,par)
    
    if x != y:
        #xとyの属している集合が異なる時
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x]==rank[y]:
                rank[x] += 1

#xとyが同じ集合に属するかの判定
def same(x,y,par):
    return find(x,par) == find(y,par)

for i in range(m):
    X,Y,Z = map(int,input().split())
    unite(X-1,Y-1,par,rank)
 
tank = set([])
for i in range(n):
    p = find(i,par)
    tank.add(p)
print(len(tank))

Submission status: Accepted

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

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

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

    def root(self, x):
        if self.nodes[x] != x:
            self.nodes[x] = self.root(self.nodes[x])
        return self.nodes[x]

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

    def unite(self, x, y):
        if self.same(x, y):
            return
        self.nodes[self.root(x)] = self.root(y)

uf = UnionFind(N)

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

group = set()
for node in uf.nodes:
    group.add(uf.root(node))

print(len(group))

Submission status: Accepted

Solution code:
import math
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

# Union-Find #
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
def same(x,y):
    return find(x)==find(y)



N,M = IL()
xyz = [IL() for i in range(M)]

used = [False]*(N+1)

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

init(N)

for x,y,z in xyz:
    unite(x,y)

ans = 0
for i in range(1,N+1):
    if used[find(i)] == False:
        ans += 1
        used[find(i)] = True

print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, N):
        self.N = N
        self.rank = [0] * N
        self.par = [i for i in range(N)]
        self.counter = [1] * N

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            z = self.counter[x] + self.counter[y]
            self.counter[x], self.counter[y] = z, z
        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 size(self, x):
        x = self.find(x)
        return self.counter[x]

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

    def groups(self):
        group = set()
        for i in range(self.N):
            group.add(self.find(i))
        return len(group)


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

if N == 2:
    print(1)
    quit()


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

ans = graph.groups()
print(ans)

Submission status: Accepted

Solution code:
class UNION_FIND(object):
    def __init__(self,n):
        self.parent=[-1 for i in range(n)]
        
    def root(self,x):
        if self.parent[x]<0:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])
            return self.parent[x]
 
    def size(self,x):
        return -self.parent[self.root(x)]
    def union(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if x==y:
            return False
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]  #Aのサイズを更新する
        self.parent[y]=x   #Bの親をAに変更する
        return True
n,m=map(int,input().split())
u=UNION_FIND(n)
for i in range(m):
    a,b,c=map(int,input().split())
    u.union(a-1,b-1)
ans=0
for i in u.parent:
    if i<0:
        ans+=1
    
print(ans)

Submission status: Accepted

Solution code:
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

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

for i in range(m):
  x,y,z=map(int,input().split())
  U.union(x-1,y-1)
ans=0
for i,j in enumerate(U.par):
  if i==j:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
def union_find():
    # グラフの連結していないグループの数をunion_findで求める
    def get_parent(node):
        if par[node] == -1:
            return node
        else:
            par[node] = get_parent(par[node])
            return par[node]

    def merge(i, j):
        i = get_parent(i)
        j = get_parent(j)
        if i != j:
            par[j] = i
        return

    n, m = map(int, input().split())
    xyz = [list(map(int, input().split())) for _ in range(m)]
    par = [-1] * n
    for x, y, z in xyz:
        merge(x-1, y-1)
    print(par.count(-1))

union_find()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
N, M = [int(_) for _ in input().split()]
XYZ = [[int(_) for _ in input().split()] for _ in range(M)]

UF = list(range(N + 1))


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


def unite(x, y):
    UF[find(x)] = find(y)


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


for x, y, z in XYZ:
    unite(x, y)
s = set()
for i in range(1, N + 1):
    s.add(find(i))
print(len(set(s)))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.parent = [-1]*size #非負なら親ノード，負ならグループの要素数

    def root(self, x): #root(x): 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]) #xをxの根に直接つなぐ
            return self.parent[x]

    def merge(self, x, y): #merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]: #xの要素数がyの要素数より「小さい」とき入れ替える
            x,y=y,x
        self.parent[x] += self.parent[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True

    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def size(self,x): #size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]
        
        
n,m = [int(i) for i in input().split()]

T=UnionFind(n)
c=0
for _ in [0]*m:
    x,y,z=[int(i) for i in input().split()]
    if T.merge(x-1,y-1):
        c+=1

print(n-c)