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:
class UnionFind:
    def __init__(self, n):
        self.p = [i for i in range(n)]

    def root(self, x):
        if self.p[x] == x:
            return x
        else:
            self.p[x] = self.root(self.p[x])
            return self.p[x]
    
    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y: self.p[x] = y
    
    def same(self, x,y):
        return (self.root(x) == self.root(y))

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

UF = UnionFind(N)

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

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

print(len(S))

Submission status: Runtime Error

Solution code:
from collections import deque
n,m = map(int, input().split())

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

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

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

print(cnt)

Submission status: Runtime Error

Solution code:
from collections import deque

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

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

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


count=0

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

print(count)

Submission status: Runtime Error

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

class UnionFind():
    def __init__(self, n):
        self.li = list(range(n))
    def root(self, x):
        if self.li[x]==x:
            return x
        self.li[x] = self.root(self.li[x])
        return self.li[x]
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx==ry:
            return
        self.li[ry] = rx
    def same(self, x, y):
        return self.root(x)==self.root(y)

uf = UnionFind(n)
for x, y in xy:
    uf.unite(x, y)
for i in range(n):
    uf.root(i)
print(len(set(uf.li)))

Submission status: Runtime Error

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

for _ in range(M):
    a, b, z = map(int, input().split())
    paths[a-1].append(b-1)
    paths[b-1].append(a-1)

visited = [False] * N

def dfs(node, prev):
    if visited[node]:
        return
    visited[node] = True
    for n in paths[node]:
        if n != prev:
            dfs(n, node)
count = 0
for i in range(N):
    if visited[i] == False:
        count += 1
        dfs(i,-1)

print(count)

Submission status: Runtime Error

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

ans, find = 0, set([])
for x, y, z in xyz:
    if not (x or y) in find:
        ans += 1
    find.add(x)
    find.add(y)
print(ans + (n - len(find)))

Submission status: Runtime Error

Solution code:
class uf():
    def __init__(self,n):
        self.n=n
        self.pa=[-2]*n
    def find(self,x):
        if self.pa[x]<-1:
            return x
        else:
            self.pa[x]=self.find(self.pa[x])
            return self.pa[x]
    def unite(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if x==y:
        	return True
        else:
            if self.pa[x]>self.pa[y]:
                x,y=y,x
            self.pa[x]+=y
            self.pa[y]=x
            return True
    def same(self,x,y):
        return self.find[x]==find.pa[y]
    def size(self,x):
        return -self.pa[self.find(x)] 
n,m=map(int,input().split())
import sys
input=sys.stdin.readline
uf=uf(n)
for _ in range(m):
    a,b,c=map(int,input().split())
    uf.unite(a-1,b-1)
memo=set([])
for i in range(n):
    memo.add(uf.find(i))
print(len(memo))

Submission status: Runtime Error

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

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

seen = [0 for i in range(n)]

def dfs(i):
    for nec in g[i]:
        if seen[nec]!=0:continue
        seen[nec]=1
        dfs(nec)

cnt = 0
for i in range(n):
    if seen[i] == 0:
        seen[i] = 1
        dfs(i)
        cnt+=1

print(cnt)

Submission status: Runtime Error

Solution code:
import union_find as uf
N,M=map(int,input().split())
uni=uf.UnionFind(N)
L=[]
for i in range(M):
    l=list(map(int,input().split()))
    L.append(l)
for i in range(M):
    uni.Unite(L[i][0],L[i][1])
x=-1
for i in range(N+1):
    if uni.root[i]<0:
        x+=1
print(x)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, M: int, X: "List[int]", Y: "List[int]", Z: "List[int]"):
    par = list(range(N))

    def getpar(n: int):
        if par[n] == n:
            return n
        par[n] = getpar(par[n])
        return par[n]

    def union(a: int, b: int):
        par[getpar(b)] = par[getpar(a)]

    for Xi, Yi in zip(X, Y):
        Xi -= 1
        Yi -= 1
        union(Xi, Yi)

    print(len({getpar(i) for i in range(N)}))


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:
def update(v):
    for nv in con[v]:
        if seen[nv]:
            continue
        seen[nv]=1
        update(nv)

