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:
# -*- coding: utf-8 -*-


def main():
    from collections import Counter

    n, m = map(int, input().split())
    numbers = list()
    ans = n

    for i in range(m):
        xi, yi, zi = map(int, input().split())
        numbers.append(xi)
        numbers.append(yi)

    for number, count in Counter(numbers).items():
        if count >= 2:
            ans -= 1

    if ans == n:
        ans -= 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import numpy as np

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

known_dict = {}
search_count = 0
for i in range(m):
  w_ary = list(map(int, input().split()))
  if not (w_ary[0] in known_dict or w_ary[1] in known_dict) :
    search_count += 1
  known_dict[w_ary[0]] = "1"
  known_dict[w_ary[1]] = "1"
print(search_count)

Submission status: Wrong Answer

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

"""
import sys


def solve(N, M, hints):
    ans = [True] * (N+1)
    ans[0] = False
    hints.sort()
    for x, y, z in hints:
        ans[y] = False
    return sum(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:])

Submission status: Wrong Answer

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

cards = [0] * n
ans = 0
for i in range(m):
      x,y,z = map(int, input().split())
      if cards[x-1] == 0:
            ans += 1
            cards[x-1] = 1
            cards[y-1] = 1
      elif cards[x-1] == 1:
             cards[y-1] = 1
print(ans+cards.count(0))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
card = set(i for i in range(1,N+1))
ans = N

for i in range(M):
    x,y,z = map(int,input().split())
    if x in card:
        card.remove(x)
        if y in card:
            card.remove(y)
        ans -= 1
    else:
        if y in card:
            card.remove(y)
            ans -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
n,m=[int(i) for i in input().split()]
ls=[]
for i in range(m):
    l=input().split()
    l.pop(2)
    ls.append([int(i) for i in l])

from itertools import chain
count=len(set(range(n+1))-set(chain.from_iterable(ls))-{0})
while len(ls) != 0:
    ls = [i for i in ls if not (i.__contains__(ls[0][0]) or i.__contains__(ls[0][1]))]
    count+=1
print(count)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
edge = [0] *n
count =1
for _ in range(m):
    u, v, _ = map(int, input().split())
    if edge[u-1]==0 and edge[v-1]==0:
        edge[u-1] = count
        edge[v-1] = count
        count +=1
    elif edge[u-1]==0 and edge[v-1]!=0:
        edge[u-1] = edge[v-1]
    elif edge[u-1]!=0 and edge[v-1]==0:
         edge[v-1] = edge[u-1]
    else:
        pass
if edge.count(0) ==0:
    print(count-1)
else:
    summ = 0
    for i in range(1, count):
        summ += edge.count(i)
    print(count-1+n-summ )

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

#import numpy as np
#import scipy, scipy.special

# Python 3 modules: https://docs.python.org/3/library/

import sys
import math, itertools, operator
from math import *
from math import factorial as fact
from itertools import permutations, combinations
from functools import reduce
# Use scipy for stats: https://docs.scipy.org/doc/scipy/reference/stats.html
# Before Python 3.5
from fractions import gcd

inf = float('inf')

def lcm(a, b):
    return a * b // gcd(a,b)

def perm(a, b):
    import scipy.special
    return scipy.special.perm(a, b, exact = True)

def comb(a, b):
    import scipy.special
    return scipy.special.comb(a, b, exact = True)

def dfact(n):
    import scipy.special
    return scipy.special.factorial2(n, exact = True)

def prod(l):
    return reduce(operator.mul, l)

def input_ints(inp = input, sep = ' ', conv = int):
    return map(conv, inp().split(sep = sep))

################################################################################

sys.setrecursionlimit(20000)

N, M = input_ints()

# D[i][j]: Card i has a rel. with card j
D = [[] for i in range(N)]
for i in range(M):
    x, y, z = input_ints()
    x -= 1
    y -= 1
    D[x].append(y)

visited = [False for i in range(N)]
def dfs(n):
    for idx in D[n]:
        if not visited[idx]:
            visited[idx] = True
            dfs(idx)

cnt = 0
for n in range(N):
    if not visited[n]:
        visited[n] = True
        dfs(n)
        cnt += 1
print(cnt)

Submission status: Wrong Answer

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

n,m = map(int,input().split())
l = [False for i in range(n)]

for i in range(m):
    x, y, z = map(int, input().split())
    y -= 1
    l[y] = True

sum = 0
for i in range(n):
    if not l[i]:
        sum += 1

print(sum)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]


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


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

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)
uf = UnionFind(n)
for _ in range(m):
  x,y,z = map(int,input().split())
  uf.unite(x-1,y-1)
print(len(set(uf.parent)))

Submission status: Wrong Answer

Solution code:
n, m = [int(i) for i in input().split()]
x, y, z = [int(i) for i in input().split()]
group = [[x,y]]
for mi in range(m-1):
    x, y, z = [int(i) for i in input().split()]
    append_flag = False
    for gi in range(len(group)):
        if x in group[gi]:
            group[gi].append(y)
            append_flag = True
            break
        elif y in group[gi]:
            group[gi].append(x)
            append_flag = True
            break
    if not append_flag: 
        group.append([x,y])
group_len = 0
for gi in range(len(group)):
    group_len += len(set(group[gi]))
print(len(group) + n - group_len)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
checked = [False for i in range(n)]
ans = 0

for i in range(m):
    x, y, z = map(int, input().split())
    if not checked[x - 1] and not checked[y - 1]:
        ans += 1
    checked[x - 1] = True
    checked[y - 1] = True

for flag in checked:
    if not flag:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin

def solve():
    N, M = map(int, stdin.readline().split())
    
    known = set()
    cnt = 0
    
    for _ in range(M):
        x, y, x = map(int, stdin.readline().split())
        
        if x in known:
            known.add(y)
            continue
        
        if y in known:
            known.add(x)
            continue
        
        known.add(x)
        known.add(y)
        cnt += 1
    
    print (N - len(known) + cnt)
    
if __name__ == "__main__":  
    solve()

Submission status: Wrong Answer

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

info = set()
cnt = 0

for i in range(m):
    x, y, z = map(int,input().split())
    if x not in info or y not in info:
        cnt += 1
        info.add(x)
        info.add(y)

print(n - cnt)

Submission status: Wrong Answer

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

for i in range(M):
    x, y, z = map(int, input().split(" "))
    if len(group_list) == 0:
        s = set()
        s.add(x)
        s.add(y)
        group_list.append(s)
    for g in group_list:
        if x in g:
            g.add(y)
        elif y in g:
            g.add(x)
        else:
            s = set()
            s.add(x)
            s.add(y)
            group_list.append(s)
            break

count = 0
for g in group_list:
    count += len(g)

print(N - count + len(group_list))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

def Find(x):    #xの根を返す
    global table

    if table[x] == x:
        return x
    else:
        table[x] = Find(table[x])    #親の更新(根を直接親にして参照距離を短く)
        size[x] = size[table[x]]
        return table[x]

def Unite(x,y):    #xとyを繋げる
    global size
    global rank
    x = Find(x)
    y = Find(y)
    sx = Size(x)
    sy = Size(y)

    if x == y:
        return

    if rank[x] > rank[y]:
        table[y] = x
        size[x] = sx + sy
    else:
        table[x] = y
        size[y] = sx + sy
        if rank[x] == rank[y]:
            rank[y] += 1

def Check(x,y):
    if Find(x) == Find(y):
        return True
    else:
        return False

def Size(x):
    return size[Find(x)]

N,M = inpl()

table = [i for i in range(N)]    #木の親 table[x] == x なら根
rank  = [1 for i in range(N)]    #木の長さ
size  = [1 for i in range(N)]    #集合のサイズ

for i in range(M):
    x,y,z = inpl()
    x -= 1
    y -= 1
    if not Check(x,y):
        Unite(x,y)

cnt = [0]*N
for x in table:
    cnt[x] = 1
print(sum(cnt))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
p1 = [i for i in range(n)]
s1 = [1 for _ in range(n)]

def root(i):
  if p1[i] == i:
    return i
  else:
    p1[i] = root(p1[i])
  return p1[i]

def unite(i, j):
  pi = root(i)
  pj = root(j)
  if pi == pj:
    return
  else:
    if s1[pi] < s1[pj]:
      p1[pi] = pj
    elif s1[pj] < s1[pi]:
      p1[pj] = pi
    else:
      if pi < pj:
        p1[pj] = pi
        s1[pi] += 1
      else:
        p1[pi] = pj
        s1[pj] += 1

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

print(len(set(p1)))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
box = set()
box2 = set()
ans = 0
for _ in range(M):
    X, Y, Z = map(int, input().split())
    if X not in box and Y not in box:
        box.add(X)
        box.add(Y)
        ans += 1
    box2.add(X)
    box2.add(Y)
for i in range(1,N+1):
    if i not in box2:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


class Solution:
    def main(self):
        N, M = map(int, input().split())
        self.odd = defaultdict(set)
        self.even = defaultdict(set)
        for _ in range(M):
            X, Y, Z = map(int, input().split())
            if Z % 2 == 0:
                self.even[X-1].add(Y-1)
                self.even[Y-1].add(X-1)
            else:
                self.odd[X-1].add(Y-1)
                self.odd[Y-1].add(X-1)
        self.A = [None] * N
        cnt = 0
        for i in range(N):
            if self.A[i] == None:
                cnt += 1
                stack = [(i, 0)]
                while stack:
                    node, color = stack.pop()
                    if self.A[node] is None:
                        self.A[node] = color
                        for node in self.even[node]:
                            stack.append((node, color))
                        for node in self.odd[node]:
                            stack.append((node, 1^color))
        print(cnt)


if __name__ == '__main__':
    Solution().main()

Submission status: Wrong Answer

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

# Union-Find
parent = [i for i in range(N*2)]
rank = [1] * (N*2)
def get_root(node):
  global parent
  if parent[node] == node:
    return node
  root = get_root(parent[node])
  parent[node] = root
  return root

def union(a, b):
  global parent
  global rank
  root_a = get_root(a)
  rank_a = rank[root_a]
  root_b = get_root(b)
  rank_b = rank[root_b]
  if root_a == root_b:
    return
  if rank_a < rank_b:
    parent[root_a] = root_b
  else:
    parent[root_b] = root_a
    if rank_a == rank_b:
      rank[root_a] += 1

for _ in range(M):
  x, y, z = map(int, input().split())
  x -= 1
  y -= 1
  if z % 2:
    # x + y が奇数: 違うグループ
    union(x, y+N)
    union(x+N, y)
  else:
    # x + y が偶数: 同じグループ
    union(x, y)
    union(x+N, y+N)

# グループ数 / 2 が答え
print(len(set(parent)) // 2)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
datalist = [0 for i in range(n)]
ans = 0
for i in range(m):
    x, y, z = map(int, input().split())
    if datalist[x - 1] == 0 and datalist[y - 1] == 0:

        ans += 1

    datalist[x - 1] = 1
    datalist[y - 1] = 1

for i in datalist:
    if i == 0:
        ans += 1

print(ans )

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
h = {}
c = {}
for i in range(N):
    h[i + 1] = []
    c[i + 1] = 0

for m in range(M):
    x, y, z = map(int, input().split())
    h[x].append(y)
    h[y].append(x)

ans = 0
rest = N

while len(h) > 0:
    p = max([[len(v), k] for k, v in h.items()])
    if p[0] <= 1:
        break
    rest = rest - p[0] - 1
    for n in h[p[1]]:
        if n in h:
            del h[n]
    del h[p[1]]
    ans += 1

o = 0
for k, v in h.items():
    if len(v) == 1:
        o += 1
print(ans + len(h) - o // 2)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
nums = set(range(n+1)[1:])
grps = []
for i in range(m):
    x, y, z = map(int, input().split())
    if x in nums:
        nums.remove(x)
    if y in nums:
        nums.remove(y)
    found = False
    for grp in grps:
        if x in grp or y in grp:
            grp.add(x)
            grp.add(y)
            found = True
    if not found:
        grps.append({x, y})
        

print(len(grps)+len(nums))

Submission status: Wrong Answer

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

ans = [0]*N
cost = 0
for i in range(0, M):
    if XYZ[i][0] == XYZ[i][1]:
        ans[XYZ[i][0]-1] = 1
    elif ans[XYZ[i][0]-1] == 1 or ans[XYZ[i][1]-1] == 1:
        ans[XYZ[i][0]-1] = 1
        ans[XYZ[i][1]-1] = 1
    else:
        ans[XYZ[i][0]-1] = 1
        ans[XYZ[i][1]-1] = 1
        cost += 1

cost += ans.count(0)
print(cost)

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
X = [list(map(int,input().split())) for i in range(M)]
X = sorted(X, key=lambda x:(x[0],x[1]))

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, 0)
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
cnt = [0]*N
waste = 0
for _ in range(M):
    x,y,z = map(int, input().split())
    x,y = x-1,y-1
    if cnt[x]>0 and cnt[y]>0:
        waste += 1
    cnt[x] += 1
    cnt[y] += 1

print(N - M + waste)

Submission status: Wrong Answer

Solution code:
a=input().split()
a=list(map(int,a))
i=0
dif=[]
while i<a[1]:
  c=input().split()
  c=list(map(int,c))
  c.sort()
  if c[-1]-c[0]==1:
    dif.append(2)
  elif c[-1]-c[0]==0:
    dif.append(1)
  elif c[-1]-c[0]>=2:
    dif.append(c[-1]-c[0])
  i+=1
dif.sort()
print(dif[-1])

Submission status: Wrong Answer

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

reader = [i for i in range(n)]
count = [1 for i in range(n)]
#print(reader)
#print(count)
for xy in xyz:
    if reader[xy[0]-1] != reader[xy[1]-1]:
        a = max(xy[0],xy[1])-1
        b = min(xy[0],xy[1])-1
    #    print(a,b)
        reader[a] = reader[b]
        count[reader[b]] += count[a]
        count[a] = 0
    #    print(reader)
    #    print(count)
print(n-count.count(0))

Submission status: Wrong Answer

Solution code:
from collections import deque

def read_input():
    n, m = map(int, input().split())

    conds = []
    for i in range(m):
        x, y, z = map(int, input().split())
        conds.append((x, y))

    return n, m, conds


def graph_connected_component(nodes, nd_edges):
    # 無向グラフを想定、edgesを両向きにはやす
    edge_table = {n:[] for n in nodes}
    for e in nd_edges:
        edge_table[e[0]].append(e[1])
        edge_table[e[1]].append(e[0])

    result = [-1] * (len(nodes) + 1)
    count = 0
    color = 0
    while count < len(nodes):
        node_q = deque()
        color += 1

        # まだ見ていないnodeを基点にしてcomponentを構成
        for node in nodes:
            if result[node] == -1:
                node_q.appendleft(node)
                break

        # qがある = 連結先があるので探索
        while len(node_q) > 0:
            curr = node_q.pop()
            result[curr] = color
            count += 1

            # 連結先のうち、まだ未探索nodeをqにつむ
            next_nodes = edge_table[curr]
            for node in next_nodes:
                if result[node] == -1:
                    node_q.appendleft(node)

    return result


def submit():
    n, m, conds = read_input()
    nodes = [i for i in range(1, n + 1)]

    comps = graph_connected_component(nodes, conds)
    print(max(comps))


if __name__ == '__main__':
    submit()

Submission status: Wrong Answer

Solution code:
n, m = [int(i) for i in input().split()]
x, y, z = [int(i) for i in input().split()]
group = [[x,y]]
for mi in range(m-1):
    x, y, z = [int(i) for i in input().split()]
    append_flag = False
    for gi in range(len(group)):
        if x in group[gi]:
            if y not in group[gi]:
                group[gi].append(y)
            append_flag = True
            break
        elif y in group[gi]:
            if x not in group[gi]:
                group[gi].append(x)
            append_flag = True
            break
    if not append_flag: 
        group.append([x,y])
group_len = 0
for gi in range(len(group)):
    group_len += len(group[gi])
print(len(group) + n - group_len)

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

print(N-len(X1))

Submission status: Wrong Answer

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

o = [False] * N

for _ in range(M):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    z &= 1
    o[max(x, y)] = True

print(N - sum(o))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
root=[-1]*N
def search(i):
    if root[i]>=0:
        root[i]=search(root[i])
        return root[i]
    return i
for i in range(M):
    x,y,z=map(int,input().split())
    x-=1
    y-=1
    rx=search(x)
    ry=search(y)
    if rx==ry:
        continue
    elif root[rx]<=root[ry]:
        root[ry]+=root[rx]
        root[rx]=ry
    else:
        root[rx]+=root[ry]
        root[ry]=rx
ans=0
print(root)
for i in range(N):
    if root[i]<0:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

def Find(x):    #xの根を返す
    global table

    if table[x] == x:
        return x
    else:
        table[x] = Find(table[x])    #親の更新(根を直接親にして参照距離を短く)
        size[x] = size[table[x]]
        return table[x]

def Unite(x,y):    #xとyを繋げる
    global size
    global rank
    x = Find(x)
    y = Find(y)
    sx = Size(x)
    sy = Size(y)

    if x == y:
        return

    if rank[x] > rank[y]:
        table[y] = x
        size[x] = sx + sy
    else:
        table[x] = y
        size[y] = sx + sy
        if rank[x] == rank[y]:
            rank[y] += 1

def Check(x,y):
    if Find(x) == Find(y):
        return True
    else:
        return False

def Size(x):
    return size[Find(x)]

N,M = inpl()

table = [i for i in range(N)]    #木の親 table[x] == x なら根
rank  = [1 for i in range(N)]    #木の長さ
size  = [1 for i in range(N)]    #集合のサイズ

for i in range(M):
    x,y,z = inpl()
    x -= 1
    y -= 1
    if not Check(x,y):
        Unite(x,y)

cnt = [0]*N
for x in table:
    cnt[x] = 1
print(sum(cnt))

Submission status: Wrong Answer

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

A = [-1 for i in range(N)]

count = 0

for i in range(M):

    x, y, z = map(int, input().split())

    x -= 1
    y -= 1

    if A[x] == -1 and A[y] == -1:
        A[x] = count
        A[y] = count
        count += 1

    elif A[x] != -1:
        A[y] = A[x]

    elif A[y] != -1:
        A[x] = A[y]

ans = count

for x in A:
    if x == -1:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)

N,M = map(int,input().split())
u = UnionFind(N)
for _ in range(M):
  x,y,z = map(int,input().split())
  u.unite(x-1,y-1)
print(len(set(u.parent)))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


g = Graph()
N, M = [int(i) for i in input().split()]
magic = [1 for i in range(N)]

for i in range(M):
    u, v, w = [int(i) for i in input().split()]
    g.add_edge(u-1, v-1, w)
    g.add_edge(v-1, u-1, w)
    magic[u-1] = 0
    magic[v-1] = 0
ans = sum(magic)

d = Dijkstra(g, 0)
ans += 1

for i in d.dist.keys():
    #print(i)
    magic[i] = 1

for i in range(1, N):
    if magic[i] == 0:
        d = Dijkstra(g, i)
        ans += 1
        for j in d.dist.keys():
            #print(j)
            magic[j] = 1

print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in 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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


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

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

    for i in range(N):
        uf.find(i)
    # print(uf.par[1:])
    s = set(uf.par[1:])
    print(len(s))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

info_list =[]

for i in range(M):
    info_list.append(list(map(int, input().split())))
    
a = set()

info_count = 0

for info in info_list:
    if info[0] in a and info[1] in a:
        pass
    else:
        info_count += 1
        a.add(info[0])
        a.add(info[1])
        
print(N - info_count)

Submission status: Wrong Answer

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

ans = [0]*N
cost = 0
for i in range(0, M):
    if ans[XYZ[i][0]-1] == 1 or ans[XYZ[i][1]-1] == 1:
        ans[XYZ[i][0]-1] = 1
        ans[XYZ[i][1]-1] = 1
    else:
        ans[XYZ[i][0]-1] = 1
        ans[XYZ[i][1]-1] = 1
        cost += 1

cost += ans.count(0)
print(cost)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
known = []
count = 0
for i in range(M):
	X, Y, _ = map(int, input().split())
	if (X in known) & (Y in known):
		pass
	elif X in known:
		known.append(X)
	elif Y in known:
		known.append(Y)
	else:
		known.append(X)
		known.append(Y)
		count += 1
if len(known) < N:
	count = count + N - len(known)

print(count)

Submission status: Wrong Answer

Solution code:
# UnionTreeクラス：グループ分けを木構造で管理する
class UnionFind():
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.size = [1] * N
        self.N = N

    # xのrootを返す
    def root(self, x):
        if self.par[x] == x:
            return x
        else: 
            self.par[x] = self.root(self.par[x])
            return self.root(self.par[x])

    # x, yが同じrootの場合true
    def same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry

    # x,yのrootが違った場合、併合
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if self.size[rx] < self.size[ry]:
            self.par[rx] = ry
            self.size[ry] += self.size[rx]
        else:
            self.par[ry] = rx
            self.size[rx] += self.size[ry]
            
#　以降 ABC120の例 (途中まで)--------------------------------------------
import sys
input = sys.stdin.readline

n, m = (int(i) for i in input().split())
xyz = [[int(i)-1 for i in input().split()] for i in range(m)]

uf = UnionFind(n)
for x,y,z in xyz:
    if not uf.same(x,y):
        uf.unite(x,y)


print(len(set(uf.par)))

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 = {}
    for i in xyz:
        x,y,z = i.split()
        x = int(x)
        y = int(y)
        z = int(z)
        if x not in results and y not in results:
            results[x] = x
            results[y] = x
        elif x not in results and y in results:
            results[x] = results[y]
        elif x in results and y not in results:
            results[y] = results[x]
        elif x in results and y in results:
            if results[x] != results[y]:
                for k in results:
                    if results[k] == results[y]:
                        results[k] = results[x]
    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:
N, M = list(map(int, input().split()))

K = []
for i in range(M):
    X, Y, Z = list(map(int, input().split()))
    if X in K:
        if Y in K:
            N -= 2
        else:
            # N -= 1
            K.append(Y)
    elif Y in K:
        # N -= 1
        K.append(X)
    else:
        K.append(X)
        K.append(Y)
        N -= 1

print(N)