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:
# https://atcoder.jp/contests/abc126/tasks/abc126_e
import itertools
from collections import Counter
from collections import defaultdict
import bisect


# Union find
class UnionFind():
    def __init__(self,size):
        self.table = [-1 for _ in range(size)]  # 負の値の場合根を表す。正の値は次の要素を返す、根まで続く

    #集合の代表を求める
    def find(self,x):
        while self.table[x] >= 0:
            #根に来た時,self.table[根のindex]は負の値なのでx = 根のindexで値が返される。
            x = self.table[x]
        return x

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

    def rewrite(self,x, p):
        while self.table[x] >= 0:
            #根に来た時,self.table[根のindex]は負の値なのでx = 根のindexで値が返される。
            tmp = x
            x = self.table[x]
            self.table[tmp] = p
        return

    #併合
    def union(self,x,y):
        s1 = self.find(x)#根のindex,table[s1]がグラフの高さ
        s2 = self.find(y)
        if s1 != s2:#根が異なる場合
            if self.table[s1] != self.table[s2]:#グラフの高さが異なる場合
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                    self.rewrite(y, s1)
                else:
                    self.table[s1] = s2
                    self.rewrite(x, s2)
            else:
                #グラフの長さが同じ場合,どちらを根にしても変わらない
                self.table[s2] = s1
                self.rewrite(y, s1)
        return

    def num_group(self):
        # print(self.table)
        return self.table.count(-1)


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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
N,K=map(int, input().split())

class UnionFindTree:
    def __init__(self, n):
        self.nodes = list(range(n+10))
    def find(self, x):
        if self.nodes[x] == x:
            return x
        parent = self.find(self.nodes[x])
        self.nodes[x] = parent
        return parent
    def unite(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return
        self.nodes[a] = self.nodes[b]
    def is_same(self, a, b):
        return self.find(a) == self.find(b)

uf = UnionFindTree(N)
for i in range(K):
    i,j,k=map(int, input().split())
    uf.unite(i,j)

st = set()
for i in range(1,N+1):
    par = uf.find(i)
    st.add(par)

print(len(st))

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)
        self.size = [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 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 x == y:
            return
        if self.rank[x] > self.rank[y]:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
        else:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

n, m = map(int,input().split())
edges = []
for i in range(m):
    a,b,_ = map(int,input().split())
    edges.append([a-1,b-1])

uf = UnionFind(n)
point = n*(n-1)//2
ans = []

while edges:
    ans.append(point)
    a, b = edges.pop()
    pa = uf.find(a)
    pb = uf.find(b)
    uf.union(a,b)

score = 0
for i in range(n):
    if uf.size[i] != 0:
        score += 1

print(score)

Submission status: Accepted

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

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

visit = [False] * N
ans = 0
for i in range(N):
    if visit[i]:
        continue
    ans += 1
    visit[i] = True
    vlist = nlist[i]
    while vlist:
        tmp = []
        for to in vlist:
            if visit[to]:
                continue
            visit[to] = True
            tmp.extend(nlist[to])
        vlist = tmp

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
A = [list(map(int,input().split())) for i in range(m)]

B = [[] for i in range(n+1)]

deta = [-1 for i in range(n+1)]
for i in range(len(A)):
    B[A[i][0]].append(A[i][1])
    B[A[i][1]].append(A[i][0])
    deta[A[i][0]]=0
    deta[A[i][1]]=0

count = 0
start = 1

while start < n+1 :
    while start < n+1 and deta[start]!=0 :
        start += 1

    if start < n+1 :
        count += 1
        #print("c")

        nurulist = [start]
        t = 0
        while t < len(nurulist):
            k = nurulist[t]
            for j in range(len(B[k])):
                if deta[B[k][j]] == 0:
                    deta[B[k][j]] = 1
                    nurulist.append(B[k][j])
            t += 1

print(count+deta.count(-1)-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


class UnionFind:
    def __init__(self, n):
        self._parents = list(range(n))
        self._ranks = [0] * n
        self._size = [1] * n

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

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

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

        if self._ranks[rx] < self._ranks[ry]:
            self._parents[rx] = ry
            self._size[ry] += self._size[rx]
        else:
            self._parents[ry] = rx
            self._size[rx] += self._size[ry]
            if self._ranks[rx] == self._ranks[ry]:
                self._ranks[rx] += 1

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



def solve(N: int, M: int, X: "List[int]", Y: "List[int]", Z: "List[int]"):
    uf = UnionFind(N)
    qq = UnionFind(N)

    for x, y, z in zip(X, Y, Z):
        x -= 1
        y -= 1
        uf.unite(x, y)
        #if (z % 2) == 0:
        #    uf.unite(x, y)
        #else:
        #    qq.unite(x, y)

    return len(set([uf.root(i) for i in range(N)]))


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))
    result = solve(N, M, X, Y, Z)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