N,M=map(int,input().split())
seen=[0]*N
con=[[] for i in range(N)]
cnt=[[i,0] for i in range(N)]
for i in range(M):
    X,Y,Z=map(int,input().split())
    X,Y=X-1,Y-1
    con[X].append(Y)
    con[Y].append(X)
    cnt[X][1]+=1
    cnt[Y][1]+=1
cnt.sort(key=lambda x:x[1],reverse=True)
ans=0
for i,a in cnt:
    if(seen[i]):
        continue
    ans+=1
    seen[i]=1
    update(i)
print(ans)

Submission status: Runtime Error

Solution code:
import networkx as nx

G = nx.Graph()

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

G.add_nodes_from(range(1, N + 1))
for _ in range(M):
    x, y, z = map(int, input().split())
    G.add_edge(y, z)

cnt = 0
for c in  nx.connected_components(G):
        cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

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

#初期値が0の辞書
from collections import defaultdict
xyz = defaultdict(lambda: set([]))
for _ in range(m):
    x,y,z=map(int,input().split())
    xyz[x].add(y)
    xyz[y].add(x)

no_checked=[0]*n

def DFS(x):
    global no_checked
    global xyz
    no_checked[x-1]=1
    for item in xyz[x]:
        if no_checked[item-1]==0:
            DFS(item)

cnt=0
for i in range(1,n+1):
    if no_checked[i-1]==0:
        cnt+=1
        DFS(i)

    #print(i,no_checked)
print(cnt)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

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

#初期値が0の辞書
from collections import defaultdict
xyz = defaultdict(lambda: set([]))
for _ in range(m):
    x,y,z=map(int,input().split())
    xyz[x].add(y)
    xyz[y].add(x)

no_checked=[0]*n

def DFS(x):
    global no_checked
    global xyz
    no_checked[x-1]=1
    for item in xyz[x]:
        if no_checked[item-1]==0:
            DFS(item)

cnt=0
for i in range(1,n+1):
    if no_checked[i-1]==0:
        cnt+=1
        DFS(i)

    #print(i,no_checked)
print(cnt)

Submission status: Runtime Error

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

#初期値が0の辞書
from collections import defaultdict
xyz = defaultdict(lambda: set([]))
for _ in range(m):
    x,y,z=map(int,input().split())
    xyz[x].add(y)
    xyz[y].add(x)

no_checked=[0]*n

def DFS(x):
    global no_checked
    global xyz
    no_checked[x-1]=1
    for item in xyz[x]:
        if no_checked[item-1]==0:
            DFS(item)

cnt=0
for i in range(1,n+1):
    if no_checked[i-1]==0:
        cnt+=1
        DFS(i)

    #print(i,no_checked)
print(cnt)

Submission status: Runtime Error

Solution code:
import math
import operator as op
from functools import reduce
from fractions import Fraction as frac

def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer / denom
def rd(p):
    if(p==0):
        return input()
    if(p==1):
        return int(input())
    if(p==2):
        return map(int,input().split())
    if(p==3):
        return list(map(int,input().split()))
        

# t=rd(1)
def find(u,par):
    if(par[u]<0):
        return u
    else:
        return find(par[u],par)
def uni(x,y,par):
    u=find(x,par)
    v=find(y,par)
    if(par[u]<par[v]):
        par[u]+=par[v]
        par[v]=u
        
    else:
        par[v]+=par[u]
        par[u]=v
t=1
for term in range(1,t+1):
    n,m=rd(2)
    par=[-1 for i in range(n+1)]
    
    
    for i in range(m):
        x,y,z=rd(2)
        uni(x,y,par)
    ans=0
    for i in range(1,n+1):
        if(par[i]<0):
            ans+=1
    print(ans)

Submission status: Runtime Error

Solution code:
import math
import operator as op
from functools import reduce
from fractions import Fraction as frac

def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer / denom
def rd(p):
    if(p==0):
        return input()
    if(p==1):
        return int(input())
    if(p==2):
        return map(int,input().split())
    if(p==3):
        return list(map(int,input().split()))
        

# t=rd(1)
def find(u,par):
    if(par[u]<0):
        return u
    else:
        return find(par[u],par)
def uni(x,y,par):
    u=find(x,par)
    v=find(y,par)
    if(par[u]<par[v]):
        par[u]+=par[v]
        par[y]=u
        
    else:
        par[v]+=par[u]
        par[x]=v
