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: Wrong Answer

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

items = []
visible = set()

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


def f(num):
    know = set()
    cnt = 0
    for x, y, z in items:
        if x in know:
            know.add(y)
            continue
        elif y in know:
            know.add(x)
            continue
        else:
            cnt += 1
            know.add(x)
            know.add(y)
    cnt += N - len(know)
    if cnt <= num:
        return True
    else:
        return False


ok = N
ng =0

while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if f(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Wrong Answer

Solution code:
def main():
    n, m = map(int, input().split())
    a = []
    count = 0
    for i in range(m):
        x, y, z = map(int, input().split())
        if (x not in a) and (y not in a):
            count += 1
        if x not in a:
            a.append(x)
        if not y in a:
            a.append(y)

    print(n - count)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
l = [list(map(int,input().split())) for _ in range(m)]
g = {}
for i in range(1,n+1):
    g[i] = []
for x,y,z in l:
    g[x].append(y)

def connected_components(graph):
    seen = set()
    def component(n):
        nodes = set([n])
        while nodes:
            n = nodes.pop()
            seen.add(n)
            nodes |= set(graph[n]) - seen
            yield n
    for n in graph:
        if n not in seen:
            yield component(n)

def print_gen(gen):
    a = [list(x) for x in gen]
    print(len(a))

print_gen(connected_components(g))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
X = []
Y = []

for _ in range(M):
    xt, yt, __ = map(int, input().split())
    X.append(xt)
    Y.append(yt)

per = [-1] * (N + 1)


def get(i):
    if per[i] == -1:
        return i
    else:
        per[i] = get(per[i])
        return get(per[i])


def union(x, y):
    xp = get(x)
    yp = get(y)
    if xp == yp:
        return 0;
    else:
        per[x] = get(y)


for i in range(M):
    union(X[i], Y[i])

print(per.count(-1) - 1)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
s = [input().split() for i in range(m)]
li = [[s[0][0],s[0][1]]]
del s[0]
for item in s:
  num_1 = item[0]
  num_2 = item[1]
  for group in li:
    if num_1 in group and num_2 in group:
      flag=0
      pass
      break
    elif num_1 in group:
      group.append(num_2)
      flag=0
      break
    elif num_2 in group:
      group.append(num_1)
      flag=0
      break
    else:
      flag = 1
  if flag:
    li.append([num_1,num_2])
count = 0
for j in li:
  count += len(j)-1
print(n-count)

Submission status: Wrong Answer

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

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

info_lst = []
constrain = M
for i in range(M):
  if (X[i][0] in info_lst) and (X[i][1] in info_lst):
    constrain -= 1
  else:
    if (X[i][0] not in info_lst):
      info_lst.append(X[i][0])
    if (X[i][1] not in info_lst):
      info_lst.append(X[i][1])
      
ans = min(N - constrain, 1)
print(ans)

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import math
import re

def main(params):
    n = int(params[0])
    m = int(params[1])
    xyz = params[2:]
    results = {}
    tmp = {}
    for i in xyz:
        x,y,z = i.split()
        x = int(x)
        y = int(y)
        z = int(z)
        if x in results and y in results:
            if results[x] != results[y]:
                tx = results[x]
                ty = results[y]
                for i in  tmp[tx]:
                    results[i] = ty
                tmp[ty].extend(tmp[tx])
        elif x not in results and y in results:
            results[x] = results[y]
            tmp[results[y]] = [x]
        elif x in results and y not in results:
            results[y] = results[x]
            tmp[results[x]] = [y]
        elif x not in results and y not in results:
            results[x] = x
            results[y] = x
            tmp[x] = [x,y]
    t = {}
    for i in range(n):
        if i+1 in results:
            t[results[i+1]] = 1
        else:
            t[i+1] = 2
    print len(t)

if __name__ == "__main__":
    n,m = raw_input().split()
    n = int(n)
    m = int(m)
    cnt = m # TODO: edit here
    params = [n,m]
    for i in range(cnt):
        param = raw_input()
        params.append(param)
    main(params)

Submission status: Wrong Answer

Solution code:
import sys

#Union Find

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

#xとyの属する集合の併合
def unite(x,y,par,rank):
    x = find(x,par)
    y = find(y,par)
    
    if x != y:
        #xとyの属している集合が異なる時
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x]==rank[y]:
                rank[x] += 1

