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:
class Unionfind():  # Unionfind
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):  # グループの根
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):  # グループの併合
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def roots(self):  # 根のリスト
        return [i for i, x in enumerate(self.parents) if x < 0]


n, m = map(int, input().split())
xyz = sorted([list(map(int, input().split())) for _ in range(m)])

uf = Unionfind(n)
for x, y, z in xyz:
    uf.union(x - 1, y - 1)
print(len(uf.roots()))

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

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

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

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

        if x == y:
            return

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

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

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

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

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

# カードN枚
# 各カードには1か2が書かれている
N, M = getNM()
# A1 + A2 + 1は偶数
query = []

for i in range(M):
    a, b, c = getNM()
    query.append([a, b, c])

U = UnionFind(N)
for i in query:
    U.union(i[0] - 1, i[1] - 1)

print(U.group_count())

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


class UnionFind:

    def __init__(self, N: int):
        # d[i] = <parent id> if i is a child,
        #       - <size of the group> if i is a root
        self.d = [-1 for _ in range(N)]

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

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

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

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

    def show(self):
        m = {}
        for n in range(len(self.d)):
            r = self.root(n)

            if r not in m:
                m[r] = [n]
            else:
                m[r].append(n)

        print("root -> childs")
        print("---------------------")
        for key in m:
            print("{} -> {}".format(key, m[key]))


def main():
    n, m = geta(int)

    uf = UnionFind(2*n)

    ans = n

    for _ in range(m):
        x, y, z = geta(int)

        united = False
        if z & 1 == 0:
            united = uf.unite(2*x-2, 2*y-2) and uf.unite(2*x-1, 2*y-1)
        else:
            united = uf.unite(2*x-2, 2*y-1) and uf.unite(2*x-1, 2*y-2)

        if united:
            ans -= 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#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+1)

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

ans = 0
for i in range(1,N+1,1):
    if par[i] < 0:
        ans +=1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.ranks = [0 for _ in range(n)]

    def root(self, node):
        parent_node = self.parents[node]
        if parent_node == node:
            return node
        root_node = self.root(parent_node)
        self.parents[node] = root_node  # reduction
        return root_node

    def union(self, one_node, other_node):
        one_root = self.root(one_node)
        other_root = self.root(other_node)
        if one_root == other_root:
            return
        if self.ranks[one_root] < self.ranks[other_root]:
            self.parents[one_root] = other_root
        else:
            self.parents[other_root] = one_root
            if self.ranks[one_root] == self.ranks[other_root]:
                self.ranks[one_root] += 1