t=1
for term in range(1,t+1):
    n,m=rd(2)
    par=[-1 for i in range(n+1)]
    
    
    for i in range(m):
        x,y,z=rd(2)
        uni(x,y,par)
    ans=0
    for i in range(1,n+1):
        if(par[i]<0):
            ans+=1
    print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
    
root=[int(i) for i in range(n)] 
rank=[0]*n    
def find(x):
    if root[x]==x:
        return x 
    else:
        return find(root[x])

for i in range(m):
    x,y,z=map(int,input().split())
    fx=find(x-1)
    fy=find(y-1)
    if rank[fx]>=rank[fy]:
        root[fy]=fx
        if rank[fx]==rank[fy]:
            rank[fx]+=1
    else:
        root[fx]=fy 
a=()
for i in range(n):
    a.add(find(i)) 
print(len(a))

Submission status: Runtime Error

Solution code:
import networkx as nx

n, m = map(int, input().split())
g = nx.Graph()
g.add_nodes_from(range(1, n+1))
for i in range(m):
    x, y, z = map(int, input().split())
    g.add_edge(x, y)
print(nx.number_connected_components(g))

Submission status: Runtime Error

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

import numpy as np

arr = np.zeros([N+1,M] ,dtype=int)

for i in range(M):
    x, y, z = list(map(int, input().split()))
    arr[x-1, i] = 1
    arr[y-1, i] = 1
    arr[-1, i ] = z % 2
ml = 0
for j in range(M):
    ml_flag = True
    for i in range(j, N):
        #print(arr[i][j])
        if i == 0 and j == 2:
            import IPython;IPython.embed()
        if arr[i][j] != 0:
            min_i = i
            ml_flag = False
            #print("i,j", i, j, "break")
            break
    if ml_flag:
        ml += 1
    for i in range(min_i+1, N):
        #print("yay")
        #print("arr", arr)
        if arr[i][j] != 0:
            arr[i] = (arr[i] + arr[min_i]) % 2

print(N - M + ml)

Submission status: Runtime Error

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

def union(x,y):
    x,y = find(x),find(y)
    if x == y:
        return
    par[y] = x

n,m = map(int,input().split())
par = {i:i for i in range(1,n+1)}
for _ in range(m):
    a,b,c = map(int,input().split())
    union(a,b)
