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:
# -*- coding utf-8 -*-

MOD = 10 ** 9 + 7

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

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())

uf = UnionFind(n)
for x, y, z in xyz_m:
    uf.union(x - 1, y - 1)

print(uf.group_count())

Submission status: Accepted

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


class DisjointSet():
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

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

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

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def count_groups(self):
        return len([i for i, x in enumerate(self.parent) if i == x])


d = DisjointSet(N)
for i in range(M):
    xi, yi, zi = map(int, input().split())
    d.unite(xi - 1, yi - 1)
print(d.count_groups())

Submission status: Accepted

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

    # return root of x
    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
        self._size[x] = self._size[y] = self._size[x] + self._size[y]
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

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


def main():
    n, m = map(int, input().split())
    u = UnionFind(n)
    for _ in range(m):
        x, y, z = map(int, input().split())
        u.unite(x, y)
    s = set()
    for i in range(1, n+1):
        s.add(u.find(i))
    print(len(s))
    
    
main()

Submission status: Accepted

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

p=[i for i in range(n)]
r=[0 for i in range(n)]

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

def unite(x,y):

  x = find(x)
  y = find(y)
  if x==y:
    return

  if r[x]<r[y]:
    p[x]=y
  else:
    p[y]=x
    if r[x]==r[y]:
      r[x] += 1

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

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

s = set()
for i in range(n):
  s.add(find(i))

print(len(s))

Submission status: Accepted

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

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

    def size(self, index):
        return -1 * self.parents[self.root(index)]

    def add(self, A, B):
        A = self.root(A)
        B = self.root(B)
        if (A == B):
            return
        if (self.size(A) < self.size(B)):
            A, B = B, A
        self.parents[A] += self.parents[B]
        self.parents[B] = A
N, M = [int(x) for x in input().split()]
XYZ = [[int(x) - 1 for x in input().split()] for _ in range(M)]
uf = UnionFind(N)
for x, y, z in XYZ:
    uf.add(x, y)
s = set()
for i in range(N):
    s.add(uf.root(i))
print(len(s))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
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 solve(N: int, M: int, X: "List[int]", Y: "List[int]", Z: "List[int]"):
    uf = UnionFind(N)
    
    for i in range(M):
        uf.union(X[i]-1,Y[i]-1)
    
    print(uf.group_count())
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    X = [int()] * (M)  # type: "List[int]"
    Y = [int()] * (M)  # type: "List[int]"
    Z = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        X[i] = int(next(tokens))
        Y[i] = int(next(tokens))
        Z[i] = int(next(tokens))
    solve(N, M, X, Y, Z)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, M = map(int, readline().split())
graph = [[] for _ in range(N + 1)]
check = []

for i in readlines():
    x, y, z = map(int, i.split())
    graph[x].append(y)
    graph[y].append(x)
    check.extend([x, y])

check = set(check)
answer = N - len(check)
while check:
    queue = deque([check.pop()])
    while queue:
        v = queue.popleft()
        for j in graph[v]:
            if j in check:
                queue.append(j)
                check.remove(j)
    answer += 1

print(answer)

Submission status: Accepted

Solution code:
class Unionfind():
    def __init__(self,N,weighted=False):
        self.root = list(range(N))
        self.depth = [1 for _ in range(N)]
        self.weighted = False
        if weighted:
            self.weighted = True
            self.weight = [0 for _ in range(N)]
    def find(self,x):
        if self.root[x] == x:
            return x
        else:
            r = self.find(self.root[x])
            if self.weighted:
                self.weight[x] += self.weight[self.root[x]]
            self.root[x] = r
            return r
    def unite(self,a,b,x=0):
        A = self.find(a)
        B = self.find(b)
        if self.weighted:
            wa = self.weight[a]
            wb = self.weight[b]
        if A == B:
            return
        elif self.depth[A] > self.depth[B]:
            self.root[B] = A
            self.depth[A] += self.depth[B]
            if self.weighted:
                self.weight[B] = wa -wb + d
        else:
            self.root[A] = B
            self.depth[B] += self.depth[A]
            if self.weighted:
                self.weight[A] = wb - wa - d
N,M = map(int,input().split())
uf = Unionfind(N)
for _ in range(M):
    x,y,_ = map(int,input().split())
    uf.unite(x-1,y-1)
