Problem:


Score : 500 points

Problem Statement

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

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

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

You know the following facts:

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

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

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

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

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

Constraints

All values in input are integers.

2 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq X_i < Y_i \leq N

1 \leq Z_i \leq 100

The pairs (X_i, Y_i) are distinct.

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3 1
1 2 1

Sample Output 1

2

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

Sample Input 2

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

Sample Output 2

2

Sample Input 3

100000 1
1 100000 100

Sample Output 3

99999



Sample input:
3 1
1 2 1


Sample output:
2

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

N, M = map(int, input().split())
L = [[int(v) - 1 for v in input().split()] for _ in range(M)]

class UnionFind:
    def __init__(self, n):
        self.data = [0] * N
        for i in range(N):
            self.data[i] = i
            
    def get_root(self, x):
        r = self.data[x]
        if r == x:
            return r
        p = self.get_root(r)
        self.data[x] = p
        return p
    
    def unite(self, x, y):
        rx = self.get_root(x)
        ry = self.get_root(y)
        
        if rx != ry:
            self.data[rx] = ry
            
    def same(self, x, y):
        return self.get_root(x) == self.get_root(y)
    
u = UnionFind(N)
for a, b, _ in L:
    u.unite(a, b)
    
s = set()
for i in range(N):
    s.add(u.get_root(i))

print(len(s))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
n , m = map(int,input().split())
g = [i for i in range(n)]
def find(x):
    if g[x] == x:
        return x
    g[x] = find(g[x])
    return g[x]
def union(x,y):
    x = find(x)
    y = find(y)
    if x!=y:
        g[x] = y

for i in range(m):
    xi,yi,zi = map(int,input().split())
    union(xi-1,yi-1)

ans = 0
for i in range(n):
    if find(i) == i:
        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.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)
ans=set()
for i in range(1,n+1):
    ans.add(uf.Find_Root(i))
print(len(ans))

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

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

e_list = [[] for i in range(N)]

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

from collections import deque

def BFS(vi,color,color_list):
    Q = deque([vi])
    color_list[vi]=color
    while len(Q)>0:
        v = Q.pop()
        for v1 in e_list[v]:
            if color_list[v1]==-1:
                color_list[v1]=color
                Q.appendleft(v1)

color_list = [-1]*N
color = 0

for i in range(N):
    if color_list[i]==-1:
        BFS(i,color,color_list)
        color+=1

print(color)

Submission status: Accepted

Solution code:

import collections
import itertools

def getint(): return int(input())
def getints(): return list(map(int, input().split()))

##* union-find
##pre union_find
class UnionFind:
    def __init__(self, node_count):
        self.group_count = node_count
        self.par = [-1] * node_count
    def root(self, x):
        if self.par[x] < 0:
            return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]
    def connect(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        self.group_count -= 1
        if self.par[y] < self.par[x]:
            x, y = y, x
        self.par[x] += self.par[y]
        self.par[y] = x
        return True
    def same(self, x, y):
        return self.root(x) == self.root(y)
    def get_size(self, x):
        return -self.par[self.root(x)]
    def get_groupsize(self):
        return self.group_count


n,m=getints()
uf = UnionFind(n)

for i in range(m):
    x,y,_=getints()
    uf.connect(x-1,y-1)

print(uf.group_count)

Submission status: Accepted

Solution code:
class UnionFind():
  def __init__(self, n):
    self.n = n
    # n+1なのはノード番号とリストのインデックスを一致させるため
    # root[x]<0ならそのノードが根かつその絶対値が木の要素数
    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)]

n, m = map(int, input().split())
UF = UnionFind(n)
for i in range(m):
  x, y, z = map(int, input().split())
  UF.Unite(x,y)

print(sum(x<0 for x in UF.root[1:]))

Submission status: Accepted

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

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

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            if self.par[x] > self.par[y]: # merge technique
                x, y = y, x
            self.par[x] += self.par[y]
            self.par[y] = x

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

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


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)

par = [uf.root(i) for i in range(n)]
print(len(set(par)))

Submission status: Accepted

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