print(len(set(par.values()))

Submission status: Runtime Error

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

G = [[] for _ in range(N + 1)]
for el in XYZ:
    x, y, z = el
    G[x].append(y)
    G[y].append(x)

seen=[False] * (N + 1)
def dfs(parent):
    seen[parent] = True
    for child in G[parent]:
        if seen[child] == False:
            dfs(child)

cnt = 0
for start in range(1, N + 1):
    if seen[start] == False:
        dfs(start)
        cnt += 1
print(cnt)

Submission status: Runtime Error

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

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

visited = [False for _ in range(n)]


def dfs(v, p):
    for u in tree[v]:
        if u == p:
            continue
        if visited[u]:
            continue
        else:
            visited[u] = True
            dfs(u, v)


res = 0
for i in range(n):
    if not visited[i]:
        dfs(i, -1)
        res += 1
print(res)

Submission status: Runtime Error

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

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

G=[[] for _ in range(N+1)]
for el in XYZ:
    G[el[0]].append(el[1])
    G[el[1]].append(el[0])
#print(G)

not_seen=list(range(1,N+1))
todo=queue.Queue()
def dfs(n):
    if n in not_seen:
        not_seen.remove(n)
    for nxt in G[n]:
        if nxt in not_seen:
            todo.put(nxt)
    if todo.empty():
        return None
    else:
        dfs(todo.get())


cnt=0
while not_seen:
    cnt+=1
    dfs(not_seen[0])
print(cnt)
import queue
import sys
sys.setrecursionlimit(10**6)

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

G=[[] for _ in range(N+1)]
for el in XYZ:
    G[el[0]].append(el[1])
    G[el[1]].append(el[0])
#print(G)

not_seen=list(range(1,N+1))
todo=queue.Queue()
def dfs(n):
    if n in not_seen:
        not_seen.remove(n)
    for nxt in G[n]:
        if nxt in not_seen:
            todo.put(nxt)
    if todo.empty():
        return None
    else:
        dfs(todo.get())


cnt=0
while not_seen:
    cnt+=1
    dfs(not_seen[0])
print(cnt)

Submission status: Runtime Error

Solution code:
import queue

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

G=[[] for _ in range(N+1)]
for el in XYZ:
    G[el[0]].append(el[1])
    G[el[1]].append(el[0])
#print(G)

seen=[False]*(N+1)
todo=queue.Queue()
def dfs(n):
    seen[n]=True
    for nxt in G[n]:
        if seen[nxt]==False:
            todo.put(nxt)
    if todo.empty():
        return None
    else:
        dfs(todo.get())


cnt=0
for check in range(1, N+1):
    if seen[check]==False:
        cnt+=1
        dfs(check)
print(cnt)

Submission status: Runtime Error

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

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

seen = [False]*(N)
ans = 0
def dfs(v):
    if seen[v]:
        return
    seen[v] = True
    for nv in G[v]:
        dfs(nv)

for v in range(N):
    if not seen[v]:
        dfs(v)
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
def f(j):
  nodes[j]=1
  for k in links[j]:
    if nodes[k]==0:
      f(k)

N, M=map(int, input().split())
XYZ=[list(map(int, input().split())) for _ in range(M)]
links=[[] for _ in range(N+1)]
for i in range(M):
  links[XYZ[i][0]].append(XYZ[i][1])
  links[XYZ[i][1]].append(XYZ[i][0])
  
nodes=[0]*(N+1)
ans=0
for i in range(1, N+1):
  if nodes[i]==0:
    ans+=1
    nodes[i]=1
    for j in links[i]:
      f(j)
      
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys


class Node:
    def __init__(self, index):
        self.index = index
        self.ref = []
        self.visited = False

    def append(self, node):
        self.ref.append(node)
        node.ref.append(self)

    def visit(self):
        self.visited = True
        for r in self.ref:
            if not r.visited:
                r.visit()


def solve(N: int, M: int, X: "List[int]", Y: "List[int]", Z: "List[int]"):
    nodes = [Node(i) for i in range(N)]
    X = [x-1 for x in X]
    Y = [y-1 for y in Y]
    for i in range(M):
        nodes[X[i]].append(nodes[Y[i]])
    sum = 0
    for i in range(N):
        if not nodes[i].visited:
            sum += 1
            nodes[i].visit()
    print(sum)
    return


# Generated by 1.1.6 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:
N,M=map(int,input().split())

class UnionFind:
  def __init__(self, n):
    self.n = n
    self.parents = [i for i in range(n)]
 
  def find(self, x):
    if self.parents[x]==x:
      return x
    self.parents[x] = self.find(self.parents[x])
    return self.parents[x]
 
  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x == y:
      return
    if self.size(x) < self.size(y):
      x, y = y, x
    self.parents[x] += self.parents[y]
    self.parents[y] = x
    
  def size(self, x):
    return self.parents[self.find(x)]
  
  def cnt(self):
    par=self.parents
    return len(set(par))

uf=UnionFind(N)
for i in range(M):
  x,y,z=map(int,input().split())
  uf.union(x-1,y-1)
print(uf.cnt())

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

# scipy version

import sys
from collections import deque
from array import array

import numpy

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components

def input():
    return sys.stdin.readline().rstrip('\n')

##### main

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

#C = [[0]*N for _ in range(N)]
#
#for i in range(M):
#    a,b,c = list(map(int, input().split()))
#    C[a-1][b-1] = c

R = numpy.full(N, 0, dtype=numpy.int32)
C = numpy.full(N, 0, dtype=numpy.int32)
V = numpy.full(N, 0, dtype=numpy.int32)

for i in range(M):
    r,c,v = list(map(int, input().split()))
    R[i] = r-1
    C[i] = c-1
    V[i] = v

matrix = csr_matrix((V,(R,C)), shape=(N,N))

n = connected_components(matrix, directed=False, return_labels=False)

print(n)

Submission status: Runtime Error

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

def dfs(s):
    if visited[s]:
        return
    visited[s] = 1
    for to in t[s]:
        if visited[to]:
            continue
        dfs(to)
    
N, M = map(int,input().split())
t = [[] for _ in range(N)]
visited = [0] * N
for _ in range(M):
    X, Y, Z = map(int,input().split())
    X -= 1
    Y -= 1
    t[X].append(Y)
    t[Y].append(X)
ans = 0
for i in range(1, N + 1):
    if visited[i]:
        continue
    ans += 1
    dfs(i)
print(ans)

Submission status: Runtime Error

Solution code:
def dfs(s):
    if visited[s]:
        return
    visited[s] = 1
    for to in t[s]:
        if visited[to]:
            continue
        dfs(to)
    
N, M = map(int,input().split())
t = [[] for _ in range(N)]
visited = [0] * N
for _ in range(M):
    X, Y, Z = map(int,input().split())
    X -= 1
    Y -= 1
    t[X].append(Y)
    t[Y].append(X)
for i in range(1, N + 1):
    s = visited.index(0)
    dfs(s)
    if min(visited):
        ans = i
        break
print(ans)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
U=[i for i in range(N)]
def root(i):
    if U[i]==i:
        return i
    else:
        return root(U[i])
def union(i, j):
    if root(i)==root(j):
        return
    else:
        U[root(i)]=root(j)
        return
for i in range(M):
    X,Y,Z=map(int,input().split())
    union(Y-1,X-1)
a=set()
for u in U:
    a.add(u)
print(len(a))

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n,m=map(int,input().split())
    G=[[] for _ in range(n)]
    for _ in range(m):
        x,y,z=map(int,input().split())
        x-=1
        y-=1
        G[x].append(y)
        G[y].append(x)
    
    visited=[True]*n
    def dfs(i):
        visited[i]=False
        for e in G[i]:
            if visited[e]:
                dfs(e)
    
    cnt=0
    for i in range(n):
        if visited[i]:
            cnt+=1
            dfs(i)
    
    print(cnt)  

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n,m=map(int,input().split())
    G=[[] for _ in range(n)]
    for _ in range(m):
        x,y,z=map(int,input().split())
        x-=1
        y-=1
        G[x].append(y)
        G[y].append(x)
    
    visited=[True]*n
    def dfs(i):
        for e in G[i]:
            if visited[e]:
                visited[e]=False
                dfs(e)
    
    cnt=0
    for i in range(n):
        if visited[i]:
            cnt+=1
            dfs(i)
    
    print(cnt)  

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    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)
    
    visited=[True]*n
    def dfs(i):
        for e in G[i]:
            if visited[e]:
                visited[e]=False
                dfs(e)
    
    cnt=0
    for i in range(n):
        if visited[i]:
            cnt+=1
            dfs(i)
    
    print(cnt)  

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
 
