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:
def visit_tree(now, num):
    if not visited[now]:
        visited[now] = num
        if len(tree[now]) == 0:
            return 0
        for i in range(len(tree[now])):
            visit_tree(tree[now][i], num)

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

visited = [0 for _ in range(n)]
num = 0
for i in range(n):
    if not visited[i]:
        num += 1
        visit_tree(i, num)

print(num)

Submission status: Runtime Error

Solution code:
def visit_tree(now, num):
    if now >= len(visited):
        return 0
    if not visited[now]:
        visited[now] = num
        for i in range(len(tree[now])):
            visit_tree(tree[now][i], num)

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

visited = [0 for _ in range(n)]
num = 0
for i in range(n):
    if not visited[i]:
        num += 1
        visit_tree(i, num)

print(num)

Submission status: Runtime Error

Solution code:
def visit_tree(now, num):
    if not visited[now]:
        visited[now] = num
        for i in range(len(tree[now])):
            visit_tree(tree[now][i], num)

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

visited = [0 for _ in range(n)]
num = 0
for i in range(n):
    if not visited[i]:
        num += 1
        visit_tree(i, num)

print(num)

Submission status: Runtime Error

Solution code:
from _collections import deque
from _ast import Num


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
from collections import deque
from math import sqrt
from math import floor
import heapq
# https://atcoder.jp/contests/agc033/tasks/agc033_b
# B - LRUD Game
"""
"""
N = gi()
M = gi()
g = [[] for i in range(N + 1)]

for i in range(M):
    x = gi()
    y = gi()
    z = gi()
    g[x].append(y)
    g[y].append(x)

visited = [0] * (N + 1)


def dfs(v):
    if visited[v]:
        return
    visited[v] = 1

    for u in g[v]:
        dfs(u)


ans = 0
for v in range(1, N + 1):
    if visited[v]:
        continue
    ans += 1
    dfs(v)

print(ans)

Submission status: Runtime Error

Solution code:
from sys import setrecursionlimit
setrecursionlimit(100000)

nVertices, nEdges = map(int, input().split())
g = [[] for _ in range(nVertices + 1)]
for _ in range(nEdges):
    u, v, _ = map(int, input().split())
    g[u].append(v)
    g[v].append(u)

def dfs(v):
    visited[v] = True
    for to in g[v]:
        if not visited[to]:
            dfs(to)

cnt = 0
visited = [False] * (nVertices + 1)
for v in range(1, nVertices + 1):
    if not visited[v]:
        dfs(v)
        cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
N,M=map(int,input().split())
XYZ=[list(map(int,input().split())) for i in range(M)]
data=[[] for i in range(N+1)]
ittenai=[]
for x,y,z in XYZ:
    data[x].append(y)
    data[y].append(x)
    ittenai.append(x)
    ittenai.append(y)


ittenai=set(ittenai)
count=N-len(ittenai)
while ittenai:
    x=ittenai.pop(x)
    stack=deque([x])

    count+=1
    while stack:
        num=stack.popleft()
        for i in data[num]:
            if i in ittenai:
                ittenai.remove(i)
                stack.append(i)
print(count)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()

# Aでxの根を求める
def find(A, x):
    p = A[x]
    if p == x:
        return x
    a = find(A, p)
    A[x] = a
    return a

# Aでxとyの属する集合の併合
def union(A, x, y):
    if find(A, x) > find(A, y):
        bx, by = find(A, y), find(A, x)
    else:
        bx, by = find(A, x), find(A, y)
    # 根をbx(値の小さい方)に統一 
    A[by] = bx

V = [i for i in range(N)]
for i in range(M):
    x, y, z = lr()
    if find(V, x-1) != find(V, y-1):
        union(V, x-1, y-1)

answer = [find(x) for x in set(V)]
print(len(set(answer)))
# 36

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()

# Aでxの根を求める
def find(A, x):
    p = A[x]
    if p == x:
        return x
    a = find(A, p)
    A[x] = a
    return a

