Problem:


Score : 500 points

Problem Statement

There are N cards placed face down in a row. On each card, an integer 1 or 2 is written.

Let A_i be the integer written on the i-th card.

Your objective is to guess A_1, A_2, ..., A_N correctly.

You know the following facts:

For each i = 1, 2, ..., M, the value A_{X_i} + A_{Y_i} + Z_i is an even number.

You are a magician and can use the following magic any number of times:

Magic: Choose one card and know the integer A_i written on it. The cost of using this magic is 1.

What is the minimum cost required to determine all of A_1, A_2, ..., A_N?

It is guaranteed that there is no contradiction in given input.

Constraints

All values in input are integers.

2 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq X_i < Y_i \leq N

1 \leq Z_i \leq 100

The pairs (X_i, Y_i) are distinct.

There is no contradiction in input. (That is, there exist integers A_1, A_2, ..., A_N that satisfy the conditions.)

Input

Input is given from Standard Input in the following format:

N M
X_1 Y_1 Z_1
X_2 Y_2 Z_2
\vdots
X_M Y_M Z_M

Output

Print the minimum total cost required to determine all of A_1, A_2, ..., A_N.

Sample Input 1

3 1
1 2 1

Sample Output 1

2

You can determine all of A_1, A_2, A_3 by using the magic for the first and third cards.

Sample Input 2

6 5
1 2 1
2 3 2
1 3 3
4 5 4
5 6 5

Sample Output 2

2

Sample Input 3

100000 1
1 100000 100

Sample Output 3

99999



Sample input:
3 1
1 2 1


Sample output:
2

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, data):
        """
        与えられたdataまでの長さの配列を作成
        配列は1から開始する
        それがunionfindの親となり初めは自分自身
        またrankも定義し初期値は0
        """
        self.parent = {}
        self.rank = {}
        for i in range(1, data+1):
            self.parent[i] = i
            self.rank[i] = 0


    def find(self, x):
        """
        与えられた値に対してその親ノードを返却
        """
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x]) # self.parentに入れ直しているのは次findするとき高速になるよう再起により親を直接結んでいる
            return self.parent[x]


    def same(self, x, y):
        """
        与えられた2つの値が同一グループ(親)かチェック
        """
        return self.find(x) == self.find(y)


    def unite(self, x, y):
        """
        与えられた2つの値を同一のグループ(親)にする
        """
        x = self.find(x)
        y = self.find(y)
        if x == y: # すでに同じグループなら何もしない
            return
        if self.rank[x] > self.rank[y]: # ランクが異なる場合小さい方の親を大きい方にする
            self.parent[y] = x
            return
        else: # ランクが同じ場合どちらかの親にする その際親にした方の値のランクをあげる
            self.parent[x] = y
            if self.rank[x] == self.rank[y]: self.rank[y] += 1
            return


N,M = map(int, input().split())
union_find = UnionFind(N)
for i in range(M):
    X,Y,Z = map(int, input().split())
    union_find.unite(X,Y)

ans = 0
for i in range(1,N+1):
    if union_find.find(i) == i:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def main():
    #Union Find
    #locate x 
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    #merge 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 and y in same group
    def same(x,y):
        return find(x) == find(y)
    
    #number of factor of x group
    def size(x):
        return -par[find(x)]

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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

#こっからunion-find

#各ノードの親を格納するリスト
par = [i for i in range(n+1)]
#各木の根に対するrankを格納するリスト
rank = [0 for i in range(n+1)]

#xの根を発見する
#発見するだけでなくxと通過したノードを根の直下に配置する
def find(x):
    #自分の親が自分なら根
    if x==par[x]:
        return x
    else:
        #違う場合は親の根を自分の親にする
        par[x]=find(par[x])
        return par[x]


#xとyが含まれる木を合併する
def unite(x,y):
    #xの根,yの根をrx,ryとする
    rx=find(x)
    ry=find(y)
    
    #根が同じならもともと同じ木なのでok
    if rx==ry:
        return
    
    #根が異なる場合はrankが大きい木に小さい木をくっつける（rankを増やさないため）
    if rank[rx]<rank[ry]:
        par[rx]=ry
    else:
        par[ry]=rx
    #rankが等しい気を合併した時のみrankが増える
    if rank[rx]==rank[ry]:
        rank[rx]+=1

