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, 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())
XYZs = [list(map(lambda x: int(x)-1, input().split())) for _ in range(M)]

uf = UnionFind(N)

for XYZ in XYZs:
    uf.union(XYZ[0], XYZ[1])

print(uf.group_count())

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict


def input():
    return sys.stdin.readline().rstrip()


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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


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)

    print(uf.group_count())



if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

def uf_find(x):
    while uf[x]!=x:
        x=uf[x]
    return x

for i in range(m):
    x,y,z=map(int,input().split())
    a,b=uf_find(x),uf_find(y)
    if a>b:
        a,b=b,a
    uf[b]=a

c=set()
for i in range(1,n+1):
    c.add(uf_find(i))
print(len(c))

Submission status: Accepted

Solution code:
import sys
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	#a = int(input())
	n, m = tin()
	#s = input()
	is_open=[-1]*n
	graph = [[] for _ in range(n)]
	for _ in range(m):
		x, y, _ = tin()
		graph[x-1].append(y-1)
		graph[y-1].append(x-1)
		
	ret = 0
	for i in range(n):
		if is_open[i] > 0:
			continue
		ret += 1
		q=collections.deque()
		q.append(i)
		is_open[i] = 1
		while q:
			pos = q.pop()
			for t in graph[pos]:
				if is_open[t] > 0:
					continue
				is_open[t] = 1
				q.append(t)
	return ret
		
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

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


class UF:
    def __init__(self, n):
        self.n = n
        self.g = list(range(n))
        self.vertices = list(range(n))

    def union(self, i0, i1):
        g0, g1 = self.find(i0), self.find(i1)
        g0, g1 = min(g0, g1), max(g0, g1)
        self.g[g1] = g0

    def find(self, i):
        path = []
        while self.g[i] != i:
            path.append(i)
            i = self.g[i]

        for j in path:
            self.g[j] = i

        return i

uf = UF(n)

for x, y in xy:
    uf.union(x, y)

g = set()
for x in range(n):
    g.add(uf.find(x))

answer = len(g)
print(answer)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.components = n

    def root(self, x):
        if self.p[x] == x:
            return x
        else:
            self.p[x] = self.root(self.p[x])
            return self.p[x]
    
    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            self.p[x] = y
            self.components -= 1
    
    def same(self, x,y):
        return (self.root(x) == self.root(y))
N, M = map(int,input().split())

UF = UnionFind(N)

for _ in range(M):
    X, Y, Z = map(int,input().split())
    X, Y = X-1, Y-1
    UF.unite(X,Y)

print(UF.components)

Submission status: Accepted

Solution code:
import networkx as X
n,m=map(int,input().split())
g=X.Graph()
for i in range(n):g.add_node(i+1)
for i in range(m):x,y,z=map(int,input().split());g.add_edge(x,y)
print(X.number_connected_components(g))

Submission status: Accepted

Solution code:

class UnionFind:
    def __init__(self, n):
        self.par = list(range(n))
        self.rank = [0] * n
        self.size = [1] * n

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

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

        if x == y:
            return

        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        elif self.rank[x] < self.rank[y]:
            x, y = y, x

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

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

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


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

tree = UnionFind(N)
for x, y, z in X:
    tree.unite(x - 1, y - 1)

# Update
for x in range(N):
    tree.find(x)

print(len(set(tree.par)))

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())
uf = UnionFind(N)
for _ in range(M):
    X, Y, Z = map(lambda x: int(x)-1, input().split())
    uf.union(X, Y)