# Aでxとyの属する集合の併合
def union(A, x, y):
    if find(A, x) > find(A, y):
        bx, by = find(A, y), find(A, x)
    else:
        bx, by = find(A, x), find(A, y)
    # 根をbx(値の小さい方)に統一 
    A[by] = bx

V = [i for i in range(N)]
for i in range(M):
    x, y, z = lr()
    if find(V, x-1) != find(V, y-1):
        union(V, x-1, y-1)

answer = [find(x) for x in set(V)]
print(len(answer))
# 36

Submission status: Runtime Error

Solution code:
def f(j):
  a[j]=1
  n=len(dic[j])
  for k in range(n):
    if a[dic[j][k]]==0:
      f(dic[j][k])

N, M=map(int, input().split())
dic={}
for i in range(1, N+1):
  dic[i]=[]

for i in range(M):
  x, y, z=map(int, input().split())
  dic[x].append(y)
  dic[y].append(x)
  
a=[0]*(N+1)
out=0
i=1
while i<N+1:
  if a[i]==0:
    a[i]=1
    out+=1
    n=len(dic[i])
    for j in range(n):
      if a[dic[i][j]]==0:
        f(dic[i][j])
  i+=1
print(out)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
V = [[] for _ in range(N)]
visited = [False for _ in range(N)]
ans = 0

for _ in range(M):
	x, y, z = map(int, input().split())
	V[x - 1].append(y - 1)
	V[y - 1].append(x - 1)
	
for i in range(N):
	if V[i] == []:
		visited[i] = True
		ans += 1
	
def dfs(cur):
	visited[cur] = True
	for adj in V[cur]:
		if visited[adj]: continue
		dfs(adj)
	
while not all(visited):
	cur = visited.index(False)
	visited[cur] = True
	dfs(cur)
	ans += 1
	
print(ans)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
V = [[] for _ in range(N)]
visited = [False for _ in range(N)]
ans = 0

for _ in range(M):
	x, y, z = map(int, input().split())
	V[x - 1].append(y - 1)
	V[y - 1].append(x - 1)
	
for i in range(N):
	if V[i] == []:
		visited[i] = True
		ans += 1
	
def dfs(cur):
	visited[cur] = True
	for adj in V[cur]:
		if visited[adj]: continue
		return dfs(adj)
	
while not all(visited):
	cur = visited.index(False)
	visited[cur] = True
	dfs(cur)
	ans += 1
	
print(ans)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
xyz=[tuple(map(int,input().split())) for i in range(M)]
class unionFind:
    parent = []

    def __init__(self, N):
        self.parent = [i for i in range(N)]

    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 same(self, x, y):
        x, y = x-1, y-1
        return(self.root(x) == self.root(y))

    def unite(self, x, y):
        x, y = x-1, y-1
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.parent[x] = y
            return
G=unionFind(N)
for x,y,z in xyz:
  G.unite(x,y)
ans=set()
for i in range(N):
  ans.add(G.root(i))
print(len(ans))

Submission status: Runtime Error

Solution code:
f-8

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

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

searched = [False] * N
count = 0
for i in range(N):
	if searched[i] == True:
		continue

	count += 1
	stack = [i]
	while len(stack) > 0:
		node = stack.pop()
		searched[node] = True
		for n in adj_list[node]:
			if searched[n] == False:
				stack.append(n)

print(count)

Submission status: Runtime Error

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

parent=[i for i in range(N)]
depth=[0 for i in range(N)]

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

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

def unite(x,y):
  rx=root(x)
  ry=root(y)
  if rx==ry:
    return
  if depth[x]<depth[y]:
    parent[rx]=ry
  else:
    parent[ry]=rx
    if depth[x]==depth[y]:
      depth[x]+=1
      
for i in range(M):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  unite(a,b)
  
roots=set()
for i in range(N):
  roots.add(root(i))

print(len(roots)-1)

Submission status: Runtime Error

Solution code:
# union-findで行けそう。

