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: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from typing import List
sys.setrecursionlimit(10 ** 7)


class UnionFind(object):
    """docstring for UnionFind"""

    def __init__(self, n):
        super(UnionFind, self).__init__()
        self.v = [-1 for _ in range(n)]

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

    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        if -self.v[x] < -self.v[y]:
            x, y = y, x
        self.v[x] += self.v[y]
        self.v[y] = x

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

    def has_same_root(self, x, y):
        return self.find_root(x) == self.find_root(y)


def solve(N: int, M: int, X: "List[int]", Y: "List[int]", Z: "List[int]"):
    uf = UnionFind(N)
    for x, y, z in zip(X, Y, Z):
        uf.unite(x - 1, y - 1)

    print(sum(1 for i in range(N) if uf.is_root(i)))

    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools
# (tips: You use the default template now. You can remove this line by using your custom template)
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: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

a = input().split()
N = int(a[0])
M = int(a[1])

l = []
f = []
for i in range(N):
	temp = []
	l.append(temp)
	f.append(0)

for i in range(M):
	b = input().split()
	X = int(b[0]) - 1
	Y = int(b[1]) - 1
	l[X].append(Y)
	l[Y].append(X)

def search(cnt, li, flag, num):
	if(flag[num] == 0):
		flag[num] = cnt
		if(len(li[num]) != 0):
			for i in range(len(li[num])):
				search(cnt, li, flag, li[num][i])
		
cnt = 0
for i in range(N):
	if(f[i] == 0):
		cnt += 1
		search(cnt, l, f, i)			
print(cnt)

Submission status: Runtime Error

Solution code:
a = input().split()
N = int(a[0])
M = int(a[1])

l = []
f = []
for i in range(N):
	temp = []
	l.append(temp)
	f.append(0)

for i in range(M):
	b = input().split()
	X = int(b[0]) - 1
	Y = int(b[1]) - 1
	l[X].append(Y)
	l[Y].append(X)

def search(cnt, li, flag, num):
	if(flag[num] == 0):
		flag[num] = cnt
		if(len(li[num]) != 0):
			for i in range(len(li[num])):
				search(cnt, li, flag, li[num][i])
		
cnt = 0
for i in range(N):
	if(f[i] == 0):
		cnt += 1
		search(cnt, l, f, i)			
print(cnt)

Submission status: Runtime Error

Solution code:
a = input().split()
N = int(a[0])
M = int(a[1])

l = []
f = []
for i in range(N):
	temp = []
	l.append(temp)
	f.append(0)

for i in range(M):
	b = input().split()
	X = int(b[0]) - 1
	Y = int(b[1]) - 1
	l[X].append(Y)
	l[Y].append(X)

def search(cnt, li, flag, num):
	if(flag[num] == 0):
		flag[num] = cnt
		if(len(li[num]) != 0):
			for i in range(len(li[num])):
				search(cnt, li, flag, li[num][i])
		
cnt = 0
for i in range(N):
	print(f)
	if(f[i] == 0):
		cnt += 1
		search(cnt, l, f, i)			
print(cnt)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)
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: Runtime Error

Solution code:
import sys
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: Runtime Error

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

N, M = map(int, input().split())
L = [[int(v) 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 - 1, b - 1)
    
s = set()
for i in range(N):
    s.add(u.get_root(i))

print(len(s))

Submission status: Runtime Error

Solution code:
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)

print(len(set([find(i) for i in range(n)])))

Submission status: Runtime Error

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

g = [i for i in range(n+1)]
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,yi)

print(len(set([find(i) for i in range(1,n+1)])))

Submission status: Runtime Error

Solution code:
n , m = map(int,input().split())
d = {}
for i in range(m):
    xi, yi, zi = map(int,input().split())
    if xi in d:
        d[xi] += [yi]
    else:
        d[xi] = [yi]
    if yi in d:
        d[yi] += [xi]
    else:
        d[yi] = [xi]

def f(x):
    global v
    v.remove(x)
    if x in d:
        for k in d[x]:
            if k in v:
                f(k)