def main():
    n,m = map(int,input().split())
    li = [list(map(int,input().split())) for _ in range(m)]

    roots = [[] for _ in range(n)]
    for x,y,z in li:
        roots[x-1].append(y-1)
        roots[y-1].append(x-1)

    ans = 0
    count = 0
    group = [-1] * n

    for i in range(n):
        if group[i] == -1:
            stack = [i]
            while stack:
                label = stack.pop(-1)
                for j in roots[label]:
                    if group[j] == -1:
                        group[j] = ans
                        stack.append(j)
            ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.N      = N
        self.depth  = [0] * N
        self.parent = list(range(N))

    def find(self, x):
        if x == self.parent[x]:
            return x
        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.depth[x] < self.depth[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.depth[x] == self.depth[y]:
                self.depth[x] += 1

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

    def is_root(self, x):
        return x == self.find(x)

    def num_tree(self):
        return sum([self.is_root(i) for i in range(self.N)])


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

T = UnionFind(N)

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

print(T.num_tree())

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.depth  = [0] * n
        self.parent = list(range(n))

    def find(self, x):
        if x == self.parent[x]:
            return x
        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.depth[x] < self.depth[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.depth[x] == self.depth[y]:
                self.depth[x] += 1

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

    def is_root(self, x):
        return x == self.find(x)


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

T = UnionFind(N)

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

print(sum([T.is_root(i) for i in range(N)]))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.depth  = [0] * n
        self.parent = list(range(n))

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

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.depth[x] < self.depth[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            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.depth[self.ind(x)]


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

T = UnionFind(N)

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

print(sum([1 for i in range(N) if T.find(i) == i]))

Submission status: Accepted

Solution code:
class UnionFind:

    def __init__(self, n):
        # parent[x] < 0 means x is root and abs(parent[x]) == size[x]
        self.parent, self.depth = [-1] * n, [0] * n

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

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

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

        if self.depth[x] > self.depth[y]:
            self.parent[x] += self.parent[y]
            self.parent[y] = x
        else:
            self.parent[y] += self.parent[x]
            self.parent[x] = y
            if self.depth[x] == self.depth[y]:
                self.depth[y] += 1

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

    def numTree(self):
        return sum([1 for p in self.parent if p < 0])


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

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

print(U.numTree())

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n=1):
        self.parent = [i for i in range(n)] #parent[a] = bはaの親がbであることを示す。最初はすべてroot。
        self.rank = [0] * (n+1) # 根の深さ
        self.cnt = 0


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


    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        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 groupsize(self):
        self.cnt = 0
        for i, x in enumerate(self.parent):
            if x == i:
                self.cnt += 1
        return self.cnt


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

for i in range(M):
    uf.unite(A[i][0]-1, A[i][1]-1)

print(uf.groupsize())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *

class UnionFind:

    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.height = [0 for i in range(n)]
        self.size = [1 for i in range(n)]

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

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

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.height[x] < self.height[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = self.par[x]
            self.size[x] += self.size[y]
            if self.height[x] == self.height[x]:
                self.height[x] += 1

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

N, M = map(int, input().split())
xyz = [None] * M
uf = UnionFind(2*N)
for i in range(M):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    if z % 2:
        uf.unite(x, y+N)
        uf.unite(x+N, y)
    else:
        uf.unite(x, y)
        uf.unite(x+N, y+N)
roots = set()
ans = 0
for i in range(N):
    p1, p2 = uf.find(i), uf.find(i+N)
    if p1 not in roots and p2 not in roots:
        roots.add(p1)
        ans += 1
print(ans)

Submission status: Accepted

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

    
    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 groupsize(self):
        self.cnt = 0
        for i, x in enumerate(self.par):
            if x == i:
                self.cnt += 1
        return self.cnt
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

N, M = map(int,input().split())
A = [list(map(int,input().split())) for i in range(M)]
uf = UnionFind(N)

for i in range(M):
    uf.union(A[i][0]-1, A[i][1]-1)

print(uf.groupsize())

Submission status: Accepted

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

    
    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 groupsize(self):
        self.cnt = 0
        for i, x in enumerate(self.par):
            if x == i:
                self.cnt += 1
        return self.cnt
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

N, M = map(int,input().split())
A = [list(map(int,input().split())) for i in range(M)]
uf = UnionFind(N)

for i in range(M):
    uf.union(A[i][0]-1, A[i][1]-1)

print(uf.groupsize())

Submission status: Accepted

Solution code:



import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
import math

N, M = list(map(int, input().split()))
XYZ = []
for i in range(M):
	XYZ.append(list(map(int, input().split())))

renketu = [dict() for i in range(N)]
for i in range(N):
	renketu[i]["iro"] = -1
	renketu[i]["eda"] = []
for i in range(M):
	renketu[XYZ[i][0] - 1]["eda"].append([XYZ[i][0], XYZ[i][1]])
	renketu[XYZ[i][1] - 1]["eda"].append([XYZ[i][1], XYZ[i][0]])

num = 0
for i in range(N):
	if renketu[i]['iro'] == -1:
		num += 1
		stack = [i]
		# print(rest, num)
		renketu[i]['iro'] = num
		while len(stack) > 0:
			node = stack.pop()
			for edge in renketu[node]["eda"]:
				if renketu[edge[1] - 1]["iro"] == -1:
					renketu[edge[1] - 1]["iro"] = num
					stack.append(edge[1] - 1)

print(num)

Submission status: Accepted

Solution code:
from collections import deque
import sys


sys.setrecursionlimit(100000)


class UnionFind:
    def __init__(self, size):
        self.parent = [-1] * (size + 1)  # 非負なら親ノード，負ならグループの要素数

    def root(self, x):  # root(x): xの根ノードを返す．
        if self.parent[x] < 0:
            return x
        elif self.parent[self.parent[x]] < 0:
            return self.parent[x]
        else:
            self.parent[x] = self.root(self.parent[x])  # xをxの根に直接つなぐ
            return self.parent[x]

    def merge(self, x, y):  # merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]:  # xの要素数がyの要素数より「小さい」とき入れ替える
            x, y = y, x
        self.parent[x] += self.parent[y]  # xの要素数を更新
        self.parent[y] = x  # yをxにつなぐ
        return True

    def issame(self, x, y):  # same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)

    def size(self, x):  # size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]

N,M = list(map(int, input().split(" ")))
uf = UnionFind(N)
for _ in range(M):
    x,y,_ = list(map(int, input().split(" ")))
    uf.merge(x,y)
anss = set()
for i in range(1,N+1):
    anss.add(uf.root(i))
print(len(anss))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
n,m=map(int,input().split())
class UnionFind(object):
    def __init__(self, N):
        self.parent = [i for i in range(N)]
 
    def merge(self, a, b):
        pa = self.root(a)
        pb = self.root(b)
        self.parent[pa] = pb
    
    def root(self, x):
        p = self.parent[x]
        if p == x:
            return x
        else:
            r = self.root(p)
            self.parent[x] = r
            return r
u=UnionFind(n)
for i in range(m):
  a,b,c=map(int,input().split())
  if a>b:
    a=g
    g=b
    b=a
  u.merge(a-1,b-1)
a=[0]*n
for i in range(n):
  a[i]=u.root(i)
print(len(set(a)))

Submission status: Accepted

Solution code:
import sys;sys.setrecursionlimit(10**9)
class u():#UnionFind f-根探し u-連結 s-連結? c-要素数
  def __init__(self,n):self.n,self.r=[-1]*n,[0]*n
  def f(self,x):
    if self.n[x]<0:return x
    else:self.n[x]=self.f(self.n[x]);return self.n[x]
  def u(self,x,y):
    x,y=self.f(x),self.f(y)
    if x==y:return
    elif self.r[x]>self.r[y]:self.n[x]+=self.n[y];self.n[y]=x
    else:self.n[y]+=self.n[x];self.n[x]=y;self.r[y]+=self.r[x]==self.r[y]
  def s(self,x,y):return self.f(x)==self.f(y)
  def c(self,x):return -self.n[self.f(x)]
n,m=map(int,input().split());u=u(n)
for i in range(m):
  a,b,c=map(int,input().split());a-=1;b-=1
  if not(u.s(a,b)):n-=1;u.u(a,b)
print(n)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]  # 自身が親だとして初期化
        self.rank = [0 for _ in range(n)]  # 自身が根なので根の深さ0として初期化

    def find(self, x):
        """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,yの属する集合のマージ"""
        x = self.find(x)  # xの根
        y = self.find(y)  # yの根
        if x == y:  # 同じ根を持つなら何もしない
            return
        if self.rank[x] < self.rank[y]:  # yの根のほうが深いとき
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


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

parent = [-1] * N
unionfind = UnionFind(N)
for i in range(M):
    xi, yi, zi = map(int, input().split())
    xi -= 1
    yi -= 1
    unionfind.unite(xi, yi)
    parent[yi] = xi

# print(parent)
# print(unionfind.par)
ans_set = set()
for i in range(N):
    ans_set.add(unionfind.find(i))
ans = len(ans_set)

# print(ans_set)
print(ans)

Submission status: Accepted

Solution code:
def uf_init(n):
    return list(range(n))

def uf_root(uf, x):
    update_node_arr = []
    while(uf[x] != x):
        update_node_arr.append(x)
        x = uf[x]
    for y in update_node_arr:
        uf[y] = x
    return x

def uf_same(uf, x, y):
    return uf_root(uf, x) == uf_root(uf, y)

def uf_unite(uf, x, y):
    x = uf_root(uf, x)
    y = uf_root(uf, y)
    if x == y:
        return
    uf[x] = y

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

uf = uf_init(N)

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

uf_roots = set()
for i in range(N):
    uf_roots.add(uf_root(uf, i))

print(len(uf_roots))

Submission status: Accepted

Solution code:
def init(n):
    for i in range(N):
        par[i] = i
        rnk[i] = 0

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

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if (rnk[x] < rnk[y]):
        par[x] = y
    else:
        par[y] = x
        if(rnk[x] == rnk[y]):
            rnk[x] += 1
            
N, M = map(int, input().split())

X = [0 for i in range(M)]
Y = [0 for i in range(M)]
Z = [0 for i in range(M)]

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

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

for i in range(M):
    unite(X[i], Y[i])
    
for i in range(N):
  find(i)

print(len(set(par)))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
XY = [i for i in range(N + 1)]

def root(x):
  temp = x
  while temp != XY[temp]:
    temp = XY[temp]
  XY[x] = temp
  return temp
for _ in range(M):
  x, y = map(int, input().split()[:2])
  XY[root(x)] = root(y)

print(sum(i == v for i, v in enumerate(XY)) - 1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, k = [ int(v) for v in input().split() ]
card_parent = [ i for i in range(n) ]
card_set = [ set([i]) for i in range(n) ]
card_list = set( tuple( int(v)-1 for v in input().split() ) for i in range(k) )

def parent(x,a):
    if card_parent[x] == x:
        return x, a
    else:
        return parent(card_parent[x],a+1)


for i in card_list:
    p, q = i[0], i[1]
    card_parent[p], rank_p = parent(p,0)
    card_parent[q], rank_q = parent(q,0)
    if card_parent[p] != card_parent[q]:
        if rank_p > rank_q:
            card_parent[card_parent[q]] = card_parent[p]
        else:
            card_parent[card_parent[p]] = card_parent[q]




card_parent = [ parent(i,0)[0] for i in range(n) ]

print(len(set(card_parent)))

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
n, k = [ int(v) for v in input().split() ]
card_parent = [ i for i in range(n) ]
card_set = [ set([i]) for i in range(n) ]
card_list = [ tuple( int(v)-1 for v in input().split() ) for i in range(k) ]

def parent(x,a):
    if card_parent[x] == x:
        return x, a
    else:
        return parent(card_parent[x],a+1)


for i in card_list:
    p, q = i[0], i[1]
    card_parent[p], rank_p = parent(p,0)
    card_parent[q], rank_q = parent(q,0)
    if card_parent[p] != card_parent[q]:
        if rank_p > rank_q:
            card_parent[card_parent[q]] = card_parent[p]
        else:
            card_parent[card_parent[p]] = card_parent[q]




card_parent = [ parent(i,0)[0] for i in range(n) ]

print(len(set(card_parent)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
N, M = map(int, input().split())
X = [0] * M
Y = [0] * M
Z = [0] * M 
for i in range(M):
  X[i], Y[i], Z[i] = map(int, input().split())

reach = [[] for _ in range(N)]

for i in range(M) :
    reach[Y[i]-1].append(X[i])
    reach[X[i]-1].append(Y[i])

approach = [False for _ in range(N)]

def change(reach, s):       
    approach[s-1] = True
    for i in reach[s-1]:
        if not approach[i-1] :
            change(reach, i)

ans = 0
for i in range(N) :
    if not approach[i]:
        change(reach, i+1)
        ans += 1

print(ans)

Submission status: Accepted

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

G = [[] for _ in range(N)]
 
for i in XYZ:
    G[i[0]-1].append(i[1])
    G[i[1]-1].append(i[0])
 
check = [False for _ in range(N)]
 
def DFS(G,s):
    check[s-1] = True
    for i in G[s-1]:
        if not check[i-1]:         
            DFS(G,i)
ans = 0
for i in range(N):
    if not check[i]:
        DFS(G,i+1)
        ans += 1

print(ans)

Submission status: Accepted

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

class UnionFind:
    def __init__(self, n):
        self.par = list(range(n))
        self.rank = [0] * 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
    
    def get_par(self):
        return self.par

t = UnionFind(N)
for u, v, _ in edges:
    t.unite(u - 1, v - 1)

print(len(set(t.find(x) for x in range(N))))

Submission status: Accepted

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

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

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        else:
            if self.size(x) < self.size(y):
                x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x

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

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

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


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.is_root(i) for i in range(n)))

Submission status: Accepted

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.sz[x] > self.sz[y]:
            x,y = y,x
        self.sz[x] += self.sz[y]
        self.sz[y] = x

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

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

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)

l = []
for i in range(N):
    l.append(uf.find(i))
print(len(set(l)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
class Node:
    def __init__(self):
        self.next=[]
    def get_data(self,new_next,weight=1):
        self.next.append({new_next:weight})


def BFS():
    total=0
    check_node=tmp_node
    #print(check_node)
    now=min(check_node)
    tmp=[now]
    check_node.remove(now)
    ans=N-len(check_node)
    new_tmp=[]
    while len(check_node)>0:
        #print("tmp:{}".format(tmp))
        if tmp==[]:
            ans+=1
            tmp.append(check_node[0])
            check_node.remove(check_node[0])
        total+=1
        for each in tmp:
            #print("each:{}".format(each))
            for i in node[each].next:
                k=list(i.keys())[0]
                if k in check_node:
                    #print("append :{}".format(k))
                    new_tmp.append(k)
                    check_node.remove(k)
        #print("new_tmp:{}".format(new_tmp))
        #print("check_node:{}".format(check_node))
        tmp=new_tmp
        new_tmp=[]
    #print("end")
    #print("loop time:{}".format(total))
    #print("ans:{}".format(ans))
    print(ans)


def rec_BFS(i):
    tmp=[list(j.keys())[0] for j in i]
    for each in tmp:
        if not check_node[each]:
            check_node[each]=True
            rec_BFS(node[each].next)






        
        

N,M=list(map(int,input().split()))
node=[Node() for _ in range(N)]
#ans=[[100 for _ in range(N)]for _ in range(N)]
tmp_node=[]
for i in range(M):
    tmp_p,tmp_n,tmp_w=list(map(int,input().split()))
    #if not tmp_p-1 in tmp_node:
    #    tmp_node.append(tmp_p-1)
    #if not tmp_n-1 in tmp_node:
    #    tmp_node.append(tmp_n-1)
    node[tmp_p-1].get_data(tmp_n-1)
    node[tmp_n-1].get_data(tmp_p-1)
#BFS()
s=0
check_node=[False for _ in range(N)]
for i in range(N):
    if not check_node[i]:
        check_node[i]=True
        s+=1
        rec_BFS(node[i].next)
print(s)