#x,yが同じ木に含まれるかの判定
def some(x,y):
    return find(x)==find(y)

#union-find終わり

#入力x,yを同じグループに
for i in range(m):
    x,y,z=map(int,input().split())
    unite(x,y)

#すべてのノードを根の直下に配置
for i in range(1,n+1):
    find(i)

#木の数を数える(根の種類を数える)
ans=len(set(par))-1

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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

par = [i for i in range(n+1)]
rank = [0 for i in range(n+1)]

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

def unite(x,y):
    rx=find(x)
    ry=find(y)
    
    if rx==ry:
        return
    
    if rank[rx]<rank[ry]:
        par[rx]=ry
    else:
        par[ry]=rx
        
    if rank[rx]==rank[ry]:
        rank[rx]+=1

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

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

for i in range(1,n+1):
    find(i)
    
ans=len(set(par))-1

print(ans)

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,m = LI()
def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]

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

def union(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

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

xyz = [LI() for _ in range(m)]
for x,y,z in xyz:
    if root(x-1) != root(y-1):
        union(x-1,y-1)
f = defaultdict(lambda :0)
ans = 0
for i in range(n):
    if f[root(i)] == 0:
        ans += 1
        f[root(i)] = 1

print(ans)

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,m = LI()
def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]

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

def union(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

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

xyz = [LI() for _ in range(m)]
for x,y,z in xyz:
    if root(x-1) != root(y-1):
        union(x-1,y-1)
f = defaultdict(int)
for i in range(n):
    f[root(i)] = 1

ans = 0
for i,j in f.items():
    if j != 1:
        continue
    ans += 1
print(ans)

Submission status: Accepted

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

graph = [[] for _ in range(N+1)]
for i in range(M):
  X, Y, Z = map(int, input().split())
  graph[X].append(Y)
  graph[Y].append(X)

answer = 0
stack = []
seen = [0] * (N+1)

for i in range(1, N+1):
  if seen[i] == 0:
    answer += 1
    seen[i] = 1
    if len(graph[i]):
      stack.append(i)
      while stack:
        s = stack.pop()
        for g in graph[s]:
          if seen[g] == 0:
            stack.append(g)
            seen[g] = 1
print(answer)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    n,m=map(int, input().split())
    
    tree=[[] for _ in range(n)]
    for i in range(m):
        x,y,w = map(int,input().split())
        tree[x-1].append(y-1)
        tree[y-1].append(x-1)
    
    singles = [ i for i in range(n) if tree[i]==[]]
    
    visited=[False]*n
    for i in singles:
        visited[i] = True
    ans=len(singles)
    
    from collections import deque
    while False in visited:
        ans+=1
        start = visited.index(False)
        visited[start]=True
        q=deque([(start,togo) for togo in tree[start]])
        while q:
            parent,x = q.pop()
            visited[x]=True
            for y in tree[x]:
                if not visited[y]:
                    q.append((x,y))
    #         print(parent,x,q)
    #     print(visited,ans)
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

singles = [ i for i in range(n) if tree[i]==[]]

visited=[False]*n
for i in singles:
    visited[i] = True
ans=len(singles)

from collections import deque
while False in visited:
    ans+=1
    start = visited.index(False)
    visited[start]=True
    q=deque([(start,togo) for togo in tree[start]])
    while q:
        parent,x = q.pop()
        visited[x]=True
        for y in tree[x]:
            if not visited[y]:
                q.append((x,y))
#         print(parent,x,q)
#     print(visited,ans)
print(ans)

Submission status: Accepted

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

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

        return self.p[x]

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

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

        if u == v: return

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

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

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

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

x=[]
y=[]
z=[]
for i in range(m):
    p,q,r=map(int,input().split())
    x.append(p-1)
    y.append(q-1)
    z.append(r)

cost=0

uf=Uf(n)
for i in range(m):
    uf.unite(x[i],y[i])
cnt=set()
for i in range(n):
    tmp=uf.root(i)
    cnt.add(tmp)

print(len(cnt))

Submission status: Accepted

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

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

Submission status: Accepted

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

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

check = [False]*n

cnt=0
import queue
q=queue.Queue()
for i in range(n):
	if check[i]:
		continue
	cnt+=1
	check[i]=True
	q.put(i)

	while not q.empty():
		now=q.get()
		for ne in g[now]:
			if check[ne]:
				continue
			check[ne]=True
			q.put(ne)

print(cnt)

Submission status: Accepted

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

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

check = [False]*n

cnt=0
import queue
for i in range(n):
	if check[i]:
		continue
	cnt+=1
	check[i]=True
	q=queue.Queue()
	q.put(i)

	while not q.empty():
		now=q.get()
		for ne in g[now]:
			if check[ne]:
				continue
			check[ne]=True
			q.put(ne)

print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect, string
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**7)
inf = float('inf')
mod = 10**9+7
ans = inf ;count = 0 ;pro = 1