g = Graph()
N, M = [int(i) for i in input().split()]
magic = [1 for i in range(N)]

for i in range(M):
    u, v, w = [int(i) for i in input().split()]
    g.add_edge(u-1, v-1, w)
    g.add_edge(v-1, u-1, w)
    magic[u-1] = 0
    magic[v-1] = 0
ans = sum(magic)

d = Dijkstra(g, 0)

for i in range(N):
    if magic[i] == 0:
        d = Dijkstra(g, i)
        ans += 1
        for j in d.dist.keys():
            #print(j)
            magic[j] = 1

print(ans)

Submission status: Accepted

Solution code:
class Union():
    def __init__(self, N):
        self.Parent = []
        for i in range(N):
            self.Parent.append(-1)

    def root(self, A):
        if (self.Parent[A] < 0):
            return A
        else:
            self.Parent[A] = self.root(self.Parent[A])
            return self.Parent[A]
    def size(self, A):
        return int(-1 * self.Parent[self.root(A)])


    def connect(self, A, B):
        A = self.root(A)
        B = self.root(B)
        if (A == B):
            return False

        if (self.size(A) < self.size(B)):
            A, B = B, A
        self.Parent[A] += self.Parent[B]
        self.Parent[B] = A
        return True


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

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

ans = N

uni = Union(N)

for i in range(M):
    uni.connect(X[i], Y[i])

parents = []

for i in range(N):
    parents.append(uni.root(i))
print(len(set(parents)))

Submission status: Accepted

Solution code:
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]
 
 
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])
 
 
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
 
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
n, m = map(int, input().split())
U=UnionFind(n)
for i in range(m):
    x, y, z = map(int, input().split())
    U.unite(x-1, y-1)
cnt=0
for i in range(n):
    if U.find(i)==i:
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

# Union-Find木
class UnionFind:
    def __init__(self, n):
        self.n = n
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        # 1-indexedのままでOK、その場合は[0]は未使用
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (n+1)
        # あるノードを根とする集合に属するノード数
        self.size = [1] * (n+1)
        # あるノードを根とする集合が木かどうか
        self.tree = [True] * (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 x == y:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

        # 木の高さを比較し、低いほうから高いほうに辺を張る
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    # あるノードの属する集合のノード数
    def get_size(self, x):
        return self.size[self.find(x)]

    # 木かどうかの判定
    def is_tree(self, x):
        return self.tree[self.find(x)]

    # 集合の数
    def len(self):
        res = set()
        for i in range(self.n+1):
            res.add(self.find(i))
        # グループ0の分を引いて返却
        return len(res) - 1

N,M=MAP()
uf=UnionFind(N)
for i in range(M):
    x,y,z=MAP()
    if not uf.same(x, y):
        uf.union(x, y)

print(uf.len())

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納　par[x] == x の時そのノードは根
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0)
        self.rank = [0] * (n+1)
        # 各々の集合の要素数（根が代表して値を持っておく）
        self.count = [1] * (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
            self.count[y] += self.count[x]
            self.count[x] = 0
        else:
            self.par[y] = x
            self.count[x] += self.count[y]
            self.count[y] = 0
            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 size(self,x):
        q = UnionFind.find(self,x)
        return self.count[q]
n, m = map(int,input().split())
u = UnionFind(n)
ans = 0
for i in range(m):
    x,y,z = map(int,input().split())
    x -= 1
    y -= 1

    u.union(x,y)

for i in range(n):
    if u.par[i] == i:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, N):
        # par = parent
        self.par = [i for i in range(N)]
        return

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

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

        self.par[x] = min(x, y)
        self.par[y] = min(x, y)
        return True


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