#xとyが同じ集合に属するかの判定
def same(x,y,par):
    return find(x,par) == find(y,par)
    
input = sys.stdin.readline
n,k = map(int,input().split())
rpar = [] #親
#tpar = []
rrank = [0]*n#木の深さ
#trank= [0]*n

#初期化
for i in range(n):
    #par[i]:i rank[i]:0
    rpar.append(i)
    #tpar.append(i)


for i in range(k):
    x,y,odd = map(int,input().split())
    unite(x-1,y-1,rpar,rrank)

import collections
c = collections.Counter(rpar)
clist = c.values()
values, counts = zip(*c.most_common())
#print(rpar,rrank)
print(n-sum(counts)+len(counts))

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
l = [list(map(int,input().split())) for _ in range(m)]
g = {}
for i in range(1,n+1):
    g[i] = []
for x,y,z in l:
    g[x].append(y)

def connected_components(graph):
    seen = set()
    def component(n):
        nodes = set([n])
        while nodes:
            n = nodes.pop()
            seen.add(n)
            nodes |= set(graph[n]) - seen
            yield n
    for n in graph:
        if n not in seen:
            yield component(n)

def print_gen(gen):
    a = [list(x) for x in gen]
    print(len(a))

print_gen(connected_components(g))

Submission status: Wrong Answer

Solution code:
N,M=list(map(int,input().split()))
hoge=[]
total=0
for i in range(M):
    tmp=list(map(int,input().split()))
    if (tmp[0] in hoge) and (tmp[1] in hoge):
        pass
    elif (tmp[0] in hoge):
        hoge.append(tmp[1])
    elif(tmp[1] in hoge):
        hoge.append(tmp[0])
        
    else:
        hoge.append(tmp[1])
        hoge.append(tmp[0])
        total+=1
print(total+N-len(hoge))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = []
count = 0
for i in range(m):
    x, y, z = map(int, input().split())
    if (x not in a) and (y not in a):
        count += 1
    if x not in a:
        a.append(x)
    if not y in a:
        a.append(y)

print(n-count)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
lst=[]
for i in range(m):
  x,y,z=map(int,input().split())
  lst.append((x,y))
l=[0]*n
ans=n-1
check=[]
for i in range(m):
  a,b=lst[i]
  if l[a-1]==0 and l[b-1]==0:
    l[a-1]=1
    l[b-1]=1
  elif l[a-1]==1 and l[b-1]==1:
    ans-=2
  else:
    ans-=1
print(ans)

Submission status: Wrong Answer

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

n = int(n)
m = int(m)

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

cluster = [i for i in range(n)]

for x, y, z in xyz:
    x -= 1
    y -= 1
    if cluster[x] < cluster[y]:
        cluster[y] = cluster[x]
    else:
        cluster[x] = cluster[y]

count_flip = 0
before_v = -1
for v in cluster:
    if before_v < v:
        count_flip += 1
        before_v = v

print(count_flip)

Submission status: Wrong Answer

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

N,M = [int(i) for i in input().split()]
l = [[] for _ in range(N)]
ans = set()
for i in range(M):
    x,y,_ = [int(j)-1 for j in input().split()]
    while len(l[x]) != 0:
        x = l[x][0]
    ans.add(x)
    l[y].append(x)

print(len(ans))

Submission status: Wrong Answer

Solution code:

# coding: utf-8

# In[26]:

import sys
#import numpy as np
input = sys.stdin.readline
N, M = map(int, input().split())
#hint = np.array([list(map(int, input().split())) for i in range(M)])
hint = [list(map(int, input().split())) for i in range(M)]


# In[32]:

#hint


# In[48]:

so = N
syugo = []
for i in range(M):
    x_flag = False
    y_flag = False
    x, y = hint[i][:2]
    for i, s in enumerate(syugo):
        if x in s:
            x_flag = True
            x_i = i
        if y in s:
            y_flag = True
            y_i = i
    if x_flag and y_flag:
        syugo[x_i] = syugo[x_i] | syugo[y_i]
        syugo.pop(y_i)
        so -= 1
    elif x_flag:
        syugo[x_i] = syugo[x_i] | set([x, y])
        so -= 1
    elif y_flag:
        syugo[y_i] = syugo[y_i] | set([x, y])
        so -= 1
    else:
        syugo.append(set([x, y]))
        so -= 2


