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:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        for _ in range(num): return []
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list,zip(*read_all))

#################

#強連結成分分解
#label：グループ数
#group[i]：i個目のノードが所属するグループ
def scc(N, G, RG):
    used = [False]*N
    group = [None]*N
    order = []
    def dfs(S):
        i_order = []
        temp_order = []
        level = 0
        while S:
            v1 = S.pop()
            if used[v1[0]]:
                continue
            if v1[1]<level:
                for _ in range(len(temp_order)-v1[1]):
                    x = temp_order.pop()
                    i_order.append(x)
                level = v1[1]
            level += 1
            if not used[v1[0]]:
                for v1_to in G[v1[0]]:
                    if not used[v1_to]:
                        S.append((v1_to,level))
                temp_order.append(v1[0])
                used[v1[0]] = True
        for t in reversed(temp_order):
            i_order.append(t)
        return i_order
    for i in range(N):
        if not used[i]:
            i_order = dfs([(i,0)])
            order += i_order
    def rdfs(S,col):
        used[S[0]] = True
        while S:
            v1 = S.pop()
            for v1_to in RG[v1]:
                if not used[v1_to]:
                    used[v1_to] = True
                    S.append(v1_to)
            group[v1] = col
    used = [False]*N
    label = 0
    for s in reversed(order):
        if not used[s]:
            rdfs([s], label)
            label += 1
    return label, group

N,M = II()
X,Y,Z = Line(M,3)
 
graph = [[] for _ in range(N)]
for i in range(M):
    graph[X[i]-1].append(Y[i]-1)
    graph[Y[i]-1].append(X[i]-1)
    
label,group = scc(N,graph,graph)
print(label)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        for _ in range(num): return []
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list,zip(*read_all))

#################

#強連結成分分解
#label：グループ数
#group[i]：i個目のノードが所属するグループ
def scc(N, G, RG):
    used = [False]*N
    group = [None]*N
    order = []
    def dfs(S):
        used[S[0]] = True
        while S:
            v1 = S.pop()
            for v1_to in G[v1]:
                if not used[v1_to]:
                    used[v1_to] = True
                    S.append(v1_to)
            order.append(v1)
    for i in range(N):
        if not used[i]:
            dfs([i])
    def rdfs(S,col):
        used[S[0]] = True
        while S:
            v1 = S.pop()
            for v1_to in RG[v1]:
                if not used[v1_to]:
                    used[v1_to] = True
                    S.append(v1_to)
            group[v1] = col
    used = [False]*N
    label = 0
    for s in order:
        if not used[s]:
            rdfs([s], label)
            label += 1
    return label, group

N,M = II()
X,Y,Z = Line(M,3)

graph = [[] for _ in range(N)]
for i in range(M):
    graph[X[i]-1].append(Y[i]-1)
    graph[Y[i]-1].append(X[i]-1)

label,group = scc(N,graph,graph)
print(label)

Submission status: Accepted

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

input = sys.stdin.readline

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

ans = list(range(N))
def root(a):
    if a==ans[a]:
        return a
    else:
        ans[a] = root(ans[a]) 
        return ans[a]

for _ in range(M):
    x, y, _ = map(lambda a: int(a)-1, input().split())
    rx, ry = root(x), root(y)
    if rx != ry:
        ans[ry] = rx

count = 0
for i,a in enumerate(ans):
    count += i==a


print(count)

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split(" "))
edges = {k: set() for k in range(N)}
for i in range(M):
    x, y, z = map(int, input().split(" "))
    x -= 1
    y -= 1
    edges[x].add(y)
    edges[y].add(x)

nodes = list(range(N))
# print(edges)
ans = 0
i = 0
seen = set()
while i < len(nodes):
    n = nodes[i]
    i += 1
    if n in seen:
        continue

    ans += 1
    Q = deque()
    Q.append(n)
    while Q:
        s = Q.pop()
        if s in seen:
            continue
        seen.add(s)
        for t in edges[s]:
            Q.append(t)

print(ans)

Submission status: Accepted

Solution code:
#解説チラ見
n,m = map(int,input().split())
ans = n
pre = [i for i in range(n)]
for _ in range(m):
  x,y,z = map(lambda x: int(x)-1, input().split())
  X = [x]
  while pre[x] != x:
    x = pre[x]
    X.append(x)
  Y = [y]
  while pre[y] != y:
    y = pre[y]
    Y.append(y)
  if x != y:
    ans -= 1
    for xx in X:
      pre[xx] = y
    for yy in Y:
      pre[yy] = y
    pre[x] = y
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

N, M = map(int, input().split())
E = defaultdict(list)
for i in range(M):
    x, y, z = map(int, input().split())
    E[x - 1].append(y - 1)
    E[y - 1].append(x - 1)