root_set = set()
for i in range(N):
    root_set.add(uf.find(i))
print(len(root_set))

Submission status: Accepted

Solution code:
import sys
from collections import deque
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, M = map(int, readline().split())
graph = [[] for _ in range(N + 1)]
check = set([])

for i in readlines():
    x, y, z = map(int, i.split())
    graph[x].append(y)
    graph[y].append(x)
    check.add(x)
    check.add(y)

answer = N - len(check)
while check:
    queue = deque([check.pop()])
    while queue:
        v = queue.popleft()
        for j in graph[v]:
            if j in check:
                queue.append(j)
                check.remove(j)
    answer += 1

print(answer)

Submission status: Accepted

Solution code:
import sys
from collections import deque
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, M = map(int, readline().split())
graph = [[] for _ in range(N + 1)]

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

cnt = 0
checked = set([])

for i in graph:
    if i:
        if i[0] not in checked:
            queue = deque([i[0]])
            while queue:
                v = queue.popleft()
                for j in graph[v]:
                    if j not in checked:
                        queue.append(j)
                        checked.add(j)
            cnt += 1


print(N - len(checked) + cnt)

Submission status: Accepted

Solution code:


import sys
def input():
	return sys.stdin.readline().strip()

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


class Union_Find():
	def __init__(self, n):
		self.union = [i for i in range(n)]
		self.level = [0 for i in range(n)]
		self.num = n

	def root(self, i, mode=0):
		keiro = [i]
		ans = i
		while ans != self.union[ans]:
			ans = self.union[ans]
			keiro.append(ans)
		if mode == 0:
			return ans
		else:
			return ans, keiro

	def unite(self, i, j):
		root_i, list_i = self.root(i, 1)
		root_j, list_j = self.root(j, 1)
		if root_i != root_j:
			self.num -= 1
			if self.level[root_i] < self.level[root_j]:
				self.level[root_j] = max(self.level[root_i] + 1, self.level[root_j])
				for node in list_i:
					self.union[node] = root_j
			else:
				self.level[root_i] = max(self.level[root_j] + 1, self.level[root_i])
				for node in list_j:
					self.union[node] = root_i

union = Union_Find(N)

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

print(union.num)

Submission status: Accepted

Solution code:
class UF:
    def __init__(self, N):
        self.uf = [-1]*N
        self.n = N

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

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

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x==y: return
        if self.size(x) > self.size(y): x, y = y, x
        self.uf[y] += self.uf[x]
        self.uf[x] = y
        self.n -= 1

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

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 i in range(M):
    x, y, z = map(int,input().split())
    x-=1; y-=1
    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())
XYZ = [list(map(int,input().split())) for _ in range(M)]
uf = UnionFind(N)
for i in range(M):
  uf.union(XYZ[i][0]-1,XYZ[i][1]-1)
#print(uf.parents)
#print(uf)
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())
XYZ = [list(map(int,input().split())) for _ in range(M)]
uf = UnionFind(N)
for i in range(M):
  uf.union(XYZ[i][0]-1,XYZ[i][1]-1)
#print(uf.parents)
#print(uf)
print(uf.group_count())

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
d = {}
for _ in range(m):
    x, y, _ = map(int, input().split())
    if x in d:
        d[x].append(y)
    else:
        d[x] = [y]
    if y in d:
        d[y].append(x)
    else:
        d[y] = [x]
s = {i for i in range(1, n+1)}
a = 0
ts = set()
while s:
    cur = [s.pop()]
    ts = set(cur)
    a += 1
    while cur:
        nextp= []
        for i in cur:
            for j in d.get(i, []):
                if j not in ts:
                    ts.add(j)
                    nextp.append(j)
        cur = nextp
    s -= ts
print(a)

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 = [int(x) for x in input().split()]
uf = UnionFind(N)
for _ in range(M):
    x,y,z = [int(x) for x in input().split()]
    uf.union(x-1,y-1)
ans = 0
print(uf.group_count())

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
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())

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

  print(len(uf.roots()))
solve()

Submission status: Accepted

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

    def find(self, x):
        #要素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が属するグループと要素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):
        # 要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def same(self, x, y):
        # 要素x, yが同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)

    def members(self, x):
        # 要素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())
#############################################################

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = []

