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:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
from operator import mul

INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


# UnionFind
class UnionFind():
    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 size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 組合せnCr
def combinations_count(n, r):
    if n < r:
        return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

# ここから書き始める
n, m = map(int, input().split())            
x = [0 for i in range(m)]
y = [0 for i in range(m)]
z = [0 for i in range(m)]
for i in range(m):
    x[i], y[i], z[i] = map(int, input().split())
a = [[i] for i in range(n)]
for i in range(m):
    a[x[i] - 1].append(y[i] - 1)
    a[y[i] - 1].append(x[i] - 1)
a.sort(reverse=True, key=lambda x:len(x))
# print("a =", a)
b = [0 for i in range(n)]
# print("a =", a)
ans = 0
c = []
# for i in range(n):
#     index1 = bisect_left(c, i)
#     if index1 == len(c) or c[index1] != i:
#         ans += 1
#     c += a[i]
for i in range(n):
    index1 = bisect_left(c, a[i][0])
    if index1 == len(c) or c[index1] != a[i][0]:
        ans += 1
    c += a[i][1:]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
from operator import mul

INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


# UnionFind
class UnionFind():
    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 size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 組合せnCr
def combinations_count(n, r):
    if n < r:
        return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

# ここから書き始める
n, m = map(int, input().split())            
x = [0 for i in range(m)]
y = [0 for i in range(m)]
z = [0 for i in range(m)]
for i in range(m):
    x[i], y[i], z[i] = map(int, input().split())
a = [[] for i in range(n)]
for i in range(m):
    a[x[i] - 1].append(y[i] - 1)
    a[y[i] - 1].append(x[i] - 1)
b = [0 for i in range(n)]
# print("a =", a)
ans = 0
c = []
for i in range(n):
    index1 = bisect_left(c, i)
    if index1 == len(c) or c[index1] != i:
        ans += 1
    c += a[i]
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = [int(v) for v in input().split()]
inputs = []

for i in range(0, m):
    hint = [int(v) for v in input().split()][:2]
    hint.sort()
    inputs.append(hint)

inputs.sort()
hints = [None for _ in range(0, n)]

for x, y in inputs:
    hx = hints[x - 1]
    hy = hints[y - 1]

    if hx is None and hy is None:
        hints[x - 1] = min([x, y])
        hints[y - 1] = min([x, y])
    elif hx is None:
        hints[x - 1] = hy
    elif hy is None:
        hints[y - 1] = hx

count = hints.count(None)
count += len(set([h for h in hints if h is not None]))
print(count)

Submission status: Wrong Answer

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

for i in range(1,n+1):
    if not p[i]:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

for i in range(1,n):
    if not p[i]:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

    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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    def same(self, x, y):
        if self.find(x) == self.find(y):
            return True
        else:
            return False

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

uf = UnionFind(n) # n: 頂点数

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

    uf.unite(x-1, y-1)

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

Submission status: Wrong Answer

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

g = 0
A = [-1] * n

for x, y, z in XYZ:
  x -= 1
  y -= 1
  if A[x] == -1:
    if A[y] == -1:
      A[x] = [g, z % 2]
      A[y] = [g, (z + 1) % 2]
      g += 1
    else:
      A[x] = [A[y][0], (A[y][1] + z) % 2]
  else:
    A[y] = [A[x][0], (A[x][1] + z) % 2]