class UnionFind:
    __slots__ = ['id','sz']

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

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

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

    def union(self, x, y):
        s1, s2 = self.root(x), self.root(y)
        if s1 != s2:
            if self.id[s1] <= self.id[s2]:
                self.id[s1] += self.id[s2]
                self.id[s2] = s1
            else:
                self.id[s2] += self.id[s1]
                self.id[s1] = s2
            self.sz-=1
            return True
        return False


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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500*500)
N, M = map(int,input().split())
Q = [list(map(int,input().split())) for _ in range(M)]
C = [[] for _ in range(N+1)]
count = 0
for q in Q:
    X = q[0]
    Y = q[1]
    C[X].append(Y)
    C[Y].append(X)

flag = [-1]*(N+1)
flag[1] = 0
def dfs(s):
    global count
    for c in C[s]:
        flag[s] = 0
        if flag[c] == -1:
            flag[c] = 0
            count += 1
            dfs(c)

for i in range(1,N+1):
    dfs(i)
print(N-count)

Submission status: Accepted

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

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

    def Count(self,x):
        return -self.root[self.Find_Root(x)]

uf=UnionFind(n)
for _ in range(m):
    x,y,z=map(int,input().split())
    x-=1
    y-=1
    uf.Unite(x,y)
r=[0]*n
for i in range(n):
    r[i]=uf.Find_Root(i)
s=set(r)
print(len(s))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(m):
        x,y,z=map(int,input().split())
        x-=1; y-=1
        E[x].append(y)
        E[y].append(x)

    cnt=0
    col=[None]*n
    def dfs(v)->bool:
        if(col[v] is not None): return False
        Q=[v]
        col[v]=cnt
        while(Q):
            v=Q.pop()
            for nv in E[v]:
                if(col[nv] is not None): continue
                col[nv]=cnt
                Q.append(nv)
        return True

    for v in range(n):
        cnt+=dfs(v)

    print(cnt)
resolve()

Submission status: Accepted

Solution code:
from collections import deque

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

seen = [False] * n
ans = 0
for i in range(n):
    if not seen[i]:
        seen[i] = True
        node = deque(graph[i])
        while node:
            v = node.popleft()
            if seen[v]:
                continue
            seen[v] = True
            node.extend(graph[v])
        ans += 1

print(ans)

Submission status: Accepted

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

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

    def isSame(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.root[x] = y
        else:
            self.root[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


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

for i in range(1, n + 1):
    uf.find(i)

n_tree = set(uf.root)
ans = len(n_tree) - 1
print(ans)

Submission status: Accepted

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

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

        return self.p[x]

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

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

        if u == v: return

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

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

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

def main():
    n,m = map(int,input().split())
    ls = [[int(x) for x in input().split()] for _ in range(m)]
    uni = Uf(n+1)

    for i in range(m):
        a,b,c = ls[i]
        uni.unite(a,b)
    ans = 0
    for i in range(1,n+1):
        if i == uni.root(i):
            ans +=1
        else:
            pass
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
    
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])

def find(x): # 木の根を求める
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
        
def unite(x,y): # xとyの属する集合を併合
    x=find(x)
    y=find(y)
    if x==y:return
    if rank[x]<rank[y]:
        par[x]=y
    else:
        par[y]=x
        if rank[x]==rank[y]:
            rank[x]+=1

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