n, m = map(int, input().split())
par = [-1] * (n + 1)


def find(a):
    if par[a] < 0:
        return a
    else:
        par[a] = find(par[a])
        return par[a]


def unite(a, b):
    a = find(a)
    b = find(b)
    if a == b:
        return False
    else:
        if par[a] < par[b]:
            a, b = b, a
        par[x] += par[y]
        par[y] = x
        return True


for i in range(m):
    x, y, z = map(int, input().split())
    unite(x, y)
cnt = 0
for i in range(n):
    if par[i + 1] < 0:
        cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
    def find(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        self.parent[x] = y

def main():
    N, M = map(int, input().split())
    uf = UnionFind(N)
    for i in range(M):
        X, Y, Z = map(int, input().split())
        uf.union(X-1, Y-1)
    s = set()
    for i in range(N):
        s.add(uf.find(i))
    print(len(s))

if __name__ == "__main__":
    sys.setrecursionlimit(10**6)
    main()

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
    def find(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        self.parent[x] = y

def main():
    N, M = map(int, input().split())
    uf = UnionFind(N)
    for i in range(M):
        X, Y, Z = map(int, input().split())
        uf.union(X-1, Y-1)
    s = set()
    for i in range(N):
        s.add(uf.find(i))
    print(len(s))

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from operator import itemgetter


def solve():
    N, M = map(int, input().split())
    xy_dict = defaultdict(int)
    xy = [[] for _ in range(N)]
    for _ in range(M):
        x, y, z = map(lambda j: int(j)-1, input().split())
        xy_dict[x] += 1
        xy_dict[y] += 1
        xy[x].append(y)
        xy[y].append(x)
    
    xy_sorted = sorted(xy_dict.items(), key=itemgetter(1), reverse=True)
    opened = [0 for _ in range(N)]
    ans = N
    for i in range(M):
        parent = xy_sorted[i][0]
        if opened[parent] == 1:
            for child in xy[parent]:
                if opened[child] == 0:
                    opened[child] = 1
                    ans -= 1
            continue
        opened[parent] = 1
        for child in xy[parent]:
            opened[child] = 1
        ans -= xy_dict[parent]
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from operator import itemgetter


def solve():
    N, M = map(int, input().split())
    xy_dict = defaultdict(int)
    xy = [[] for _ in range(N+1)]
    for _ in range(M):
        x, y, z = map(int, input().split())
        xy_dict[x] += 1
        xy_dict[y] += 1
        xy[x].append(y)
        xy[y].append(x)
    
    xy_sorted = sorted(xy_dict.items(), key=itemgetter(1), reverse=True)
    opened = [0 for _ in range(N+1)]
    ans = N
    for i in range(M):
        parent = xy_sorted[i][0]
        if opened[parent] == 1:
            continue
        opened[parent] = 1
        for child in xy[parent]:
            opened[child] = 1
        ans -= xy_dict[parent]
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
n, m = map(int, input().split())
memo = set(list(range(n)))
E = [[] for i in range(n)]
for i in range(m):
    x, y, z = map(int, input().split())
    E[x-1].append(y-1)
    E[y-1].append(x-1)
def dfs(cur, pre):
    stack = deque([[cur, pre]])
    while stack:
        cur, pre = stack.pop()
        memo.discard(cur)
        for e in E[cur]:
            if e != pre and e in memo:
                stack.append([e, cur])
ans = 0
for i in range(n):
    if i in memo:
        dfs(cur, -1)
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**5)
n, m = map(int, input().split())
adjacent_list = [[] for i in range(n + 1)]
for i in range(m):
    x, y, z = map(int,input().split())
    adjacent_list[x].append(y)
    adjacent_list[y].append(x)
##結局、グラフが何個あるか数える
finished = set()
ans = 0
def dfs(node):
    global finished
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i)

while len(finished) != n:
    for i in range(1,n+1):
        if i not in finished:
            dfs(i)
            ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
