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:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
N,M=map(int,input().split())
XYZ=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N+1)]
ittenai=[]
for x,y,z in XYZ:
    data[x].append(y)
    data[y].append(x)
    ittenai.append(x)
    ittenai.append(y)


ittenai=set(ittenai)
count=N-len(ittenai)
while ittenai:
    x=ittenai.pop()
    stack=deque([x])

    count+=1
    while stack:
        num=stack.popleft()
        for i in data[num]:
            if i in ittenai:
                ittenai.remove(i)
                stack.append(i)
print(count)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

#########
class UnionFind():
    """
    parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
    find(x):要素xの属するグループの根を返す
    size(x):要素xの属するグループの要素数を返す
    same(x,y):x,yが同じグループに属しているか返す
    members(x):要素xが属するグループに属する要素をリストで返す
    roots(x):全ての根の要素を返す
    group_counte():グループの数を返す
    all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
    """
    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 Kruskal(V,edges):
        """
        V:node数
        edges:[u,v,cost]の辺のリスト
        
        return: 最小全域木のコストの和
        """
        #edges = sorted(edges, key=lambda x: x[2])  # costでself.edgesをソートする
        res = 0
        uf=UnionFind(V)
        for e in edges:
            if not uf.same(e[0], e[1]):
                uf.union(e[0], e[1])
                res += e[2]
        return res

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

N,M=map(int,input().split())
edges=[]

for i in range(M):
    x,y,z=map(int,input().split())
    edges.append((x-1,y-1,1))
    
E=Kruskal(N,edges)
print(N-E)

Submission status: Accepted

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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()

# Aでxの根を求める
def find(A, x):
    p = A[x]
    if p == x:
        return x
    a = find(A, p)
    A[x] = a
    return a

# Aでxとyの属する集合の併合
def union(A, x, y):
    if find(A, x) > find(A, y):
        bx, by = find(A, y), find(A, x)
    else:
        bx, by = find(A, x), find(A, y)
    # 根をbx(値の小さい方)に統一 
    A[by] = bx

V = [i for i in range(N)]
for i in range(M):
    x, y, z = lr()
    if find(V, x-1) != find(V, y-1):
        union(V, x-1, y-1)

answer = [find(V, x) for x in set(V)]
print(len(set(answer)))
# 36

Submission status: Accepted

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

def f(j):
  a[j]=1
  n=len(dic[j])
  for k in range(n):
    if a[dic[j][k]]==0:
      f(dic[j][k])

N, M=map(int, input().split())
dic={}
for i in range(1, N+1):
  dic[i]=[]

for i in range(M):
  x, y, z=map(int, input().split())
  dic[x].append(y)
  dic[y].append(x)
  
a=[0]*(N+1)
out=0
i=1
while i<N+1:
  if a[i]==0:
    a[i]=1
    out+=1
    n=len(dic[i])
    for j in range(n):
      if a[dic[i][j]]==0:
        f(dic[i][j])
  i+=1
print(out)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m = inpl()
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())

#初期化
uf = UnionFind(n)
for i in range(m):
    a,b,c = inpl()
    uf.union(a-1,b-1)
print(uf.group_count())

Submission status: Accepted

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

class Union:
  def __init__(self, num):
    self.T = [-1 for i in range(num)]

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

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

  def merge(self, x, y):
    a = self.root(x)
    b = self.root(y)
    if a == b: return False
    if self.size(a) < self.size(b): a, b = b, a
    self.T[a] += self.T[b]
    self.T[b] = a
    return True

uni = Union(N)

for i in range(M):
  x, y, z = XYZ[i]
  x -= 1
  y -= 1
  z -= 1
  uni.merge(x, y)

ans = 0
for i in range(N):
  if uni.T[i] < 0:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
n,m=map(int,input().split())
xyz=[list(map(int,input().split())) for i in range(m)]
# print(xyz)
class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.weight = [0] * (n+1)


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

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

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

    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

uf=WeightedUnionFind(n)
for i in range(m):
    uf.union(xyz[i][0] ,xyz[i][1],1)

dic={}
for i in range(n):
    tmp=uf.find(i+1)
    if tmp in dic:
        continue
    else:
        dic[tmp]=1