def main():
    N, M = list(map(int, input().split(' ')))
    tree = UnionFind(N)
    for _ in range(M):
        x, y, _ = list(map(int, input().split(' ')))
        tree.union(x - 1, y - 1)
    roots = list(map(lambda n: tree.root(n), range(N)))
    print(len(set(roots)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, M: int, X: "List[int]", Y: "List[int]", Z: "List[int]"):
    X = map(lambda x: x-1, X)
    Y = map(lambda x: x-1, Y)
    uf = UnionFind(N)
    for x, y in zip(X, Y):
        uf.union(x, y)
    return len(uf.roots())

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    X = [int()] * (M)  # type: "List[int]"
    Y = [int()] * (M)  # type: "List[int]"
    Z = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        X[i] = int(next(tokens))
        Y[i] = int(next(tokens))
        Z[i] = int(next(tokens))
    print(solve(N, M, X, Y, Z))

# https://note.nkmk.me/python-union-find/
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
 
    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
uf=UnionFind(n)
for i in range(m):
  x,y,z=map(int,input().split())
  uf.union(x-1,y-1)
print(uf.group_count())

Submission status: Accepted

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

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

UF = UnionFind(n)

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

print(UF.group_count())

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit


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

    def find(self, x):
        p = self.parent
        while p[x] >= 0:
            x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        p = self.parent
        if x != y:
            if x > y:
                x, y = y, x
            p[x], p[y] = p[x] + p[y], x

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

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


def main():
    input = stdin.buffer.readline
    n, m = map(int, input().split())
    ans = n - m
    f = UnionFindTree(n)
    for _ in range(m):
        x, y, z = map(int, input().split())
        if f.same(x - 1, y - 1):
            ans += 1
        f.union(x - 1, y - 1)
    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
import sys

input = lambda: sys.stdin.readline().rstrip()


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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


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


def solve():

    uni = UnionFind(N)

    for i in range(M):
        x, y, z = map(int, input().split())
        x, y = x - 1, y - 1
        uni.union(x, y)

    print(uni.group_count())


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return 0
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

N,M,*f = map(int, open(0).read().split())
XYZ = [f[i:i+3] for i in range(0, len(f), 3)]
XY = [(x[0],x[1]) for x in XYZ]
uf = UnionFind(N)
ans = 0
for x, y in XY:
    uf.union(x-1,y-1)
for x in uf.parents:
    if x < 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
    n,m = map(int,input().split())
    graph = {}
    for i in range(n):
        graph[i+1] = []
    for i in range(m):
        x,y,z = map(int,input().split())
        graph[x] += [y]
        graph[y] += [x]
    dis = [-1 for i in range (n)]
    ans = 0
    for i in range(n):
        if dis[i]==-1:
            ans += 1
            que = [i]
            dis[i] = 0
            while len(que)>0:
                s = que.pop(0)
                for nv in graph[s+1]:
                    if dis[nv-1]!=-1:
                        continue
                    dis[nv-1] = 0
                    que.append(nv-1)
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
int1 = lambda x: int(x) - 1

# https://note.nkmk.me/python-union-find/
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


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

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

print(uf.group_count())

Submission status: Accepted

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

def dfs(G,v):
    seen[v] = True 
    for next_v in G[v]:
        if seen[next_v]:
            continue
        dfs(G,next_v)
            
N,M = map(int,input().split())
G = [[]  for _ in range(N)]
seen= [False] * N 
cnt = 0

for i in range(M):
    x,y,z = map(int,input().split())
    G[x-1].append(y-1)
    G[y-1].append(x-1)
    
for v in range(N):
    if seen[v]:
        continue
    dfs(G,v)
    cnt += 1
    
print(cnt)

Submission status: Accepted

Solution code:
from collections import deque
 
n,m = map(int,input().split())
 
root = [[] for i in range(n)]
for _ in range(m):
    a, b ,c = (int(x) for x in input().split())
    root[b-1].append(a-1)
    root[a-1].append(b-1) 

check = [-1]*n

ans = 0

for j in range(n):
  if check[j] != -1: continue
  ans += 1
  check[j] = 1
  stack=deque([j])
  check[0] = 0
  while len(stack)>0:
      v = stack.popleft()
      for i in root[v]:
          if check[i] == -1:
              check[i] = 1
              stack.append(i)
for i in check:
  if i == -1:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

queue = deque()
check = [False for _ in range(n)]
ans = 0
for i in range(n):
    if check[i]:
        continue
    ans += 1
    queue.append(i)
    while queue:
        pos = queue.popleft()
        for next_pos in edge[pos]:
            if check[next_pos]:
                continue
            check[next_pos] = True
            queue.append(next_pos)
print(ans)

Submission status: Accepted

Solution code:
class UnionTree:

	# 節の数
	def __init__(self, N):
		self.__par = [i for i in range(N)]
		self.__rank = [0] * N

	# 根
	def root(self, x):
		if(self.__par[x] == x):
			return x
		else:
			self.__par[x] = self.root(self.__par[x])
			return self.__par[x]

	# 結合
	def unite(self, x, y):
		rx = self.root(x)
		ry = self.root(y)
		if(rx == ry):
			return

		if(self.__rank[rx] < self.__rank[ry]):
			self.__par[rx] = ry
		else:
			self.__par[ry] = rx
			if(self.__rank[rx] == self.__rank[ry]):
				self.__rank[rx] += 1

	# 一致
	def same(self, x, y):
		rx = self.root(x)
		ry = self.root(y)
		if(rx == ry):
			return True
		
		
# N枚のカードとルール
N, M = map(int, input().split())

# UnionTree Class
union_tree = UnionTree(N)

# ルールの適応
for i in range(M):
	# 結合
	a, b, x = map(int, input().split())
	union_tree.unite(a-1, b-1)

# 個数のみ数える
cnt = set()

for i in range(N):
	cnt.add(union_tree.root(i))

print(len(cnt))

Submission status: Accepted

Solution code:
import sys

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


N, M = map(int, sys.stdin.readline().strip().split())
pairs = []
for _ in range(M):
    x, y, z = map(int, sys.stdin.readline().strip().split())
    pairs.append((x-1, y-1, z))

uf = UnionFind(N)
for (x, y, z) in pairs:
    uf.union(x, y)

group = uf.group_count()
print(group)

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    N, M = NMI()
    uf = UnionFind(N)
    for i in range(M):
        x, y, z = NMI()
        uf.unite(x-1, y-1)
    gc = uf.group_count()
    print(gc)


class UnionFind:
    def __init__(self, n):
        #親要素のノード番号を格納　xが根のとき-(サイズ)を格納
        self.par = [-1 for i in range(n)]
        self.n = n

    def find(self, x):
        #根ならその番号を返す
        if self.par[x] < 0:
            return x
        else:
            #親の親は親
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def is_same(self, x, y):
        #根が同じならTrue
        return self.find(x) == self.find(y)

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

        #木のサイズを比較し、小さいほうから大きいほうへつなぐ
        if self.par[x] > self.par[y]:
            x, y = y, x

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

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

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

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

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

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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class UnionFold:
    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.find(self.par[x])
    
    #同じ木に属するか判定
    def same(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
                
def main():
    N,M = map(int, input().split())
    union_fold = UnionFold(N)
    for _ in range(M):
        x,y,z = map(int, input().split())
        if not(union_fold.same(x,y)):
            union_fold.union(x,y)
    
    n=0
    for i in range(1,N+1):
        if union_fold.par[i]==i:
            n+=1
    print(n)
    
main()

Submission status: Accepted

Solution code:
from collections import Counter


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

    def same(self, u, v):
        return self.find_set(u) == self.find_set(v)

    def unite(self, u, v):
        u = self.find_set(u)
        v = self.find_set(v)

        if u == v:
            return

        if self.rank[u] > self.rank[v]:
            self.p[v] = u
            self.size[u] += self.size[v]
        else:
            self.p[u] = v
            self.size[v] += self.size[u]
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1

    def find_set(self, u):
        if u != self.p[u]:
            self.p[u] = self.find_set(self.p[u])

        return self.p[u]

    def update_p(self):
        for u in range(self.n):
            self.find_set(u)

    def get_size(self, u):
        return self.size[self.find_set(u)]


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)

c = Counter(uf.find_set(i) for i in range(n))
ans = len(c)
print(ans)

Submission status: Accepted

Solution code:
# Union-Find
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
    if par[x] > par[y]:
        x, y = y, x
    par[y] = x
    return True


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


def size(x):
    return -par[find(x)]


N, M = map(int, input().split())
# 負のとき size, 非負のとき parent
par = [-1] * N
for i in range(M):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    unite(x, y)

print(par.count(-1))

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

    def group_count(self):
        return len(self.roots())
      
n,m = map(int,input().split()) 

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

Submission status: Accepted

Solution code:
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
# 同一の集合の判定
def same(x, y):
    if find(x) == find(y):
        return True
    else:
        return False
# 集合の併合
def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if par[x] > par[y]:
        x, y = y, x
    par[x] += par[y]
    par[y] = x

# 集合の数
def uCnt(x):
    return -par[find(x)]


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

ans = [i for i in range(N) if par[i] < 0]
print(len(ans))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(10**6)
def dfs(i,c):
    visited[i]=1
    col[i] = c
    for j in edge[i]:
        if not visited[j[0]]:
            if j[1]%2==0:
                dfs(j[0],c)
            else:
                dfs(j[0],-1*c)
class UnionFind:
    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.rank = [0]*N
        self.count = 0
    def root(self, a):
        if self.parent[a]==a:
            return a
        else:
            self.parent[a]=self.root(self.parent[a])
            return self.parent[a]
    def size(x):
        return -par[root(x)]

    def is_same(self, a, b):
        return self.root(a)==self.root(b)
    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return

        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

def main():
    dd = defaultdict(int)
    n,m=map(int, input().split())
    uf = UnionFind(n)

    for i in range(m):
        x,y,z=map(int, input().split())
        uf.unite(x-1,y-1)
    for i in range(n):
        dd[uf.root(i)]+=1
    print(len(dd))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n,m = map(int,input().split())
    g = {}
    for i in range(m):
        x,y,z = map(int,input().split())
        if x-1 not in g.keys():
            g[x-1] = [y-1]
        else:
            g[x-1] += [y-1]
        if y-1 not in g.keys():
            g[y-1] = [x-1]
        else:
            g[y-1] += [x-1]
    t = [-1 for i in range(n)]
    def bfs(s,t):
        t[s] = 0
        que = [s]
        while len(que)>0:
            v = que.pop(0)
            for nv in g[v]:
                if t[nv]!=-1:
                    continue
                t[nv]=0
                que.append(nv)
        return t

    ans = 0
    for i in range(n):
        s = i
        if t[s]!=-1:
            continue
        if s not in g.keys():
            ans += 1
            continue
        t[s]=0
        ans += 1
        t = bfs(s,t)
    print(ans)

if __name__ == "__main__":
    main()