v = [i+1 for i in range(n)]
count = 0
while len(v) > 0:
    f(v[0])
    count += 1
print(count)

Submission status: Runtime Error

Solution code:
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())
  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: Runtime Error

Solution code:
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())
  u.merge(a-1,b-1)
a=[0]*n
for i in range(n):
  a[i]=u.root(i)
print(len(a))

Submission status: Runtime Error

Solution code:
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(in,input().split())
  uf.merge(a-1,b-1)
print(len(u.parent))

Submission status: Runtime Error

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

def uf_root(uf, x):
    if uf[x] != x:
        uf[x] = uf_root(uf, uf[x])
    return uf[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: Runtime Error

Solution code:
from collections import defaultdict as ddydd
from collections import deque as q
N, M = map(int, input().split())
XYZ = ddydd(list)
TreeMemo = ddydd(int)
link = []
trace = [0] * (N + 1)
start = 0
for _ in range(M):
  x, y, z = map(int, input().split())
  if start == 0:
    start = x
  XYZ[x].append(y)
  XYZ[y].append(x)
  TreeMemo[x] = 0
  TreeMemo[y] = 0
  if not x in link: link.append(x)
  if not y in link: link.append(y)

def searchPreMin(n):
  global trace
  trace.append(n)
  temp = min(XYZ[n])
  if temp < n:
    return searchPreMin(temp)
  else:
    return n
def searchPreMax(n):
  global trace
  trace.append(n)
  temp = max(XYZ[n])
  if temp > n:
    return searchPreMax(temp)
  else:
    return n
def searchMax(n):
  global trace
  if trace[n] != 0:
    return TreeMemo[n]
  trace = []
  n = searchPreMin(n)
  temp = searchPreMax(n)
  for t in trace:
    TreeMemo[t] = temp
  return temp

forest = []
nodes = len(link)
while link:
  temp = link.pop()
  tree = searchMax(temp)
  if not tree in forest: forest.append(tree)
    
print(N - nodes + len(forest))

Submission status: Runtime Error

Solution code:
from collections import defaultdict as ddydd
from collections import deque as q
N, M = map(int, input().split())
XYZ = ddydd(list)
TreeMemo = ddydd(int)
link = []
trace = []
start = 0
for _ in range(M):
  x, y, z = map(int, input().split())
  if start == 0:
    start = x
  XYZ[x].append(y)
  XYZ[y].append(x)
  TreeMemo[x] = 0
  TreeMemo[y] = 0
  if not x in link: link.append(x)
  if not y in link: link.append(y)

def searchPreMin(n):
  global trace
  trace.append(n)
  temp = min(XYZ[n])
  if temp < n:
    return searchPreMin(temp)
  else:
    return n
def searchPreMax(n):
  global trace
  trace.append(n)
  temp = max(XYZ[n])
  if temp > n:
    return searchPreMax(temp)
  else:
    return n
def searchMax(n):
  global trace
  if trace[n] != 0:
    return TreeMemo[t]
  trace = []
  n = searchPreMin(n)
  temp = searchPreMax(n)
  for t in trace:
    TreeMemo[t] = temp
  return temp

forest = []
nodes = len(link)
while link:
  temp = link.pop()
  tree = searchMax(temp)
  if not tree in forest: forest.append(tree)
    
print(N - nodes + len(forest))

Submission status: Runtime Error

Solution code:
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: Runtime Error

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):
    if card_parent[x] == x:
        return x
    else:
        return parent(card_parent[x])


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




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

print(len(set(card_parent)))

Submission status: Runtime Error

Solution code:
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: Runtime Error

Solution code:
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())

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

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

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

print(ans)

Submission status: Runtime Error

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

reach = [[] for _ in range(N)]
 
for i in XYZ:
    reach[i[0]-1].append(i[1])
    reach[i[1]-1].append(i[0])

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: Runtime Error

Solution code:
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: Runtime Error

Solution code:
N, M = map(int, input().split())
X = [0] * M
Y = [0] * M
Z = [0] * M 
unique = []
count = 0
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)]