visited = [False] * N
ans = 0
q = deque()
for i in range(N):
    if not visited[i]:
        ans += 1
        visited[i] = True
        q.append(i)
        while q:
            nxt = q.pop()
            for j in E[nxt]:
                if not visited[j]:
                    visited[j] = True
                    q.append(j)
print(ans)

Submission status: Accepted

Solution code:
import sys
# input関係の定義
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
# template


# PyPyだと再帰が遅いので注意
# BEGIN CUT HERE
class UnionFind():
    '''
    UnionFind木

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

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

    '''

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

    def unite(self, x: int, y: int) -> bool:
        '''x と y を結合'''
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False  # 元々結合されている場合はFalseを返し終了する
        elif self._data[x] > self._data[y]:
            x, y = y, x  # swap
        self._data[x] += self._data[y]
        self._data[y] = x
        return True

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

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

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

# END CUT HERE

# BEGIN CUT HERE
class QuickFind():
    def __init__(self, n):
        self.i2g = [i for i in range(n)]  # i2g[i] := アイテム i の所属するグループの番号
        self.g2i = [[i]for i in range(n)]  # g2i[g]: = グループ g に所属するアイテムたち

    def unite(self, ia, ib):
        '''アイテム ia の所属するグループとアイテム ib の所属するグループを 1 つにする'''
        # ia と ib が同じグループに属しているならば return
        if self.same(ia, ib):
            return
        # ia の所属するグループが ib の所属するグループより小さくならないようにする
        if len(self.g2i[self.i2g[ia]]) < len(self.g2i[self.i2g[ib]]):
            ia, ib = ib, ia
        ga, gb = self.i2g[ia], self.i2g[ib]
        # グループ gb に所属する全てのアイテムをグループ ga に移す
        for j in self.g2i[gb]:
            self.i2g[j] = ga
        self.g2i[ga].extend(self.g2i[gb])
        self.g2i[gb] = []


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

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

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

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

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



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


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

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

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

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

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

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

# verified on 2019/06/23
# Python3:616ms


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


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

    mx = defaultdict(int)
    for i in range(MAX):
        mx[uf.root(i)] += 1
    my = defaultdict(int)
    for i in range(MAX, 2 * MAX):
        my[uf.root(i)] += 1
    ans = 0
    for i in range(2 * MAX):
        ans += mx[i] * my[i]
    print(ans - N)
# verified on 2019/06/23
# Python:580ms

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

if __name__ == '__main__':
    # AOJ_DSL_1_A()
    # ABC120_D()
    ABC126_E()
    # ABC131_F()
    # ATC001B()
    # import cProfile
    # cProfile.run('benchmark()', sort=0)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)

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

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# ABC126E - 1 or 2
import sys

sys.setrecursionlimit(10 ** 9)


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


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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC126E - 1 or 2
def dfs(start: int) -> None:
    stack = [start]
    while stack:
        v = stack.pop()
        for u in G[v]:
            if not visited[u]:
                visited[u] = color
                stack.append(u)


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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
# from typing import List
sys.setrecursionlimit(10 ** 7)


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

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

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

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

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

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


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

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

    return


# Generated by 1.1.5 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))
        Y[i] = int(next(tokens))
        Z[i] = int(next(tokens))
    solve(N, M, X, Y, Z)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    # ノード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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
graph = [[] for i in range(N)]
for i in range(M):
    x, y, z = map(int, input().split())
    x, y = x-1, y-1
    graph[x].append(y)
    graph[y].append(x)
visited = [False for i in range(N)]
def dfs(v):
    Q = []
    visited[v] = True
    Q.append(v)
    while len(Q) > 0:
        v = Q.pop()
        for u in graph[v]:
            if not visited[u]:
                visited[u] = True
                Q.append(u)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

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

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

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

Submission status: Accepted

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

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.root = [-1] * (n+1)
        self.rnk = [0] * (n+1)
    
    def find_root(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]

    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1
        
    def same(self, x, y):
        return self.find_root(x) == self.find_root(y)

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

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


# Generated by 1.1.5 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:
def solve(string):
    n, m, *xyz = map(int, string.split())
    t = [-1] * (n + 1)

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

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

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


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

Submission status: Accepted

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

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

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

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


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

Submission status: Accepted

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

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

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

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


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

Submission status: Accepted

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

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

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

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


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

Submission status: Accepted

Solution code:
from scipy.sparse import csr_matrix as csr
from scipy.sparse.csgraph import connected_components as cc


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


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

Submission status: Accepted

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

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

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

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


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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

# エントリーポイント
def main():
    N, M = input(int, int)
    XYZ = input([[int, 3], M])

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

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

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

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

Submission status: Accepted

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

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

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

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

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

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

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