adjacent_list = [[] for i in range(n + 1)]
for i in range(m):
    x, y, z = map(int,input().split())
    adjacent_list[x].append(y)
    adjacent_list[y].append(x)
##結局、グラフが何個あるか数える
finished = set()
ans = 0
def dfs(node):
    global finished
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i)

while len(finished) != n:
    for i in range(1,n+1):
        if i not in finished:
            dfs(i)
            ans += 1
        
print(ans)

Submission status: Runtime Error

Solution code:
#17:11
n,m = map(int,input().split())
pre = [-1 for i in range(n)]
for _ in range(m):
  x,y,z = map(int,input().split())
  x -= 1
  y -= 1
  while pre[x] != -1:
    x = pre[x]
  while pre[y] != -1:
    y = pre[y]
  if x != y:
    if len(X) > len(Y):
      pre[x] = y
    else:
      pre[y] = x
father = set()
ans = 0
for i in range(n):
  if pre[i] == -1:
    ans += 1
#print(pre)
print(ans)

Submission status: Runtime Error

Solution code:
#17:11
n,m = map(int,input().split())
pre = [-1 for i in range(n)]
for _ in range(m):
  x,y,z = map(int,input().split())
  x -= 1
  y -= 1
  X = []
  Y = []
  while pre[x] != -1:
    X.append(x)
    x = pre[x]
  while pre[y] != -1:
    Y.append(Y)
    y = pre[y]
  if x != y:
    if len(X) > len(Y):
      pre[x] = y
      for xx in X:
        pre[xx] = y
      for yy in Y:
        pre[yy] = y
    else:
      pre[y] = x
      for xx in X:
        pre[xx] = x
      for yy in Y:
        pre[yy] = x
father = set()
ans = 0
for i in range(n):
  if pre[i] == -1:
    ans += 1
#print(pre)
print(ans)

Submission status: Runtime Error

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

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

        ret = self.find(self.par[c])
        self.par[c] = ret
        return ret

    def union(self, x, y):
        xr = self.find(x)
        yr = self.find(y)
        if xr == yr:
            return

        if self.rank[yr] > self.rank[xr]:
            self.par[xr] = yr
        else:
            self.par[yr] = xr
            if self.rank[xr] == self.rank[yr]:
                self.rank[xr] += 1

    def show(self):
        print('parent', self.par[1:])
        print('rank', self.rank[1:])

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

for i in range(M):
    x, y, z = map(int, input().split())
    uf.union(x, y)


print([i == v for i, v in enumerate(uf.par[])].count(True)) - 1

Submission status: Runtime Error

Solution code:


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

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

def dfs(now,color):
    for y in path[now]:
        if clasta[y] == -1:
            clasta[y] = color
            dfs(y,color)
ans = 0
for idx,i in enumerate(clasta):
    if i == -1:
        clasta[idx] = idx
        dfs(idx,idx)
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
#1 or 2
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())
XY = []
for i in range(M):
    XY.append([X[i],Y[i]])
XY.sort()
for i in range(M):
    if R[XY[i][1]-1] == 0:
        R[XY[i][0]-1] = 0
    else:
        R[XY[i][1]-1] = 0
count = 0
for i in range(N):
    if R[i] != 0:
        count = count + 1
print(count)

Submission status: Runtime Error

Solution code:
#1 or 2
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())
XY = []
for i in range(M):
    XY.append([X[i],Y[i]])
XY.sort()
print(R)
for i in range(M):
    if R[XY[i][1]-1] == 0:
        R[XY[i][0]-1] = 0
    else:
        R[XY[i][1]-1] = 0
count = 0
for i in range(N):
    if R[i] != 0:
        count = count + 1
print(count)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline

def dfs(v,G,visit):
    visit[v-1]=1    
    for next in G[v-1]:        
        if visit[next-1]:
            continue
        if dfs(next,G,visit) == True:
            return True  
 