print(len(dic.values()))

Submission status: Accepted

Solution code:
def rt(i):
    while i!=G[i][0]:
        i = G[i][0]
    return i
N,M = map(int,input().split())
G = {i:[i,1] for i in range(1,N+1)}
for _ in range(M):
    X,Y,Z = map(int,input().split())
    rx = rt(X)
    ry = rt(Y)
    if rx!=ry:
        if G[rx][1]>=G[ry][1]:
            G[ry][0] = rx
            G[rx][1] += G[ry][1]
        else:
            G[rx][0] = ry
            G[ry][1] += G[rx][1]
cnt = 0
A = []
for i in range(1,N+1):
    A.append(rt(i))
A = list(set(A))
print(len(A))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def root(x):
        if par[x] == x:
            return x
        par[x] = root(par[x])
        return par[x]
    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
    n,m = LI()
    par = [i for i in range(n)]
    rank = [0]*n
    for i in range(m):
        x,y,z = LI()
        x -= 1
        y -= 1
        if root(x) != root(y):
            unite(x,y)
    s = set([root(i) for i in range(n)])
    print(len(s))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
xyz=[tuple(map(int,input().split())) for i in range(M)]
class unionFind:
    parent = []
    num=0
    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.num=N
    def root(self, x):
        if self.parent[x] == x:
            return(x)
        else:
            self.parent[x] = self.root(self.parent[x])
            return(self.parent[x])

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

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            self.num-=1
            return
G=unionFind(N)
for x,y,z in xyz:
  G.unite(x,y)
print(G.num)

Submission status: Accepted

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

par = [i for i in range(N)]
rank = [0 for i in range(N)]


def get_root(A):
    if par[A] == A:
        return A
    par[A] = get_root(par[A])
    return par[A]


def connect(A, B):
    A = get_root(A)
    B = get_root(B)
    if rank[A] < rank[B]:
        par[A] = B
    else:
        par[B] = A
        if rank[A] == rank[B]:
            rank[A] += 1


def verify_connect(A, B):
    if get_root(A) == get_root(B):
        return True
    else:
        return False


for i in range(M):
    x, y, z = map(int, input().split())
    connect(x-1, y-1)
ans = 0
for i in range(N):
    if i == get_root(i):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

N, M = (int(x) for x in input().split())

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

searched = [False] * N
count = 0
for i in range(N):
	if searched[i] == True:
		continue

	count += 1
	stack = [i]
	searched[i] = True
	while len(stack) > 0:
		node = stack.pop()	
		for n in adj_list[node]:
			if searched[n] == False:
				stack.append(n)
				searched[n] = True

print(count)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ABZ = [list(map(int, input().split())) for _ in range(M)]
 
root = [i for i in range(N + 1)]
comp_size = [1] * (N+1)
 
def root_find(x):
  y = root[x]
  if x == y:
    return x
  else:
    z = root_find(y)
    root[x] = z
    return z

def merge(x, y):
  #print(x, y)
  rx = root_find(x)
  ry = root_find(y)
  sx = comp_size[rx]
  sy = comp_size[ry]
  if rx == ry:
    return 0
  else:
    if sx >= sy:
      root[ry] = rx
      comp_size[rx] = sx + sy
    else:
      root[rx] = ry
      comp_size[ry] = sx + sy
    return sx * sy

for a, b, z in ABZ:
  merge(a, b)
#print("root:", root)

check = [0] * (N + 1)
answer = 0
for i in range(1, N + 1):
  ri = root_find(i)
  if check[ri] == 0:
    answer += 1
    check[ri] = 1

print(answer)

Submission status: Accepted

Solution code:
# union-findで行けそう。

n, m = map(int, input().split())
par = [-1] * (n + 1)


def find(a):
    if par[a] < 0:
        return a
    else:
        par[a] = find(par[a])
        return par[a]


def unite(a, b):
    a = find(a)
    b = find(b)
    if a == b:
        return False
    else:
        if par[a] < par[b]:
            a, b = b, a
        par[a] += par[b]
        par[b] = a
        return True


for i in range(m):
    x, y, z = map(int, input().split())
    unite(x, y)