N, M = LI()
xyz = [LI() for _ in range(M)]
cou = int(0)
uf = UnionFind(N)

for i in range(M):
    if not uf.same(xyz[i][0]-1, xyz[i][1]-1):
        uf.union(xyz[i][0]-1, xyz[i][1]-1)

cou = uf.group_count()
ans = cou

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 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())
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())

Submission status: Accepted

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

def dfs(x, g, vis):
    if vis[x]:
        return
    vis[x] = 1
    for y in g[x]:
        dfs(y, g, vis)

def main():
    N, M = map(int, input().split())
    g = [[] for _ in range(N)]
    for i in range(M):
        X, Y, Z = map(int, input().split())
        X -= 1
        Y -= 1
        g[X].append(Y)
        g[Y].append(X)
    vis = [0] * N

    ans = 0
    for i in range(N):
        if vis[i] == 0:
            dfs(i, g, vis)
            ans += 1
    print(ans)

main()

Submission status: Accepted

Solution code:
class UnionFind :
    def __init__(self, size) :
        """
        Parameters
        ---
        size : int
            頂点数
        """
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        """
        親のインデックスの取得

        Parameters
        ---
        index : int
            取得する頂点のインデックス

        Returns
        ---
        rootIndex : int
            指定した頂点の根のインデックス
        """
        if self.parent[index] == index :  # 根の場合
            return index
        rootIndex = self.root(self.parent[index])  # 葉の場合親の根を取得
        self.parent[index] = rootIndex  # 親の付け直し
        return rootIndex

    def union(self, index1, index2) :  # 結合
        """
        木の結合

        Parameters
        ---
        index1 : int
        index2 : int
            結合する頂点のインデックス
        """
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  # 連結されている場合
            return

        self.component -= 1  # 連結成分を減らす

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  # root2に結合
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  # root1に結合
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        """
        同じ木に属するかを判定する

        Parameters
        ---
        index1 : int
        index2 : int

        Returns
        ---
        boolean
        """
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        """
        指定した頂点の属する木の大きさを取得する
        """
        return self.size[self.root(index)]

    def getComponent(self) :
        """
        連結成分数を取得する
        """
        return self.component


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

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

ans = tree.getComponent()
print(ans)

Submission status: Accepted

Solution code:
def main():

    N, M = map(int, input().split())
    parent = [i for i in range(N)]
    level = [1 for _ in range(N)]

    def find(i):
        if parent[i] != i:
            parent[i] = find(parent[i])
        return parent[i]

    def union(i, j):
        pi, pj = find(i), find(j)
        if pi != pj:
            if level[pi] < level[pj]:
                parent[pi] = pj
                level[pj] = max(1+level[pi], level[pj])
            else:
                parent[pj] = pi
                level[pi] = max(1+level[pj], level[pi])

    for _ in range(M):
        i, j, z = map(int, input().split())
        union(i-1, j-1)

    # print(parent)
    for i in range(N): find(i)
    # print(parent)

    ans = len(set(parent))
    return ans

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,n):
        self.par=[i for i in range(n+1)]
        self.rank=[0]*(n+1)
        self.size=[1]*(n+1)
        self.num=1
        
    def findroot(self,x):
        if self.par[x]==x:
            return x
        else:
            self.par[x]=self.findroot(self.par[x])
            return self.par[x]

    def unite(self,x,y):
        x=self.findroot(x)
        y=self.findroot(y)
        if x!=y:
            self.num+=1
        if self.rank[x]==self.rank[y]:
            self.rank[x]+=1
        if self.rank[x]<self.rank[y]:
            self.par[x]=y
            self.size[y]+=self.size[x]
        else:
            self.par[y]=x
            self.size[x]+=self.size[y]

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

print(n-G.num+1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,m = map(int,input().split())
f = [False for _ in range(n)]
a = [[] for _ in range(n)]
res = 0

def dfs(k):
    f[k] = True
    for g in a[k]:
        if not f[g]:
            dfs(g)

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

for i in range(n):
    if not f[i]:
        res += 1
        dfs(i)
print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7



class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
        self.size = n

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


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


    def union(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
        self.size -= 1


n, m = LI()
U = UnionFind(n)
for i in range(m):
    x, y, z = LI()
    U.union(x - 1, y - 1)


print(U.size)