def main():
    n,m = map(int,input().split()) 
    global par,rank
    par=[i for i in range(n)]  # 親
    rank=[0 for _ in range(n)] # 木の深さ
    for _ in range(m):
        a,b,z = map(int,input().split())
        unite(a-1,b-1)
    dic=defaultdict(int)
    ans=0
    for i in range(n):
        if dic[find(i)]==0:
            ans+=1
            dic[find(i)]=1
    print(ans)
        
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def search(x, y):
    while root[x] != x: x = root[x]
    while root[y] != y: y = root[y]
    return x, y

def rebuild(x, y, r):
    while root[x] != r: x, root[x] = root[x], r
    while root[y] != r: y, root[y] = root[y], r
        
N, M = map(int, input().split())

root = {i:i for i in range(1, N+1)}
size = {i:1 for i in range(1, N+1)}
ans = 0

for i in range(M):
    x, y, z = map(int, input().split())
    
    x_r, y_r = search(x, y)

    if x_r == y_r: continue
    
    root[y_r] = x_r
    size[x_r] += size[y_r]
    if size[x_r] > 10: rebuild(x, y, x_r)
    ans += 1

print(N-ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


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)

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

print(sum(uf.root(j) for j in range(n)))

Submission status: Accepted

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

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 isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)
    
    def count(self, x):
        return -self.root[self.find_root(x)]

uf = UnionFind(N)
for _ in range(M):
    x,y,z = map(int, input().split())
    uf.unite(x, y)
    
L = [0]*(N+1)
for i in range(1, N+1):
    r = uf.find_root(i)
    if L[r] == 0:
        L[r] = 1
        
print(sum(L))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
XYZ=[]
for i in range(M):
    X,Y,Z=map(int,input().split())
    XYZ.append([X,Y])

def find_root(root,x):
    y = root[x]
    if x == y:
        return x
    z = find_root(root,y)
    root[x] = z
    return z
 
def merge(root,size,x,y):
    x = find_root(root,x)
    y = find_root(root,y)
    if x == y:
        return
    sx,sy = size[x],size[y]
    if sx < sy:
        sx,sy = sy,sx
        x,y = y,x
    root[y] = x
    size[x] += sy
    
def UF_make(graph,n):
    Root=list(range(n+1))
    Size=[1] * (n+1)
    for i in range(len(graph)):
        merge(Root,Size,graph[i][0],graph[i][1])
    for i in range(n+1):
        Root[i] = find_root(Root,i)
    Root.pop(0)
    return Root