cnt = 0
for i in range(n):
    if par[i + 1] < 0:
        cnt += 1
print(cnt)

Submission status: Accepted

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

#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)]

#xが属するグループの要素全てを返す
def members(x):
    root = find(x)
    return [i for i in range(n) if find(i) == root]

#全ての根の要素をlistで返す(一個下の関数で使う)
def roots():
    return [i for i,x in enumerate(par) if x < 0]

#グループ数を返す
def group_count():
    return len(roots())

#根をkey,そのグループに含まれる要素をvalueとして全てを辞書型で返す
def all_group_members():
    return {r: members(r) for r in roots()}

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

"""
uniteでまとめ、findで見つける。
n(要素数)だけ最初に付け加えること。
"""
lst = []
for i in range(m):
    x,y,z = map(int,input().split())
    x,y = x-1,y-1
    if z%2 == 0:
        unite(x,y)
    else:
        lst.append([x,y])

for i,j in lst:
    unite(i,j)

print(group_count())

Submission status: Accepted

Solution code:
import sys

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
    def find(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        self.parent[x] = y

def main():
    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)
    s = set()
    for i in range(N):
        s.add(uf.find(i))
    print(len(s))

if __name__ == "__main__":
    sys.setrecursionlimit(10**6)
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    edge=[[] for _ in range(N)]
    for i in range(M):
        X,Y,Z=map(lambda x:int(x)-1,input().split())
        edge[X].append(Y)
        edge[Y].append(X)
    used=[False]*N
    ans=0
    for i in range(N):
        if not used[i]:
            ans+=1
            queue=deque()
            queue.append(i)
            while queue:
                node=queue.popleft()
                used[node]=True
                for nextnode in edge[node]:
                    if not used[nextnode]:
                        queue.append(nextnode)
    print(ans)
                    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

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


ans = 0
is_used = [False]*N
for i in range(N):
  if is_used[i]:
    continue
  
  ans += 1
  is_used[i] = True
  d = deque([i])
  while d:
    node = d.pop()
    children = tree[node]
    for child in children:
      if is_used[child]:
        continue
      
      is_used[child] = True
      d.append(child)

print(ans)

Submission status: Accepted

Solution code:

class UnionFindPathCompression():
    def __init__(self, n):
        self.parents = list(range(n))

    def find(self, x):
        if self.parents[x] == x:
            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

        self.parents[y] = x

    def roots(self):
        r=[i for i,x in enumerate(self.parents) if i==x]
        return len(r)

if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    LIST=[list(map(int,input().split())) for i in range(M)]
    union_find=UnionFindPathCompression(N)
    for l in LIST:
        union_find.union(l[0]-1,l[1]-1)
    print(union_find.roots())

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
        elif 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.menbers(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__':
    N,M=list(map(int,input().split()))
    LIST=[list(map(int,input().split())) for i in range(M)]
    union_find=UnionFind(N)
    for l in LIST:
        union_find.union(l[0]-1,l[1]-1)

    print(union_find.group_count())

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 = [int(_) for _ in input().split()]
l = []
for i in range(m):
    x, y, z = [int(_) for _ in input().split()]
    l.append((x, y))

uf = UnionFind(n)
for i in range(len(l)):
    x, y = l[i]
    uf.union(x - 1, y - 1)
ans = uf.group_count()
print(ans)

Submission status: Accepted

Solution code:
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
    else:
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        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())
par = [-1]*n

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

tank = set([])
for i in range(n):
    tank.add(find(i))
print(len(tank))

Submission status: Accepted

Solution code:
def main():


    #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
        else:
            if par[x] > par[y]:
                x,y = y,x
            par[x] += par[y]
            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())
    par = [-1]*n

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = lambda: sys.stdin.readline().rstrip()

n, m = map(int, input().split())
g =  [list() for i in range(n)]

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

visited = [False] * n

def dfs(v, p):
    visited[v] = True
    for nv in g[v]:
        if nv == p or visited[nv]: continue
        dfs(nv, v)

cnt = 0

for v in range(n):
    if not visited[v]:
        dfs(v, -1)
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, num):
        self.table = [-1 for _ in range(num)]

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

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

        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False