# In[49]:

#zen = set(range(1, N+1))
#print(len(zen.difference(*syugo)) + len(syugo))
print(so+ len(syugo))
#print(so)
#print(syugo)


# In[ ]:

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math

mod = 10**9+7

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

info = list(map(list,set(map(tuple,info))))

info = sorted(info,key=lambda x:x[2])

used = []
ans = N
for i in range(len(info)):
    x,y,z = info[i]
    if x in used and y in used and z in used:
        pass
    else:
        ans -= 1
        used += list(set([x,y,z]))

print(ans)

Submission status: Wrong Answer

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

sets=[]
i=0
x=A[i][0]
y=A[i][1]
sets.append(set([x,y]))

for i in range(1,M):
    x=A[i][0]
    y=A[i][1]
    count=0
    for k,set1 in enumerate(sets):
        if (x in  set1) or (y in set1):
            if count==0:
                set1.add(x)
                set1.add(y)
                count=k
            else:
                sets[count]=sets[count] | sets[k]
                sets.pop(k)
        else:
            sets.append(set([x,y]))
print(sets)

count=0
for j in range(1,N+1):
    for set2 in sets:
        if j in set2:
            count+=1
ans2=N-count
print(ans2)

print(len(sets)+ans2)

Submission status: Wrong Answer

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

if M == 1:
  print(N-M)
else:
  a, b = -1e9, -1e9
  cnt = 0
  for x, y, z in XYZ:
    x -= 1
    y -= 1
    if x == a or y == b or x == b or y == a:
      pass
    elif x != a and y != b:
      cnt += 1
    a = x
    b = y
  print(cnt)

Submission status: Wrong Answer

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

indices = {}
for i in range(n):
    indices[i + 1] = -1

idx = 0
red = 0
for x, y, z in data:
    if indices[x] == -1 and indices[y] == -1:
        indices[x] = idx
        indices[y] = idx
        idx += 1
        red += 1
    elif indices[x] == -1:
        indices[x] = indices[y]
        red += 1
    elif indices[y] == -1:
        indices[y] = indices[x]
        red += 1
    elif indices[x] != indices[y]:
        red += 1
print(n - red)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
u = [0]*M
v = [0]*M
w = [0]*M

for i in range(M):
    u[i], v[i], w[i] = map(int, input().split())

ans = [0]*N
cost = 0

for i in range(M):
    if ans[u[i]-1] == 0 and ans[v[i]-1] == 0:
        cost += 1
        ans[u[i]-1] = cost
        ans[v[i]-1] = cost
    elif ans[u[i]-1] == 0:
        ans[u[i]-1] = ans[v[i]-1]
    elif ans[v[i]-1] == 0:
        ans[v[i]-1] = ans[u[i]-1]
    elif ans[u[i]-1] != ans[v[i]-1]:
        hoge = ans[v[i]-1]
        for j in range(N):
            if ans[j] == hoge:
                ans[j] = ans[u[i]-1]
        cost -= 1

for i in range(N):
    if ans[i] == 0:
        cost += ans[i]

print(cost)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
v = [0 for _ in range(n)]
setnum = 0
for _ in range(m):
    x, y ,z = map(int, input().split())
    if v[x-1] == 0 and v[y-1] == 0:
        setnum += 1
        v[x-1] = setnum
        v[y-1] = setnum
    elif v[x-1] != 0 and v[y-1] != 0:
        v[x-1] = min(v[x-1], v[y-1])
        v[y-1] = min(v[x-1], v[y-1])
        v = [min(v[x-1], v[y-1]) if x == max(v[x-1], v[y-1]) else x for x in v]
    elif v[x-1] != 0 or v[y-1] != 0:
        v[x-1] = max(v[x-1], v[y-1])
        v[y-1] = max(v[x-1], v[y-1])

ans = sum([1 for x in v if x == 0])
ans += len(set([x for x in v if x > 0]))