N, M = inpl()
uf = UnionFind(N)
for i in range(M):
    x, y, z = inpl()
    x -= 1
    y -= 1
    uf.union(x, y)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [-1 for _ in range(n)]

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

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

    def unite(self,x,y):
        x = self.root(x)
        y = self.root(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.root(x)]


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

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

Submission status: Accepted

Solution code:
class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True


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

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

print(len(set([uf.getRootID(i) for i in range(N)])))

Submission status: Accepted

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

onazi = [[] for i in range(N+1)] 
chigau = [[] for i in range(N+1)]

def tuika(l,a,b):
    l[a].append(b)
    l[b].append(a)

for i in range(M):
    X,Y,Z = map(int, input().split())
    if Z%2 == 0:
        tuika(onazi, X, Y)
    else:
        tuika(chigau, X, Y)
        


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

def func(i):
    stack = [i]
    colors[i] = 1

    while stack:
        node = stack.pop()
        for next_node in onazi[node]:
            if colors[next_node]==0:
                stack.append(next_node)
                colors[next_node] = colors[node]

        for next_node in chigau[node]:
            if colors[next_node]==0:
                stack.append(next_node)
                colors[next_node] = - colors[node]

result = 0
for i in range(1,N+1):
    if colors[i] == 0:
        result += 1
        func(i)
print(result)

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 = [int(n) for n in input().split()]
X = [0]*M
Y = [0]*M
Z = [0]*M
UF = UnionFind(N)
adj = [[0, []] for _ in range(N)]
for i in range(M):
    X[i], Y[i], Z[i] = [int(n) for n in input().split()]
    Z[i] %= 2
    X[i] -= 1
    Y[i] -= 1
    UF.union(X[i], Y[i])
s = set([UF.find(0)])
ans = 1

for i in range(1, N):
    tmp = UF.find(i)
    if not(tmp in s):
        ans += 1
        s.add(tmp)
print(ans)

Submission status: Accepted

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

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

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

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

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]


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

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

    for i in range(N):
        uf.find(i)
    # print(uf.par)
    s = set(uf.par)
    print(len(s))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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):
    print(len([list(x) for x in gen]))

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

print_gen(connected_components(d))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.v = [-1 for _ in range(n)]  # 根(負): 連結頂点数 * (-1) / 子(正): 根の頂点番号(0-indexed)

    def find(self, x):  # xを含む木における根の頂点番号を返す
        if self.v[x] < 0:  # (負)は根
            return x
        else:  # 根の頂点番号
            self.v[x] = self.find(self.v[x])  # uniteでは, 旧根に属する頂点の根が旧根のままなので更新
            return self.v[x]

    def unite(self, x, y):  # 違う根に属していたらrankが低くなるように連結
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if -self.v[x] < -self.v[y]:  # size比較, 　(-1) * (連結頂点数 * (-1)), (正)同士の大小比較
            x, y = y, x  # 連結頂点数が少ない方をyにすると, findでの更新回数が減る？
        self.v[x] += self.v[y]  # 連結頂点数の和を取る, 連結頂点数 * (-1)
        self.v[y] = x  # 連結頂点数が少ないy(引数yの根の頂点番号)の根をx(引数xの根の頂点番号)にする

    def root(self, x):
        return self.v[x] < 0  # (負)は根

    def same(self, x, y):
        return self.find(x) == self.find(y)  # 同じ根に属するか

    def size(self, x):
        return -self.v[self.find(x)]  # 連結頂点数を返す