N,M = map(int,input().split())
u = UnionFind(N)
for i in range(M):
    x,y,z = map(int,input().split())
    x -= 1
    y -= 1
    u.union(x,y)
ans = []
for i in range(N):
    ans.append(u.find(i))
ans = len(set(ans))
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, m = map(int, input().split())
F = [[] for _ in range(n)]
for _ in range(m):
  x, y, z = map(int, input().split())
  x -= 1
  y -= 1
  F[x].append(y)
  F[y].append(x)
seen = [False]*n
def dfs(v):
  seen[v] = True
  for nv in F[v]:
    if seen[nv]:
      continue
    dfs(nv)
ans = 0
for v in range(n):
  if not seen[v]:
    ans += 1
    dfs(v)
print(ans)

Submission status: Accepted

Solution code:
class Union_Find():
    def __init__(self, num):
        self.par = [-1]*(num+1)
        self.siz = [1]*(num+1)

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

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

    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] < self.par[ry]:
                self.par[ry] = rx
                self.siz[rx] += self.siz[ry]
            elif self.par[rx] > self.par[ry]:
                self.par[rx] = ry
                self.siz[ry] += self.siz[rx]
            else:
                self.par[rx] -= 1
                self.par[ry] = rx
                self.siz[rx] += self.siz[ry]
        return

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


n, m = map(int, input().split())
tree = Union_Find(n)
for i in range(m):
    x, y, z = map(int, input().split())
    tree.union(x, y)

ans = []
for i in range(1, n+1):
    ans.append(tree.find(i))

print(len(set(ans)))

Submission status: Accepted

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

G = {k: [] for k in range(N)}
for _ in range(M):
    X, Y, Z = map(int, input().split())
    # 無向グラフ
    G[X-1].append(Y-1)
    G[Y-1].append(X-1)

visited = [False]*N

sys.setrecursionlimit(1000000)


def dfs(ci):
    for ni in G[ci]:
        if visited[ni] is True:
            continue
        visited[ni] = True
        dfs(ni)


ans = 0
for i in range(N):
    if visited[i] is False:
        ans += 1
        visited[i] = True
        dfs(i)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int, input().split(' '))
abe = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
visited = [0]*(n+1)
for a,b,e in abe:
    graph[a].append(b)
    graph[b].append(a)
stack = []
cnt = 0
append = stack.append
pop = stack.pop
for i in range(1,n+1):
    if visited[i] != 1:
        cnt += 1
        append(i)
    while stack:
        x = pop()
        visited[x] = 1
        for y in graph[x]:
            if visited[y] != 1:
                append(y)
print(cnt)

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 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())
a = [list(map(int, input().split())) for i in range(m)]


uf1=UnionFind(n)
for i in range(m):
    b=a[i][0]
    c=a[i][1]
    uf1.union(b-1,c-1)

ans=uf1.group_count()
print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
#import numpy as np

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 main():
	n,m=map(int,input().split())
	uf=UnionFind(n)
	
	for i in range(m):
		x,y,z=map(int,input().split())
		x-=1;y-=1
		uf.union(x,y)
	print(uf.group_count())
		
		
		
	
	
	
	
	


	
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    known = [False] * N
    rel = [list() for _ in range(N)]
    
    for _ in range(M):
        x, y, z = list(map(int, input().split()))
        rel[x - 1].append(y - 1)
        rel[y - 1].append(x - 1)
    r = 0
    for i in range(N):
        if known[i]:
            continue
        known[i] = True
        r += 1
        cur = rel[i].copy()
        while cur:
            t = cur.pop()
            if not known[t]:
                cur.extend(rel[t])
                known[t] = True
    print(r)

main()

Submission status: Accepted

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components


def solve():
    N, M = map(int, input().split())
    X = [0 for _ in range(M)]
    Y = X[:]
    for i in range(M):
        X[i], Y[i], _ = map(lambda x: int(x)-1, input().split())
    
    graph = csr_matrix(([1]*M, (X, Y)), (N, N))
    ans = connected_components(graph)[0]
    print(ans)


if __name__ == '__main__':
    solve()