L=UF_make(XYZ,N)
print(len(set(L)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
n, m = [int(i) for i in sys.stdin.readline().split()]
parent = [i for i in range(n)]

def unite(a, b):
    root_a = find_root(a)
    parent[a] = root_a
    root_b = find_root(b)
    parent[b] = root_b
    if root_a != root_b:
        parent[root_b] = root_a

def find_root(a):
    ls = []
    while parent[a] != a:
        ls.append(a)
        a = parent[a]
    for l in ls:
        parent[l] = a
    return a


for i in range(m):
    x, y, z = [int(i) for i in sys.stdin.readline().split()]
    x -= 1
    y -= 1
    unite(x, y)

_set = set()
for i in range(n):
    _set.add(find_root(i))
print(len(_set))

Submission status: Accepted

Solution code:
import collections
class UnionFind:
    def __init__(self, max_size):
        self.parent = [i for i in range(max_size+1)]
        self.depth = [0 for _ in range(max_size+1)]
        self.cnt = [1 for i in range(max_size+1)]
    def find(self, x):
        deque = collections.deque()
        t = x
        while t != self.parent[t]:
            deque.append(t)
            t = self.parent[t]
        while deque:
            tmp = deque.pop()
            self.parent[tmp] = t
        return t
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.depth[x] < self.depth[y]:
            self.parent[x] = y
            self.cnt[y] += self.cnt[x]
        else:
            self.parent[y] = x
            self.cnt[x] += self.cnt[y]
            if self.depth[x] == self.depth[y]:
                self.depth[x] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def size(self, x):
        return self.cnt[self.find(x)]
n, m = map(int, input().split())
utree = UnionFind(n+10)
for _ in range(m):
    x, y, z = map(int, input().split())
    utree.unite(x, y)
s = {utree.find(i) for i in range(1, n+1)}
print(len(s))

Submission status: Accepted

Solution code:
import collections


class UnionFind:
    def __init__(self, max_size):
        self.parent = [i for i in range(max_size+1)]
        self.depth = [0 for _ in range(max_size+1)]
        self.cnt = [1 for i in range(max_size+1)]
    # 菲再起にしたい　Whileでスタックに突っこみながら見てスタックの中身全部に代入
    '''
    # 実はこっちのほうが速かったなんで？
    def find(self, x):
        t = x
        while t!=self.parent[t]:
            t = self.parent[t]
        self.parent[x]=t
        return t
    '''

    def find(self, x):
        de = collections.deque()
        t = x
        while t != self.parent[t]:
            de.append(t)
            t = self.parent[t]
        while de:
            tmp = de.pop()
            self.parent[tmp] = t
        return t

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.depth[x] < self.depth[y]:
            self.parent[x] = y
            self.cnt[y] += self.cnt[x]
        else:
            self.parent[y] = x
            self.cnt[x] += self.cnt[y]
            if self.depth[x] == self.depth[y]:
                self.depth[x] += 1

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

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


n, m = map(int, input().split())
utree = UnionFind(n+10)
for _ in range(m):
    x, y, z = map(int, input().split())
    utree.unite(x, y)
s = {utree.find(i) for i in range(1, n+1)}
print(len(s))

Submission status: Accepted

Solution code:
import collections


class UnionFind:
    def __init__(self, max_size):
        self.parent = [i for i in range(max_size+1)]
        self.depth = [0 for _ in range(max_size+1)]
        self.cnt = [1 for i in range(max_size+1)]
    # 菲再起にしたい　Whileでスタックに突っこみながら見てスタックの中身全部に代入
    '''
    # 実はこっちのほうが速かったなんで？
    def find(self, x):
        t = x
        while t!=self.parent[t]:
            t = self.parent[t]
        self.parent[x]=t
        return t
    '''

    def find(self, x):
        deque = collections.deque()
        t = x
        while t != self.parent[t]:
            deque.append(t)
            t = self.parent[t]
        while deque:
            tmp = deque.pop()
            self.parent[tmp] = t
        return t

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.depth[x] < self.depth[y]:
            self.parent[x] = y
            self.cnt[y] += self.cnt[x]
        else:
            self.parent[y] = x
            self.cnt[x] += self.cnt[y]
            if self.depth[x] == self.depth[y]:
                self.depth[x] += 1

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

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


n, m = map(int, input().split())
utree = UnionFind(n+10)
for _ in range(m):
    x, y, z = map(int, input().split())
    utree.unite(x, y)
s = {utree.find(i) for i in range(1, n+1)}
print(len(s))

Submission status: Accepted

Solution code:
import collections
class UnionFind:
    def __init__(self, max_size):
        self.parent = [i for i in range(max_size+1)]
        self.depth = [0 for _ in range(max_size+1)]
        self.cnt = [1 for i in range(max_size+1)]
    # 菲再起にしたい　Whileでスタックに突っこみながら見てスタックの中身全部に代入
    def find(self, x):
        de = collections.deque()
        t = x
        while t!=self.parent[t]:
            de.append(t)
            t = self.parent[t]
        while de:
            tmp = de.pop()
            self.parent[tmp] = t
        return t
    
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        elif self.depth[x]<self.depth[y]:
            self.parent[x] = y
            self.cnt[y] += self.cnt[x]
        else:
            self.parent[y] = x
            self.cnt[x]+=self.cnt[y]
            if self.depth[x]==self.depth[y]:
                self.depth[x]+=1
    def same(self, x, y):
        return self.find(x)==self.find(y)
    def size(self,x):
        return self.cnt[self.find(x)]

n,m = map(int,input().split())
utree = UnionFind(n+10)
for _ in range(m):
    x,y,z = map(int,input().split())
    utree.unite(x,y)
s = {utree.find(i) for i in range(1,n+1)}
print(len(s))