N, M = map(int, input().split())
uf = UnionFind(N * 2)
for _ in range(M):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    if z % 2 == 0:
        uf.unite(x, y)
        uf.unite(x + N, y + N)
    else:
        uf.unite(x, y + N)
        uf.unite(x + N, y)

# print(uf.v)

ans = 0
for i in range(N):
    if uf.root(i):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(m)]

class UnionFind:
    def __init__(self, nn):
        self.par = [i for i in range(nn+1)]
        self.rank = [0] * (nn+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)

u = UnionFind(n)
for i in range(m):
    x = a[i][0]
    y = a[i][1]
    z = a[i][2]
    u.union(x, y)

counter = []
for i in range(n+1):
    counter.append(u.find(i))

print(len(list(set(counter[1:]))))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, elems):
        self.parent = dict()
        self.children = dict()
        for e in elems:
            self.parent[e] = e
            self.children[e] = 1

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

        return self.root(self.parent[e])

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

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

        rx, ry = self.root(x), self.root(y)
        # ry <- rx
        if self.members(ry) < self.members(rx):
            rx, ry = ry, rx

        self.children[ry] += self.children[rx]
        self.parent[rx] = ry

    def members(self, x):
        return self.children[self.root(x)]


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

uf = UnionFind(range(1, n+1))
c = 0
for _ in range(m):
    x, y, z = map(int, input().split())
    if uf.same(x, y):
        continue
    else:
        c += 1
        uf.unite(x, y)

print(n - c)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc126_e
import collections

N, M = map(int, input().split())
triples = [tuple(map(int, input().split())) for _ in range(M)]

connected = collections.defaultdict(list)
for (a, b, _) in triples:
    connected[a].append(b)
    connected[b].append(a)

nodes = set(range(1, N + 1))
seen = set()
cnt = 0

for i in nodes:
    if i not in seen:
        cnt += 1
        stack = [i]
        while stack:
            state = stack.pop()
            for new_state in connected[state]:
                if new_state not in seen:
                    seen.add(new_state)
                    stack.append(new_state)

print(cnt)

Submission status: Accepted

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


class UnionFind(object):
    __slots__ = ["nodes"]

    def __init__(self, n: int):
        self.nodes = [-1]*n # 親: -(属するノード数), それ以外: (親ノードindex)

    def find(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            self.nodes[x] = self.find(self.nodes[x]) # compression
            return self.nodes[x]

    def has_same_root(self, x, y) -> bool:
        return self.find(x) == self.find(y)
    
    def size(self, x) -> int:
        return -self.nodes[self.find(x)]

    def unite(self, x: int, y: int) -> None:
        if self.has_same_root(x, y):
            return

        root_x, root_y = self.find(x), self.find(y)
        if self.nodes[root_x] < self.nodes[root_y]:
            bigroot, smallroot = (root_x, root_y)
        else: 
            bigroot, smallroot = (root_y, root_x)
        self.nodes[bigroot] += self.nodes[smallroot]
        self.nodes[smallroot] = bigroot


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


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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)) - 1
        Y[i] = int(next(tokens)) - 1
        Z[i] = int(next(tokens)) % 2
    solve(N, M, X, Y, Z)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, N):
        # 親の場合は -{その集合のサイズ}
        self.parent = [-1 for _ in range(N)]

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

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

    def connect(self, A, B):
        A = self.root(A)
        B = self.root(B)

        if A == B:
            return False

        if self.size(A) < self.size(B):
            A, B = B, A

        self.parent[A] += self.parent[B]
        self.parent[B] = A
        return True


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

uni = UnionFind(N)

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

dict = {}
for i in range(N):
    r = uni.root(i)
    dict[r] = 1

print(len(dict))