n,m = map(int,input().split())
 
#Union Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

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

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#初期化
#根なら-size,子なら親の頂点
par = [-1]*n

###具体例###
for _ in range(m):
    x, y, z = [int(x) for x in input().split()]
    unite(x - 1, y - 1)

A = {}

for i in range(n):
    A.add(find(i))

print(len(A))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
edges = [[] for _ in range(N)]
for _ in range(M):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    edges[x].append(y)
    edges[y].append(x)

visited = [False] * N

def dfs(u):
    if visited[u]:
        return

    visited[u] = True
    for v in edges[u]:
        if visited[v]:
            continue
        dfs(v)

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

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
import sys

sys.setrecursionlimit(10**5)

def dfs(num,log):
    visited[num]=min(log,visited[num])
    for item in way[num]:
        if visited[item]==10**7:
            dfs(item,log)
    return 

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

visited=[10**7]*N
way=[[] for i in range(N)]
order=[]

for _ in range(M):
    X,Y,Z=map(int,input().split())
    X,Y=min(X,Y),max(X,Y)
    order.append([X-1,Y-1,Z])

order.sort(key=lambda x:(x[0],x[1]))

for item in order:
    way[item[0]].append(item[1])
    way[item[1]].append(item[0])
    
for i in range(N):
    dfs(i,i)

visited=list(set(visited))
print(len(visited))

Submission status: Runtime Error

Solution code:
import sys

# 再帰上限の変更(デフォルトは1000)
sys.setrecursionlimit(10 ** 20)

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

# XがわかればYがわかるので、あるAiがわかったときどこまでわかるか?をグラフにしてDFSで探索

graph = [[]for i in range(N + 1)]

seen = [0] * (N + 1)

for X, Y, Z in XYZ:
    graph[X].append(Y)
    graph[Y].append(X)


def dfs(a):
    if seen[a] == 1:
        return
    else:
        seen[a] = 1
        for i in graph[a]:
            dfs(i)


ans = 0

for i in range(1, N + 1):
    if seen[i] == 1:
        continue
    else:
        dfs(i)
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
import sys