print(g + sum(i == -1 for i in A))

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self,N):
        self.root = list(range(N))
        self.size = [1] * (N)
        
    def find_root(self,x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x
    
    def merge(self,x,y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        sx,sy = self.size[x],self.size[y]
        if sx < sy:
            self.root[x] = y
            self.size[y] += sx
        else:
            self.root[y] = x
            self.size[x] += sy


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

uf = UnionFind(n)

answer = []
find_root = uf.find_root
merge = uf.merge
for i in range(m):
    x, y, z = xyz[i][0]-1, xyz[i][1]-1, xyz[i][2]
    merge(x,y)

for i in range(n):
    uf.find_root(i)
print(len(set(uf.root)))

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self,N):
        self.root = list(range(N))
        self.size = [1] * (N)
        
    def find_root(self,x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x
    
    def merge(self,x,y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        sx,sy = self.size[x],self.size[y]
        if sx < sy:
            self.root[x] = y
            self.size[y] += sx
        else:
            self.root[y] = x
            self.size[x] += sy


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

uf = UnionFind(n)

answer = []
find_root = uf.find_root
merge = uf.merge
for i in range(m):
    x, y, z = xyz[i][0]-1, xyz[i][1]-1, xyz[i][2]
    merge(x,y)

print(len(set(uf.root)))

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self,N):
        self.root = list(range(N+1))
        self.size = [1] * (N+1)
        
    def find_root(self,x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x
    
    def merge(self,x,y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        sx,sy = self.size[x],self.size[y]
        if sx < sy:
            self.root[x] = y
            self.size[y] += sx
        else:
            self.root[y] = x
            self.size[x] += sy


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

uf = UnionFind(n)

answer = []
find_root = uf.find_root
merge = uf.merge
for i in range(m):
    x, y, z = xyz[i][0], xyz[i][1], xyz[i][2]
    merge(x,y)

print(len(set(uf.root))-1)

Submission status: Wrong Answer

Solution code:

n, m = list(map(int, input().split()))
dic = {}  
count = 0
for i in range(m):
  a, b, c = list(map(int, input().split()))
  if not a in dic:
    dic[a]=[b]
  else:
    dic[a].append(b)

dp = [0]*n
#print(dic)
for i in range(n):
  if dp[i]==0:
    count += 1
    dp[i]=count
    if i+1 in dic:
      for j in dic[i+1]:
        dp[j-1]=count
  else:
    if i+1 in dic:
      for j in dic[i+1]:
        dp[j-1]=count
#print(dp)
print(count)

Submission status: Wrong Answer

Solution code:

n, m = list(map(int, input().split()))
dic = {}  
count = 0
for i in range(m):
  a, b, c = list(map(int, input().split()))
  if not a in dic:
    dic[a]=[b]
  else:
    dic[a].append(b)

dp = [0]*n
print(dic)
for i in range(n):
  if dp[i]==0:
    count += 1
    dp[i]=count
    if i+1 in dic:
      for j in dic[i+1]:
        dp[j-1]=count
  else:
    if i+1 in dic:
      for j in dic[i+1]:
        dp[j-1]=count
#print(dp)
print(count)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
Clear = [-1]*N
ans = 0
for i in range(M):
    X, Y, Z = map(int, input().split())
    X -= 1
    Y -= 1
    if Clear[X] == 1:
        Clear[Y] = 1
    elif Clear[Y] == 1:
        Clear[X] = 1
    else:
        Clear[X] = 1
        Clear[Y] = 1
        ans += 1

for i in Clear:
    if i == -1:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
Clear = [-1]*N
ans = 0
for i in range(M):
    X, Y, Z = map(int, input().split())
    X -= 1
    Y -= 1
    if Z % 2 == 0:
        if Clear[X] == 1:
            Clear[Y] = 1
        elif Clear[X] == 2:
            Clear[Y] = 2
        elif Clear[Y] == 1:
            Clear[X] = 1
        elif Clear[Y] == 2:
            Clear[X] = 2
        else:
            ans += 1
            Clear[X] = 1
            Clear[Y] = 1
    else:
        if Clear[X] == 1:
            Clear[Y] = 2
        elif Clear[X] == 2:
            Clear[Y] = 1
        elif Clear[Y] == 1:
            Clear[X] = 2
        elif Clear[Y] == 2:
            Clear[X] = 1
        else:
            ans += 1
            Clear[X] = 2
            Clear[Y] = 1

for i in Clear:
    if i == -1:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
Clear = [-1]*N
ans = 0
for i in range(M):
    X, Y, Z = map(int, input().split())
    X -= 1
    Y -= 1
    if Z % 2 == 0:
        if Clear[X] == 0:
            Clear[Y] = 0
        elif Clear[X] == 1:
            Clear[Y] = 1
        elif Clear[Y] == 0:
            Clear[X] = 0
        elif Clear[Y] == 1:
            Clear[X] = 1
        else:
            ans += 1
            Clear[X] = 1
            Clear[Y] = 1
    else:
        if Clear[X] == 0:
            Clear[Y] = 1
        elif Clear[X] == 1:
            Clear[Y] = 0
        elif Clear[Y] == 0:
            Clear[X] = 1
        elif Clear[Y] == 1:
            Clear[X] = 0
        else:
            ans += 1
            Clear[X] = 1
            Clear[Y] = 0

for i in Clear:
    if i == -1:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n)
        self.size = [1] * (n)
    # 検索
    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 x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)

uf = UnionFind(n)

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

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

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (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 x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)

uf = UnionFind(n)

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

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

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (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 x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)

uf = UnionFind(n)

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

li = uf.par[1:]

c = Counter(li)

print(len(c))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
xyz = sorted([list(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: Wrong Answer

Solution code:
n, m = map(int, input().split())
xyz = [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: Wrong Answer

Solution code:
class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.ranks = [0 for _ in range(n)]

    def root(self, node):
        parent_node = self.parents[node]
        if parent_node == node:
            return node
        root_node = self.root(parent_node)
        self.parents[node] = root_node  # reduction
        return root_node

    def union(self, one_node, other_node):
        one_root = self.root(one_node)
        other_root = self.root(other_node)
        if one_root == other_root:
            return
        if self.ranks[one_root] < self.ranks[other_root]:
            self.parents[one_root] = other_root
        else:
            self.parents[other_root] = one_root
            if self.ranks[one_root] == self.ranks[other_root]:
                self.ranks[one_root] += 1


def main():
    N, M = list(map(int, input().split(' ')))
    tree = UnionFind(N)
    for _ in range(M):
        x, y, _ = list(map(int, input().split(' ')))
        tree.union(x - 1, y - 1)
    print(len(set(tree.parents)))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n, m = map(int, input().split())
    seen = set()
    ans = n - m
    for _ in range(m):
        x, y, z = map(int, input().split())
        if x in seen and y in seen:
            ans += 1
        seen.add(x)
        seen.add(y)
    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Wrong Answer

Solution code:
N,M,*f = map(int, open(0).read().split())
XYZ = [f[i:i+3] for i in range(0, len(f), 3)]
XY = [(x[0],x[1]) for x in XYZ]
clarified = set()
cost = 0
for x, y in XY:
    if x not in clarified:
        if y not in clarified:
            cost += 1
            clarified.add(x)
            clarified.add(y)
        else:
            clarified.add(x)
    else:
        if y not in clarified:
            clarified.add(y)
print(cost+N-len(clarified))

Submission status: Wrong Answer

Solution code:
VAL_INF = 10**9

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

# カードリスト
card_list = [VAL_INF for i in range(N)]

# ルールリスト
rule_list = []
for i in range(M):
	rule_list.append(list(map(int, input().split())))

	# 0始まりにするため、-1
	rule_list[i][0] -= 1
	rule_list[i][1] -= 1

# ヒント数
hints = 0

# ルール順に処理
rule_list.sort()

# 値セット
def set_value(index, value):
	card_list[rule_list[index][0]] = value
	card_list[rule_list[index][1]] = value

for i in range(M):
	# ルールに書かれている値のカードリストの両方の値未処理	ヒント数を入れる
	if((card_list[rule_list[i][0]] == VAL_INF) and (card_list[rule_list[i][1]] == VAL_INF)):
		hints += 1
		set_value(i, hints)
	# セット済みの値あり	小さいほうの値を入れる
	else:
		min_val = min([card_list[rule_list[i][0]], card_list[rule_list[i][1]]])
		set_value(i, min_val)

# 未処理があれば、その分加算
hints += card_list.count(VAL_INF)

print(hints)

Submission status: Wrong Answer

Solution code:
VAL_INF = 10**9

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

# カードリスト
card_list = [VAL_INF for i in range(N)]

# ルールリスト
rule_list = []
for i in range(M):
	rule_list.append(list(map(int, input().split())))

	# 0始まりにするため、-1
	rule_list[i][0] -= 1
	rule_list[i][1] -= 1

# ヒント数
hints = 0

# ルール順に処理
sort_rule_list = sorted(rule_list)

# 値セット
def set_value(index, value):
	card_list[sort_rule_list[index][0]] = value
	card_list[sort_rule_list[index][1]] = value

for i in range(M):
	# ルールに書かれている値のカードリストの両方の値未処理	ヒント数を入れる
	if((card_list[sort_rule_list[i][0]] == VAL_INF) and (card_list[sort_rule_list[i][1]] == VAL_INF)):
		hints += 1
		set_value(i, hints)
	# セット済みの値あり	小さいほうの値を入れる
	else:
		min_val = min([card_list[sort_rule_list[i][0]], card_list[sort_rule_list[i][1]]])
		set_value(i, min_val)

# 未処理があれば、その分加算
hints += card_list.count(VAL_INF)

print(hints)

Submission status: Wrong Answer

Solution code:
VAL_INF = 10**9

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

# カードリスト
card_list = [VAL_INF for i in range(N)]

# ルールリスト
rule_list = []
for i in range(M):
	rule_list.append(list(map(int, input().split())))

	# 0始まりにするため、-1
	rule_list[i][0] -= 1
	rule_list[i][1] -= 1

# ヒント数
hints = 0

# ルール順に処理
sort_rule_list = sorted(rule_list)

# 値セット
def set_value(index, value):
	card_list[rule_list[index][0]] = value
	card_list[rule_list[index][1]] = value

for i in range(M):
	# ルールに書かれている値のカードリストの両方の値未処理	ヒント数を入れる
	if((card_list[sort_rule_list[i][0]] == VAL_INF) and (card_list[sort_rule_list[i][1]] == VAL_INF)):
		hints += 1
		set_value(i, hints)
	# セット済みの値あり	小さいほうの値を入れる
	else:
		min_val = min([card_list[sort_rule_list[i][0]], card_list[sort_rule_list[i][1]]])
		set_value(i, min_val)

# 未処理があれば、その分加算
hints += card_list.count(VAL_INF)

print(hints)

Submission status: Wrong Answer

Solution code:
VAL_INF = 10**9

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

# カードリスト
card_list = [VAL_INF for i in range(N)]

# ルールリスト
rule_list = []
for i in range(M):
	rule_list.append(list(map(int, input().split())))

	# 0始まりにするため、-1
	rule_list[i][0] -= 1
	rule_list[i][1] -= 1

# ヒント数
hints = 0

# ルール順に処理
sort_rule_list = sorted(rule_list)

# 値セット
def set_value(index, value):
	card_list[rule_list[index][0]] = value
	card_list[rule_list[index][1]] = value

for i in range(M):
	# ルールに書かれている値のカードリストの両方の値未処理	ヒント数を入れる
	if((card_list[rule_list[i][0]] == VAL_INF) and (card_list[rule_list[i][1]] == VAL_INF)):
		hints += 1
		set_value(i, hints)
	# セット済みの値あり	小さいほうの値を入れる
	else:
		min_val = min([card_list[rule_list[i][0]], card_list[rule_list[i][1]]])
		set_value(i, min_val)

# 未処理があれば、その分加算
hints += card_list.count(VAL_INF)

print(hints)

Submission status: Wrong Answer

Solution code:
import copy

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

# ルールリスト
rule_list = []
for i in range(M):
	rule_list.append(list(map(int, input().split())))

	rule_list[i][0] -= 1
	rule_list[i][1] -= 1
	# ルールリストのZを0,1にする。
	rule_list[i][2] = (rule_list[i][2] % 2)

# チェックリスト
check_list = [-1 for i in range(N)]

# ヒント数
hints = 1

# 0番目を奇数で仮
check_list[0] = 1

# 全て値が埋まるまでループ
while(True):
	# ルールリストをチェック
	# 片方が分かっていれば、もう片方を埋める
	for i, rule in enumerate(rule_list):
		if(check_list[rule[0]] != -1):
			check_list[rule[1]] = (check_list[rule[0]] + check_list[rule[2]]) % 2
		elif(check_list[rule[1]] != -1):
			check_list[rule[0]] = (check_list[rule[1]] + check_list[rule[2]]) % 2
		else:
			pass
	# 埋まっていない場合は、一つヒントをもらう
	try:
		tmp_chk = check_list.index(-1)
		hints += 1
		# 奇数で仮
		check_list[tmp_chk] = 1

	# 全て埋まったら抜ける
	except ValueError:
		break

print(hints)

Submission status: Wrong Answer

Solution code:
def main():
    N,M = map(int, input().split())
    L = [[] for _ in range(N)]
    L[0].append(0)

    for i in range(M):
        x,y,z = map(int, input().split())
        L_exist = [x for x in L if x]
        for j,k in enumerate(L_exist):
            if (x in k) and not(y in k):
                L[j].append(y)
                break
            elif (y in k) and not(x in k):
                L[j].append(x)
                break
            elif (x in k) and (y in k):
                break
        else:
            L[len(L_exist)].append(x)
            L[len(L_exist)].append(y)

    a = [x for x in L if x]
    
    n=0
    for i in a:
        n += len(i)

    print((N-n+1)+len(a)-1)
main()