print(ans)

Submission status: Wrong Answer

Solution code:
from __future__ import print_function
n,m = map(int,input().split())
l = [list(map(int,input().split())) for _ in range(m)]
g = {}
for i in range(1,n+1):
    g[i] = []
for x,y,z in l:
    g[x].append(y)

def connected_components(graph):
    seen = set()
    def component(n):
        nodes = set([n])
        while nodes:
            n = nodes.pop()
            seen.add(n)
            nodes |= set(graph[n]) - seen
            yield n
    for n in graph:
        if n not in seen:
            yield component(n)

def print_gen(gen):
    a = [list(x) for x in gen]
    print(len(a))

print_gen(connected_components(g))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

from copy import copy
import sys
sys.setrecursionlimit(10 ** 6)

def dfs(n):
    stack = copy(graph[n])
    while stack:
        x = stack.pop()
        dfs(x)
    checked[n] = True

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

graph = {i: [] for i in range(N)}
checked = [False for _ in range(N)]

con_com = 0

for _ in range(M):
    x, y, _ = list(map(int, input().split()))
    graph[min(x, y)-1].append(max(x, y)-1)

for i in range(N):
    if checked[i]:
        continue
    dfs(i)
    con_com += 1

print(con_com)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Fri Mar  1 19:29:34 2019