# 再帰上限の変更(デフォルトは1000)
sys.setrecursionlimit(10 ** 100)

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

# XがわかればYがわかるので、あるAiがわかったときどこまでわかるか?をグラフにしてDFSで探索

graph = [[]for i in range(N + 1)]

seen = [0] * (N + 1)

for X, Y, Z in XYZ:
    graph[X].append(Y)
    graph[Y].append(X)


def dfs(a):
    if seen[a] == 1:
        return
    else:
        seen[a] = 1
        for i in graph[a]:
            dfs(i)


ans = 0

for i in range(1, N + 1):
    if seen[i] == 1:
        continue
    else:
        dfs(i)
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
from sys import setrecursionlimit

# 再帰上限の変更(デフォルトは1000)
setrecursionlimit(10 ** 100)

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

# XがわかればYがわかるので、あるAiがわかったときどこまでわかるか?をグラフにしてDFSで探索

graph = [[]for i in range(N + 1)]

seen = [0] * (N + 1)

for X, Y, Z in XYZ:
    graph[X].append(Y)
    graph[Y].append(X)


def dfs(a):
    if seen[a] == 1:
        return
    else:
        seen[a] = 1
        for i in graph[a]:
            dfs(i)


ans = 0

for i in range(1, N + 1):
    if seen[i] == 1:
        continue
    else:
        dfs(i)
        ans += 1

print(ans)

Submission status: Runtime Error

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

graph = [[]for i in range(N + 1)]

seen = [0] * (N + 1)

for X, Y, Z in XYZ:
    graph[X].append(Y)
    graph[Y].append(X)


def dfs(a):
    if seen[a] == 1:
        return
    else:
        seen[a] = 1
        for i in graph[a]:
            dfs(i)


ans = 0

for i in range(1, N + 1):
    if seen[i] == 1:
        continue
    else:
        dfs(i)
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
adj = [[] for _ in range(m)]
for _ in range(m):
  x, y, z = map(int, input().split())
  adj[x-1].append(y-1)
  adj[y-1].append(x-1)
opn = [True] * n
count = 0
for i in range(n):
  if opn:
    count += 1
    opn[i] = False
    stack = [i]
    while stack:
      u = stack.pop()
      for v in adj[u]:
        if opn[v]:
          stack.append(v)
          opn[v] = False
print(count)

Submission status: Runtime Error

Solution code:
class union_find():
  def __init__(self,n):
    self.n=n
    self.parents=[-1]*n
  def find(self,x):
    if self.parents[x]<0:
      return x
    else:
      self.parents[x]=self.find(self.parents[x])
      return self.parents[x]
  def union(self,x,y):
    x=self.find(x)
    y=self.find(y)
    if x==y:
      return 
    if self.parents[x]>self.parents[y]:
      x,y=y,x
    self.parents[x]+=self.parents[y]
    self.parents[y]=x
    
def main():
  N,M=map(int,input().split())
  box=union_find(N)
  for i in range(M):
    x,y,z=map(int,input().split())
    box.union(x,y)
  box.find(1)
  ans=0
  for i, x in enumerate(box.parents):
    if x<0:
      ans+=1
  print(ans)
main()

Submission status: Runtime Error

Solution code:
class UnionFind():
  def __init__(self, n):
    self.par = [i for i in range(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]
  
  def unite(self, x, y):
    x = self.root(x)
    y = self.root(y)
    self.par[y] = x

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

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

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

ans = set()
for i in range(N):
  ans.add(uf.root(i))
print(len(ans))

Submission status: Runtime Error

Solution code:
import sys

n, m, *xyz = map(int, sys.stdin.read().split())
xyz = zip(*[iter(xyz)] * 3)

root = list(range(n+1))
height = [0] * (n + 1)

def find_root(v):
    u = root[v]
    if u == v:
        return u
    w = find_root(u)
    root[v] = w
    return w

def unite(u, v):
    ru = find_root(u)
    rv = find_root(v)
    if ru == rv:
        return
    if height[u] >= height[v]:
        root[rv] = ru
        height[ru] = max(height[ru], height[rv] + 1)
    else:
        root[ru] = rv

def main():
    for x, y, z in xyz:
        unite(x, y)
    
    for i in range(1, n+1):
        find_root(i)

    return len(set(root[1:]))

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