N, M =map(int, input().split())
G  = [[] for _ in range(N)]
for i in range(M):
    a,b ,_= map(int, input().split())
    G[a-1].append(b)
    G[b-1].append(a)
 
count = 0

visit = np.array([0]*N)
for i in range(1,N+1):
  if visit[i-1]:
    continue
  if G[i-1]:  
    _ = dfs(i,G,visit)
  else:
    visit[i-1] = 1
  count += 1

print(count)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
input = sys.stdin.readline

def dfs(v,G,visit):
    visit[v-1]=1    
    for next in G[v-1]:        
        if visit[next-1]:
            continue
        if dfs(next,G,visit) == True:
            return True  
 
N, M =map(int, input().split())
G  = [[] for _ in range(N)]
for i in range(M):
    a,b ,_= map(int, input().split())
    G[a-1].append(b)
    G[b-1].append(a)
 
count = 0

visit = np.array([0]*N)
for i in range(1,N+1):
  if visit[i-1]:
    continue
  if G[i-1]:  
    _ = dfs(i,G,visit)
  else:
    visit[i-1] = 1
  count += 1

print(count)

Submission status: Runtime Error

Solution code:
n,m=list(map(int,input().split()))
a=[0]*n
k=0
for i in range(m):
  x,y,z=map(int,input().split())
  x-=1
  y-=1
  if a[x]==0 and a[y]==0:
    k+=1
    a[x]=k
    a[y]=k
  elif a[x]==0:
    a[x]=a[y]
  elif a[y]==0:
    a[y]=a[x]
  else:
    for j in range(m):
      if a[j]==a[y]:
        a[j]=a[x]
if a.count(0)==0:
  print(len(list(set(a))))
else:
  print(a.count(0)+len(list(set(a)))-1)

Submission status: Runtime Error

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

Solution code:
n,m = map(int,input().split())
f = [False for _ in range(n)]
a = [[] for _ in range(n)]

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

def main():
    res = 0
    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)

main()

Submission status: Runtime Error

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

Solution code:
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())
    x -= 1
    y -= 1
    a[x].append(y)
    a[y].append(x)

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

print(res)

Submission status: Runtime Error

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

def dfs(k):
    global f
    global a
    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(0,n):
    if not f[i]:
        res += 1
        dfs(i)

print(res)

Submission status: Runtime Error

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

def dfs(i):
    global f
    global a
    f[i] = True
    for g in a[i]:
        if not f[g]:
            dfs(g)
res = 0
for i in range(n):
    if not f[i]:
        res += 1
        dfs(i)

print(res)

Submission status: Runtime Error

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

def dfs(i):
    global f
    global a
    f[i] = True
    for g in a[i]:
        if not f[g]:
            dfs(g)
res = 0
for i in range(n):
    if not f[i]:
        res += 1
        dfs(i)

print(res)

Submission status: Runtime Error

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

def dfs(i):
    f[i] = True
    for g in a[i]:
        if not f[g]:
            dfs(g)
res = 0
for i in range(n):
    if not f[i]:
        res += 1
        dfs(i)