@author: nakamuratakayuki
"""
N, M = tuple(map(int,input().split()))
xyzlist = []
for i in range(M):
    xyzlist.append(tuple(map(int,input().split())))
    
used = set()
setcount = 0
for i in range(M):
    if xyzlist[i][0] in used or xyzlist[i][1] in used:
        pass
    else:
        setcount += 1
    used.add(xyzlist[i][0])
    used.add(xyzlist[i][1])

setcount += N-len(used)
print(setcount)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
s = set([])
for i in range(m):
    x,y,z = map(int,input().split())
    if not(x in s) or not(y in s):
        n-=1
        s.add(x)
        s.add(y)
print(n)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
S = []
kisyutu = []
cnt = 0
for i in range(m):
    aa = list(input().split())
    S.append(aa)
#print(S)
for j in S:
    if j[0] not in kisyutu and j[1] not in kisyutu:
        kisyutu.append(j[0])
        kisyutu.append(j[1])
        cnt += 1
    if j[0] in kisyutu and j[1] not in kisyutu:
        kisyutu.append(j[1])
        cnt += 1
    if j[0] not in kisyutu and j[1] in kisyutu:
        kisyutu.append(j[0])
        cnt += 1
if cnt >= n:
    print(1)
else:
    print(cnt)

Submission status: Wrong Answer

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

def unite(x,y):
    x = find(x)
    y = find(y)
    if x != y:
        if rank[x] < rank[y]:
            root[x] = y
        else:
            root[y] = x
            if rank[x]==rank[y]:
                rank[x] += 1

n,m = map(int,input().split())
root = [0]*n
for i in range(n):
    root[i] = i
rank = [1]*n
size = [1]*n
for i in range(m):
    x,y,z = [int(i)-1 for i in input().split()]
    unite(x,y)
res = set()
for r in root:
    if r not in res:
        res.add(r)
print(len(res)-1)

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, m = na()
li = []
for i in range(m):
    x, y, w = na()
    li.append(x)
print(n - len(set(li)))

Submission status: Wrong Answer

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

items = []
visible = set()

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


def f(num):
    know = set()
    cnt = 0
    for x, y, z in items:
        if x in know:
            know.add(y)
            continue
        elif y in know:
            know.add(x)
            continue
        else:
            cnt += 1
            know.add(x)
            know.add(y)
    cnt += N - len(know)
    if cnt <= num:
        return True
    else:
        return False


ok = N
ng = -1

while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if f(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Wrong Answer

Solution code:

N,M= map(int,input().split())
p=[0]*N

for i in range(M):
    k=list(map(int,input().split()))
    p[k[0]-1]+=1
    p[k[1]-1]+=1
    if p[k[0]-1]==1 or p[k[1]-1]==1 :
        N=N-1
print(N)

Submission status: Wrong Answer

Solution code:
n, m = [int(i) for i in input().split()]
list_check = [0 for i in range(n)]
r_list = []
d_list = []
all_set = set([i + 1 for i in range(n)])
for i in range(m):
    x1, x2, _ = [int(i) for i in input().split()]
    if x1 not in r_list and x1 not in d_list:
        r_list.append(x1)
        d_list.append(x2)
        continue
    elif x1 in d_list and x2 not in r_list:
        d_list.append(x2)
        continue
    elif x2 not in r_list and x2 not in d_list:
        r_list.append(x2)
        d_list.append(x1)
        continue
    elif x2 in d_list and x1 not in r_list:
        d_list.append(x1)
        continue

print(n - len((set(d_list))))

Submission status: Wrong Answer

Solution code:
number = input().split()
xy_list = []

for i in range(int(number[1])):
    xy = input().split()
    xy_list.append(xy)

count = 0
point_one = 0
point_two = 0
point_three = 0
point_four = 0
point_five = 0
point_six = 0
point_seven = 0
point_eight = 0
point_nine = 0
for i in xy_list:
    if i[0] == "1":  
        point_one += 1
    if i[1] == "1":
        point_one += 1
    if i[0] == "2":  
        point_two += 1
    if i[1] == "2":
        point_two += 1
    if i[0] == "3":  
        point_three += 1
    if i[1] == "3":
        point_three += 1
    if i[0] == "4":  
        point_four += 1
    if i[1] == "4":
        point_four += 1
    if i[0] == "5":  
        point_five += 1
    if i[1] == "5":
        point_five += 1
    if i[0] == "6":  
        point_six += 1
    if i[1] == "6":
        point_six += 1
    if i[0] == "7":  
        point_seven += 1
    if i[1] == "7":
        point_seven += 1
    if i[0] == "8":  
        point_eight += 1
    if i[1] == "8":
        point_eight += 1
    if i[0] == "9":  
        point_nine += 1
    if i[1] == "9":
        point_nine += 1
    count += 1
    
answer = int(number[0])

if point_one == 2:
    answer -= 1
if point_two == 2:
    answer -= 1
if point_three == 2:
    answer -= 1
if point_four == 2:
    answer -= 1
if point_five == 2:
    answer -= 1
if point_six == 2:
    answer -= 1
if point_seven == 2:
    answer -= 1
if point_eight == 2:
    answer -= 1
if point_nine == 2:
    answer -= 1

if int(number[1]) == 1:
    print(int(number[0]) - 1)
else:
    print(answer)

Submission status: Wrong Answer

Solution code:
import numpy as np
class WeightedUnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        # 根への距離を管理
        self.weight = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            # 親への重みを追加しながら根まで走査
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y

    # 併合
    def union(self, x, y, w):
        rx = self.find(x)
        ry = self.find(y)
        # xの木の高さ < yの木の高さ
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        # xの木の高さ ≧ yの木の高さ
        else:
            self.par[ry] = rx
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            # 木の高さが同じだった場合の処理
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    # 同じ集合に属するか
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # xからyへのコスト
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]

#####
N, M = map(int, input().split())
uf = WeightedUnionFind(N)
for i in range(M):
    ui, vi, wi = map(int, input().split())
    uf.union(ui, vi, wi)
print(len(np.unique(uf.par[1:])))

Submission status: Wrong Answer

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

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

if N == M:
    print (0)
    sys.exit()

count = 0
dp = [0] * N
for i in range(M):
    if dp[lst[i][0]-1] == 0 and dp[lst[i][1]-1] == 0: #両方初めて出てくる
        count += 1
        dp[lst[i][0]-1] += 1
        dp[lst[i][1]-1] += 1
    elif dp[lst[i][0]-1] == 0 or dp[lst[i][1]-1] == 0: #どちらかが初めて出てくる
        count += 1
        a = max(dp[lst[i][0]-1], dp[lst[i][1]-1])+1
        dp[lst[i][0]-1] = a
        dp[lst[i][1]-1] = a
    else: #両方出てきたことがある-->確定する時
        count -= max(dp[lst[i][0]-1], dp[lst[i][1]-1])

a = dp.count(0)
print (count + a)

Submission status: Wrong Answer

Solution code:
#import collections

n, m = map(int, input().split())
z = []
for i in range(m):
    z.append(list(map(int, input().split())))


c = [0] * (n+1)
d = set()
j = 1
for i in range(m):
    if c[z[i][0]] != 0:
        c[z[i][1]] = c[z[i][0]]
        d.add(z[i][1])
    elif c[z[i][1]] != 0:
        c[z[i][0]] = c[z[i][1]]
        d.add(z[i][0])
    else:
        c[z[i][0]] = j
        c[z[i][1]] = j
        d.add(z[i][0])
        d.add(z[i][1])
        j += 1

#print(d)

for i in range(n):
    if not (i+1 in d):
        c[i+1] = j
        j += 1

#print(c)
print(len(set(c[1:])))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
x=[]
mahou=0
for i in range(M):
  kazu=list(map(int,input().split()))
  iti=kazu[0]
  ni=kazu[1]
  if iti not in x:
    if ni not in x:
      mahou=mahou+1
  x.append(iti)
  x.append(ni)
x_uniq = list(set(x))
card=len(x_uniq)
nokori=N-card
kotae=mahou+nokori
print(kotae)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
X = []
Y = []

for _ in range(M):
    xt, yt, __ = map(int, input().split())
    X.append(xt)
    Y.append(yt)

per = [-1] * (N+1)


def get(i):
    if per[i] == -1:
        return i
    else:
        return get(per[i])


def union(x, y):
    xp = get(x)
    yp = get(y)
    if xp == yp:
        return 0;
    elif xp < yp:
        per[x] = yp
    else:
        per[y] = xp


for i in range(M):
    union(X[i], Y[i])

print(per.count(-1)-1)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
lst=[]
for i in range(m):
  x,y,z=map(int,input().split())
  lst.append((x,y))
lst.sort()
l=[0]*n
ans=n-1
for i in range(m):
  a,b=lst[i]
  if l[a-1]==0 and l[b-1]==0:
    l[a-1]=1
    l[b-1]=1
  else:
    ans-=1
print(ans)

Submission status: Wrong Answer

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

nlist = [0] * N
for i in range(N):
    nlist[i] = i
    
for i in range(M):
    y = XYZ[i][1]-1
    x = XYZ[i][0]-1
    if nlist[y] == y:
        nlist[y] = nlist[x]
    else :
        nlist[x] = nlist[y]
cnt = 0
for i in range(N):
    if nlist[i] == i: cnt += 1
    
print(cnt)

Submission status: Wrong Answer

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

X1 = list(set(X))
Y1 = list(set(Y))

if (len(X1) >= len(Y1)):
    print(N-len(X1))
else:
    print(N-len(Y1))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10 ** 6)

def dfs(n):
    stack = graph[n]
    while stack:
        x = stack.pop()
        dfs(x)
    checked[n] = True

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

graph = {i: [] for i in range(N)}
checked = [False for _ in range(N)]

con_com = 0

for _ in range(M):
    x, y, _ = list(map(int, input().split()))
    graph[min(x, y)-1].append(max(x, y)-1)

for i in range(N):
    if checked[i]:
        continue
    dfs(i)
    con_com += 1

print(con_com)

Submission status: Wrong Answer

Solution code:
import sys


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


# N = int(input())
# A = [int(x) for x in input().split()]
# a, b, c = map(int, input().split())
# name1 = str(input())
# alph = {"A": 1, "B": 2, "C": 3, "D": 4, "E": 5}
# b = list(map(lambda x: math.ceil(x/10)*10, a))

n, m = map(int, input().split())
x = set()
y = set()
for i in range(m):
    a, b, c = map(int, input().split())
    x.add(a)
    y.add(b)
x_y = x - y
xy = x | y
print(len(x_y) + n - len(xy))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A=[-1 for i in range(N)]
costs=0

for i in range(M):
    x,y,z=map(int,input().split())
    if z%2==0:
        if A[x-1]==-1 and A[y-1]==-1:
            A[x-1]=1
            A[y-1]=1
            costs+=1
        elif A[x-1]!=-1 and A[y-1]==-1:
            A[y-1]=A[x-1]
        elif A[x-1]==-1 and A[y-1]!=-1:
            A[x-1]=A[y-1]
    else:
        if A[x-1]==-1 and A[y-1]==-1:
            A[x-1]=1
            A[y-1]=2
            costs+=1
        elif A[x-1]!=-1 and A[y-1]==-1:
            if A[x-1]==1:
                A[y-1]=2
            else:
                A[y-1]=1
        elif A[x-1]==-1 and A[y-1]!=-1:
            if A[y-1]==1:
                A[x-1]=2
            else:
                A[x-1]=1
costs+=A.count(-1)
print(costs)

Submission status: Wrong Answer

Solution code:

if __name__ == '__main__':
    n,m = list(map(int, input().split()))
    nums = [1] * (n+1)
    nums[0] = 0
    count = 0
    for i in range(m):
        x,y,z = list(map(int, input().split()))

        if(nums[x]==1 and nums[y]==1):
            count += 1

        nums[x] = 0
        nums[y] = 0

    count += sum(nums)

    print(count)

Submission status: Wrong Answer

Solution code:
N, M = (int(i) for i in input().split())

res = []
for i in range(M):
    x, y, _ = (int(i) for i in input().split())
    res.append((x, y))

res = sorted(res)

index = 0
result = [0] * N
for tup in res:
    if result[tup[0]-1] == 0:
        index += 1
        result[tup[0]-1] = index
        result[tup[1]-1] = index
    else:
        result[tup[1]-1] = result[tup[0]-1]

pon = index
for hoge in result:
    if hoge == 0:
        pon += 1

print(pon)

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
LX = []
LY = []
for i in range(M):
    X, Y, Z = map(int,input().split())
    LX.append(X)
    LY.append(Y)
AL =[[LX[0],LY[0]]]
for i in range(1,M):
    for j in range(len(AL)):
        if (LX[i] not in AL[j])&(LY[i] in AL[j]):
            AL[j].append(LX[i])
            break
        elif (LY[i] not in AL[j])&(LX[i] in AL[j]):
            AL[j].append(LY[i])
            break
        elif (LX[i] not in AL[j])&(LY[i] not in AL[j]):
            continue
        else:
            break
    if (LX[i] not in AL[len(AL)-1])&(LY[i] not in AL[len(AL)-1]):
        AL.append([LX[i],LY[i]])
P = len(AL)
Q = 0
for i in range(len(AL)):
    Q += len(AL[i])
print(N-Q+P)

Submission status: Wrong Answer

Solution code:
def solve():
    N, M = map(int, input().split())
    
    known = [0]*(N+1)
    cnt = 0
    cnt2 = 0
    
    for _ in range(M):
        x, y, x = map(int, input().split())
        
        if known[x] and known[y]:
            continue
        
        if known[x]:
            cnt2 += 1
            known[y] = 1
            continue
        
        if known[y]:
            cnt2 += 1
            known[x] = 1
            continue
        
        known[x], known[y] = 1, 1
        cnt += 1
        cnt2 += 2
    
    print (N - cnt2 + cnt)
    
if __name__ == "__main__":  
    solve()

Submission status: Wrong Answer

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

X1 = list(set(X))
Y1 = list(set(Y))

if (X1 >= Y1):
    print(N-len(X1))
else:
    print(N-len(Y1))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
E - 1 or 2
https://atcoder.jp/contests/abc126/tasks/abc126_e

"""
import sys


class DisjointSet(object):
    def __init__(self, n):
        self.rank = [0] * n
        self.p = list(range(n))
        self.size = [1] * n

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

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if self.rank[x] > self.rank[y]:
            self.size[self.p[x]] += self.size[self.p[y]]
            self.p[y] = self.findSet(x)
        else:
            self.size[self.p[y]] += self.size[self.p[x]]
            self.p[x] = self.findSet(y)
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def findSet(self, x):
        if x != self.p[x]:
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]


def solve(N, M, hints):
    d = DisjointSet(N+1)
    for x, y, z in hints:
        d.unite(x, y)
    ans = len(set(d.p[1:]))
    return ans



def main(args):
    N, M = map(int, input().split())
    hints = [[int(i) for i in input().split()] for _ in range(M)]
    ans = solve(N, M, hints)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])