ans = 0

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

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

print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
X = [0] * M
Y = [0] * M
Z = [0] * M 
unique = []
count = 0
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)]

ans = 0

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

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

print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
X = [0] * M
Y = [0] * M
Z = [0] * M 
unique = []
count = 0
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)]

i = 1

ans = 0

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

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

print(ans)

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000)

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

#   木の根を求める
	def root(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.root(self.par[x])
			return self.par[x]


#   x を含むグループと y を含むグループをマージする
	def merge(self, x, y):
		x = self.root(x)
		y = self.root(y)
		if x == y:
			return
		self.par[x] = y

if __name__ == '__main__':
	N, M = map(int, input().split())
	uf = UnionFind(N)
	for i in range(M):
		X, Y, Z = map(int, input().split())
		uf.merge(X-1, Y-1)
	
	ans = [ uf.root(i) for i in range(N)]

	print(len(set(ans)))

Submission status: Runtime Error

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

#   木の根を求める
	def root(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.root(self.par[x])
			return self.par[x]


#   x を含むグループと y を含むグループをマージする
	def merge(self, x, y):
		x = self.root(x)
		y = self.root(y)
		if x == y:
			return
		self.par[x] = y

if __name__ == '__main__':
	N, M = map(int, input().split())
	uf = UnionFind(N)
	for i in range(M):
		X, Y, Z = map(int, input().split())
		uf.merge(X-1, Y-1)
#		print(uf.par)
	
	ans = [ uf.root(i) for i in range(N)]

	print(len(set(ans)))

Submission status: Runtime Error

Solution code:
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


def main():
    N, M = map(int, input().split())

    uf = UnionFind(N)
    for _ in range(M):
        x, y, _ = map(int, input().split())
        uf.merge(x-1, y-1)

    print(len(list(filter(lambda x: x == uf.root(x), range(N)))))


main()

Submission status: Runtime Error

Solution code:
class uf_tree():

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

    def indep(self):
        dep =0
        for i in range(self.n):
            if i == self.par[i]:
                dep += 1

        return dep

    def unite(self,child,mas):
        if self.root(child) == self.root(mas):
            return
        else:
            self.par[self.root(child)] = self.root(self.mas)

    def root(self,i):
        if self.par[i] == i:
            return i
        else:
            self.par[i] = self.root(self.par[i])
            return self.par[i]

    def same(self,x,y):
        if self.root(x) == self.root(y):
            return True
        else:
            return False



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

print(uf.indep()-1)

Submission status: Runtime Error

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

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)
    return
ans = 0
for i in range(1,N+1):
    if not check[i-1]:
        DFS(G,i)
        ans += 1
print(ans)

Submission status: Runtime Error

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

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

G = [[] for _ in range(N+1)]

for i in XYZ:
    G[i[0]-1].append(i[1])
    G[i[1]-1].append(i[0])

check = [False for _ in range(N+1)]#各頂点を訪問したかどうか
def DFS(G,s):
    check[s-1] = True
    for i in G[s-1]:
        if not check[i-1]:
            DFS(G,i)
    return
ans = 0
for i in range(N):
    if not check[i]:
        DFS(G,i+1)
        ans += 1
print(ans)

Submission status: Runtime Error

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

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+1)]#各頂点を訪問したかどうか
def DFS(G,s):
    check[s-1] = True
    for i in G[s-1]:
        if not check[i-1]:
            DFS(G,i)
    return
ans = 0
for i in range(N):
    if not check[i]:
        DFS(G,i+1)
        ans += 1
print(ans)

Submission status: Runtime Error

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

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)
    return
ans = 0
for i in range(N):
    if not check[i]:
        DFS(G,i+1)
        ans += 1
print(ans)

Submission status: Runtime Error

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

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

G = [[] for _ in range(N)]
for i in range(M):
    G[XYZ[i][0]-1].append(XYZ[i][1])
    G[XYZ[i][1]-1].append(XYZ[i][0])