print(uf.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 size(self, x):
        return -self.parents[self.find(x)]

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

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

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

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

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

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

N, M = map(int, input().split())
uf = UnionFind(N)
for _ in range(M):
    X, Y, Z = map(lambda x: int(x)-1, input().split())
    uf.union(X, Y)
print(len(uf.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

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

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

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

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

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

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

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

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

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

N, M = map(int, input().split())
uf = UnionFind(N)
for _ in range(M):
    X, Y, Z = map(lambda x: int(x)-1, input().split())
    uf.union(X, Y)
ans = [uf.find(x) for x in uf.roots()]
print(len(set(ans)))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

class UnionFind():
    def __init__(self, n):
        self.parents = list(range(n))
        self.size = [1] * 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:
            if self.size[x] < self.size[y]:
                x,y = y,x
            self.parents[y] = x
            self.size[x] += self.size[y]

def main():
    N, M = map(int, input().split())
    uf = UnionFind(N)
    for _ in range(M):
        X, Y, Z = map(lambda x: int(x)-1, input().split())
        uf.union(X, Y)
    # print(len(set(uf.parents)))
    ans = [uf.find(x) for x in uf.parents]
    print(len(set(ans)))

if __name__ == "__main__":
    main()

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())
uf = UnionFind(N)

for _ in range(M):
  X, Y, Z = map(int, input().split())
  uf.union(X-1, Y-1)

print(uf.group_count())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
n,m = map(int, input().split())

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

ans = [-1]*n
def hoge(parent, pos):
  for i in rel[pos]:
    if ans[i] >= 0:
      continue
    ans[i] = pos
    hoge(pos, i)
  return

cnt = 0
for i in range(n):
  if ans[i] < 0:
    hoge(0, i)
    cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter


def read():
    N, M = map(int, input().strip().split())
    XYZ = []
    for i in range(M):
        x, y, z = map(int, input().strip().split())
        XYZ.append((x, y, z))
    return N, M, XYZ


class UnionFind():
    """Union-Find木の実装
    """

    def __init__(self, n):
        self.n = n
        self.parent = [x for x in range(n)]

    def find(self, x):
        """要素xが所属するグループを返す
        """
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def union(self, x, y):
        """要素x, yがそれぞれ所属するグループを併合する
        """
        x = self.find(x)
        y = self.find(y)
        if x > y:
            x, y = y, x
        self.parent[y] = x

    def parents(self):
        return [self.find(x) for x in range(self.n)]


def solve(N, M, XYZ):
    uf = UnionFind(N)
    for x, y, z in XYZ:
        uf.union(x-1, y-1)
    C = Counter(uf.parents())
    return len(C)


if __name__ == '__main__':
    inputs = read()
    print(solve(*inputs))

Submission status: Accepted

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

card = [[] for _ in range(n)]

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

checked = [False] * n

count = 0
for i in range(n):
    if checked[i]:
        continue
    count += 1
    q = [i]
    while q:
        j = q.pop()
        checked[j] = True
        for k in card[j]:
            if not checked[k]:
                q.append(k)
print (count)

Submission status: Accepted

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

card = [[] for _ in range(n)]

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

checked = [False] * n

count = 0
import queue
q = queue.Queue()
for i in range(n):
    if checked[i]:
        continue
    count += 1
    q.put(i)
    while not q.empty():
        j = q.get()
        checked[j] = True
        for k in card[j]:
            if not checked[k]:
                q.put(k)

print (count)

Submission status: Accepted

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque


N,M=list(map(int,input().split()))
graph=[[] for _ in range(N+1)]
for _ in range(M):
    a,b,c=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
    
#seen[i]は、頂点iを訪問済みの場合はTrue、未訪問の場合はFalse
seen=[False]*(N+1)


count=0

for i in range(1,N+1):
    if seen[i]==False:
        seen[i]=True
        S=deque([i])
        
        while S:
            v=S.popleft()
            #訪問済みの頂点をTrueにする
            for i in graph[v]:
                if seen[i]==False:
                    seen[i]=True
                    S.append(i)
        count+=1

print(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 unite(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 isSame(self, x, y):
        return self.find(x) == self.find(y)

def solve():
    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.unite(x,y)
    
    st = set()

    for i in range(N):
        st.add(uf.find(i))
    
    print(len(st))
    
if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

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

    if x == y:
      return

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

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

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

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

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

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

  def num_members(self,x):
    return abs(self.parents[self.find(x)])

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

N, M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
  a,b,c = map(int, input().split())
  uf.union(a-1,b-1)

print(uf.num_roots())

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(M):
  a,b,c = map(int, input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)

from collections import deque

ans = 0
visited = [False]*N
d = deque()
for i in range(N):
  if visited[i]==False:
    visited[i]=True
    d.append(i)
    while len(d)>0:
      v = d.popleft()
      for w in edge[v]:
        if visited[w]==False:
          visited[w]=True
          d.append(w)
    ans += 1
print(ans)

Submission status: Accepted

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

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

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

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

    if x == y:
      return

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

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

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

uf = UnionFind(N)

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

Submission status: Accepted

Solution code:
def find(x):
    while x!=T[x][0]:
        x = T[x][0]
    return x
def union(x,y):
    ax = find(x)
    ay = find(y)
    if T[ax][1]>T[ay][1]:
        T[ay][0] = ax
    elif T[ax][1]==T[ay][1]:
        T[ay][0] = ax
        T[ax][1] += 1
    else:
        T[ax][0] = ay
N,M = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(M)]
T = {i:[i,1] for i in range(1,N+1)}
for j in range(M):
    x,y = A[j][0],A[j][1]
    union(x,y)
B = [0 for _ in range(N+1)]
for i in range(1,N+1):
    B[i] = find(i)
C = {}
for i in range(1,N+1):
    b = B[i]
    if b not in C:
        C[b] = 0
    C[b] += 1
print(len(C))

Submission status: Accepted

Solution code:
N, M, *X = map(int, open(0).read().split())


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

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

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

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

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

    def num_union(self):
        return self.u


u = UnionFind(N)
for x, y, z in zip(*[iter(X)]*3):
    u.unite(x-1, y-1)
print(u.num_union())

Submission status: Accepted

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

par = [0] * n
rank = [0] * n

#初期化
for i in range(n):
    par[i] = i
    rank[i] = 0

#判定(一番上野根を求める)
def find(x):
    if par[x] == 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
    elif rank[rx] > rank[ry]:
        par[ry] = rx
    else:
        par[ry] = x
        rank[rx] += 1
        
for i in range(m):
    x,y,z = map(int, input().split())
    
    unite(x-1,y-1)
    
from collections import Counter
c = [find(i) for i in range(n)]

print(len(Counter(c)))

Submission status: Accepted

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
#https://note.nkmk.me/python-union-find/

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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
n,m=MI()
u=UnionFind(n)
for i in range(m):
    a,b,c=MI()
    u.union(a-1,b-1)
print(u.group_count())

Submission status: Accepted

Solution code:
# E - 1 or 2
from typing import Set


class UnionFind:
    """Union-Find: O(α(N))"""

    __slots__ = ["_data_size", "_first_idx", "_parents"]

    def __init__(self, data_size: int, is_zero_origin: bool = True) -> None:
        self._data_size = data_size
        self._first_idx = 0 if is_zero_origin else 1
        self._parents = [-1] * (data_size + self._first_idx)

    def __getitem__(self, x: int) -> int:
        """Find the group (root) of vertex x."""
        if self._parents[x] < 0:
            return x
        self._parents[x] = self[self._parents[x]]
        return self._parents[x]

    def __len__(self) -> int:
        """Count the number of groups (roots)."""
        return len(self.groups)

    @property
    def groups(self) -> Set[int]:
        """Return the set of groups (roots)."""
        return {
            self[x] for x in range(self._first_idx, self._data_size + self._first_idx)
        }

    def is_connected(self, x: int, y: int) -> bool:
        """Return whether two vertices x and y are connected or not."""
        return self[x] == self[y]

    def unite(self, x: int, y: int) -> None:
        """Unite two groups of vertices x and y."""
        x, y = self[x], self[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 main():
    N, _, *X = map(int, open(0).read().split())
    tree = UnionFind(N, is_zero_origin=False)
    for x, y, _ in zip(*[iter(X)] * 3):
        tree.unite(x, y)
    print(len(tree))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# E - 1 or 2
from typing import List


def main():
    def dfs(source: int) -> None:
        stack = [source]
        is_visited[source] = True
        while stack:
            u = stack.pop()
            for v in graph[u]:
                if is_visited[v]:
                    continue
                is_visited[v] = True
                stack.append(v)

    N, M, *X = map(int, open(0).read().split())
    graph: List[List[int]] = [[] for _ in range(N + 1)]
    for x, y, _ in zip(*[iter(X)] * 3):
        graph[x].append(y), graph[y].append(x)

    is_visited = [False] * (N + 1)
    res = 0
    for i in range(1, N + 1):
        if is_visited[i]:
            continue
        res += 1
        dfs(i)
    print(res)


if __name__ == "__main__":
    main()

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)

lst = []
visited = [0]*N
for i in range(N):
    if visited[i] == 1:continue
    temp = [i]
    lst1 = [i]
    visited[i] = 1
    while temp:
        p = temp.pop()
        for q in G[p]:
            if visited[q] == 0:
                visited[q] = 1
                lst1.append(q)
                temp.append(q)
    if lst1 != []:lst.append(lst1)
    
print(len(lst))