print(res)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n):
        self.table = [-1 for _ in range(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 find(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

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

ans = 0
for v in uf.table:
    if v<0:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
# 2019/10/10

class unionfind():
    def __init__(self,n):
        self.par=list(range(n+1))
        self.rank=[0]*(n+1)
    
    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 is_same(self,x,y):
        return self.find(x)==self.find(y)
    
    def unite(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

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

uf=unionfind(n)

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

ans=set(uf.par[1:])
print(len(ans))

Submission status: Runtime Error

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


def dfs(v, visited, G):
    visited[v] = True
    for nv in G[v]:
        if visited[nv]==False:
            dfs(nv, visited, G)


def main():
    N, M = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        x, y, z = map(int, input().split())
        G[x-1].append(y-1)
        G[y-1].append(x-1)
    
    nodes = list(range(N))
    visited = [False]*N
    ans = 0
    while len(nodes)!=0:
        v = nodes.pop()
        if visited[v]==True:
            continue
        ans += 1
        dfs(v, visited, G)
        # print(visited)
        # print(nodes)
    
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

input = sys.stdin.readline()

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

ans = list(range(N))
def root(a):
    if a==ans[a]:
        return a
    else:
        return root(ans[a])

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

A = {}
for a in ans:
    A[a] = 1

print(len(A))

Submission status: Runtime Error

Solution code:
def clr(x):
    for y in G[x]:
        if hist[y]==0:
            hist[y]=1
            A.append(y)
            clr(y)
N,M = map(int,input().split())
G = {}
for _ in range(M):
    x,y,_ = map(int,input().split())
    if x not in G:
        G[x] = []
    G[x].append(y)
    if y not in G:
        G[y] = []
    G[y].append(x)
cnt = N-len(G)
hist = [0 for i in range(N+1)]
LG = {i:0 for i in list(G.keys())}
while LG:
    s = LG.popitem()[0]
    hist[s]=1
    A = []
    clr(s)
    for x in A:
        del LG[x]
    cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
def clr(x):
    for y in G[x]:
        if hist[y]==0:
            hist[y]=1
            A.append(y)
            clr(y)
N,M = map(int,input().split())
G = {}
for _ in range(M):
    x,y,_ = map(int,input().split())
    if x not in G:
        G[x] = []
    G[x].append(y)
    if y not in G:
        G[y] = []
    G[y].append(x)
cnt = N-len(G)
hist = [0 for i in range(N+1)]
while G:
    s = list(G.keys())[0]
    hist[s]=1
    A = [s]
    clr(s)
    for x in A:
        del G[x]
    cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
def col(i):
    for x in G[i]:
        if hist[x]==0:
            hist[x]=1
            A.remove(x)
            col(x)
N,M = map(int,input().split())
G = {}
for _ in range(M):
    x,y,z = map(int,input().split())
    if x not in G:
        G[x]=[]
    G[x].append(y)
    if y not in G:
        G[y]=[]
    G[y].append(x)
cnt = N-len(G)
hist = {i:0 for i in G.keys()}
A = list(hist.keys())
while A:
    s = A[0]
    hist[s]=1
    A.remove(s)
    col(s)
    cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
def col(i):
    for x in G[i]:
        if x in hist and hist[x]==0:
            hist[x]=1
            col(x)
N,M = map(int,input().split())
G = {}
for _ in range(M):
    x,y,z = map(int,input().split())
    if x not in G:
        G[x]=[]
    G[x].append(y)
    if y not in G:
        G[y]=[]
    G[y].append(x)
cnt = N-len(G)
while G:
    hist = {i:0 for i in G.keys()}
    s = list(G.keys())[0]
    hist[s]=1
    col(s)
    for i in hist.keys():
        if hist[i]==1:
            del G[i]
    cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
def col(i):
    for x in G[i]:
        if hist[x]==0:
            hist[x]=1
            col(x)
N,M = map(int,input().split())
G = {}
for _ in range(M):
    x,y,z = map(int,input().split())
    if x not in G:
        G[x]=[]
    G[x].append(y)
    if y not in G:
        G[y]=[]
    G[y].append(x)
cnt = N-len(G)
while G:
    hist = {i:0 for i in G.keys()}
    s = list(G.keys())[0]
    hist[s]=1
    col(s)
    for i in hist.keys():
        if hist[i]==1:
            del G[i]
    cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(200000)

n,m,*l=map(int,open(0).read().split())
graph=[[]*n for _ in range(n)]
unvis=[True]*n

@lru_cache(maxsize=None)
def dfs(x):
	for y in graph[x]:
		if unvis[y]:
			unvis[y]=False
			dfs(y)
			
for i,j in zip(l[::3],l[1::3]):
	graph[i-1].append(j-1)
	graph[j-1].append(i-1)

ans=0
for x in range(n):
	if unvis[x]:
		unvis[x]=False
		dfs(x)
		ans+=1
print(ans)