check = [False for _ in range(N)]#各頂点を訪問したかどうか
def DFS(G,start):
    check[start-1] = True
    for i in G[start-1]:
        if not check[i-1]:
            DFS(G,i)
    return
ans = 0
for i in range(N):
    if not check[i]:
        DFS(G,i+1)
        ans += 1
print(ans)

Submission status: Runtime Error

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

N,M = 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,start):
    check[start-1] = True
    for j in G[start-1]:
        if not check[j-1]:
            DFS(G,j)
    return
ans = 0
for i in range(N):
    if not check[i]:
        DFS(G,i+1)
        ans += 1
print(ans)

Submission status: Runtime Error

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

N,M = 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,start):
    check[start-1] = True
    for i in G[start-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: Runtime Error

Solution code:
class UnionFind:
    def __init__(self,n):
        self.parent=[i for i in range(n)]
        self.rank=[0 for _ in range(n)]

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

    def union(self,x,y):
        rootx=self.find(x)
        rooty=self.find(y)
        if self.rank[rootx]<self.rank[rooty]:
            self.parent[rootx]=rooty
        else:
            self.parent[rooty]=rootx
            if self.rank[rootx]==self.rank[rooty]:
                self.rank[rootx]+=1

n,m=map(int,input().split())
xyz=[list(map(int,input().split())) for _ in range(m)]
uf=UnionFind(n)
for x,y,z in xyz:
    x,y=x-1,y-1
    uf.union(x,y)

# print(uf.parent)
for i in range(n):
    uf.find(n)
print(len(set(uf.parent)))

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
N,M = map(int,input().split())
lst = [i for i in range(N)]

def root(n):
    if n == lst[n]:
        return n
    lst[n] = func(lst[n])
    return lst[n]

def union(x,y):
    rootX, rootY = root(x), root(y)
    if rootX != rootY:
        lst[max(x,y)] = min(x,y)

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

for i in range(N):
    func(i)

ans = len([i for i in range(N) if lst[i] == i])
print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
N,M = map(int,input().split())
lst = [i for i in range(N)]

def root(n):
    if n == lst[n]:
        return n
    lst[n] = func(lst[n])
    return lst[n]

def union(x,y)
    rootX, rootY = root(x), root(y)
    if rootX != rootY:
        lst[max(x,y)] = min(x,y)

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

for i in range(N):
    func(i)

ans = len([i for i in range(N) if lst[i] == i])
print(ans)

Submission status: Runtime Error

Solution code:
N, M = [int(x) for x in input().split()]
par = list(range(N))

def root(n):
    if par[n] == n:
        return n
    else:
        ret = root(par[n])
        par[n] = ret
        return ret

def unite(a, b):
    a = root(a)
    b = root(b)
    if a != b:
        par[a] = b

for i in range(M):
    x, y, _ = [int(x) for x in input().split()]
    unite(x-1, y-1)

cnt = 0
for i,p in enumerate(par):
    if root(p) == i:
        cnt += 1
print(cnt)

Submission status: Runtime Error

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

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

for i in range(M):
    x,y,_ = map(int, input().split())
    rx = root(x-1)
    ry = root(y-1)
    if rx != ry:
        par[ry] = rx

rlist = set()
for i in par:
    rlist.add(root(i))

print(len(rlist))

Submission status: Runtime Error

Solution code:
N, M = (int(x) for x in input().split())
par = list(range(N))

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

for i in range(M):
    x,y,_ = map(int, input().split())
    rx = root(x-1)
    ry = root(y-1)
    if rx != ry:
        par[ry] = rx

rlist = set()
for i in range(N):
    rlist.add(root(i))

print(len(rlist))

Submission status: Runtime Error

Solution code:
N, M = (int(x) for x in input().split())
par = [x for x in range(N)]

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

for i in range(M):
    x,y,_ = map(int, input().split())
    rx = root(x-1)
    ry = root(y-1)
    if rx != ry:
        par[rx] = ry

rlist = set()
for i in range(N):
    rlist.add(root(i))

print(len(rlist))