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 numpy as np

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())
lst = np.array([x, y]).T.tolist()
lst.sort()
x = np.array(lst).T.tolist()[0]
y = np.array(lst).T.tolist()[1]

lst = list(range(1, N+1))
cnt = 0
for i in range(M):
    if lst[x[i]-1] > 0 and lst[y[i]-1] > 0:
        cnt -= 1
        lst[x[i]-1] = cnt
        lst[y[i]-1] = cnt
    else:
        cluster = min(lst[x[i]-1], lst[y[i]-1])
        lst[x[i]-1] = cluster
        lst[y[i]-1] = cluster

print(len(set(lst)))

Submission status: Wrong Answer

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

lst = list(range(1, N+1))
cnt = 0
for i in range(M):
    x, y, z = map(int, input().split())
    if lst[x-1] > 0 and lst[y-1] > 0:
        cnt -= 1
        lst[x-1] = cnt
        lst[y-1] = cnt
    else:
        cluster = min(lst[x-1], lst[y-1])
        lst[x-1] = cluster
        lst[y-1] = cluster

print(len(set(lst)))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
p = [i for i in range(N)]
for _ in range(M):
  x,y,z = map(int,input().split())
  x,y = x-1,y-1
  while p[x]!=x:
    x = p[x]
  p[y] = x
for i in range(N):
  x = p[i]
  while x!=p[x]:
    x = p[x]
  p[i]=x
print(len(set(p)))

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)]
        self.sizes = [1 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
            self.sizes[y] += self.sizes[x]
        else:
            self.parent[y] = x
            self.sizes[x] += self.sizes[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 size(self, x):
        return self.sizes[self.find(x)]

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

u = UnionFind(N+1)

for m in range(M):
    xyz = [int(i)-1 for i in input().split()]
    if u.find(xyz[0]) != u.find(xyz[1]):
        u.unite(xyz[0],xyz[1])

print(len(list(set(u.parent)))-1)

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)]
        self.sizes = [1 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
            self.sizes[y] += self.sizes[x]
        else:
            self.parent[y] = x
            self.sizes[x] += self.sizes[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 size(self, x):
        return self.sizes[self.find(x)]

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

u = UnionFind(N)

for m in range(M):
    xyz = [int(i)-1 for i in input().split()]
    if u.find(xyz[0]) != u.find(xyz[1]):
        u.unite(xyz[0],xyz[1])

print(len(list(set(u.parent))))

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)]
        self.sizes = [1 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
            self.sizes[y] += self.sizes[x]
        else:
            self.parent[y] = x
            self.sizes[x] += self.sizes[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 size(self, x):
        return self.sizes[self.find(x)]


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

u = UnionFind(N)


for m in range(M):
    xyz = [int(i)-1 for i in input().split()]
    if u.find(xyz[0]) != u.find(xyz[1]):
        u.unite(xyz[0],xyz[1])

    

cnt = [0]*N
for n in range(N):
    cnt[u.parent[n]] = 1
    

print(sum(cnt))

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)]
        self.sizes = [1 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
            self.sizes[y] += self.sizes[x]
        else:
            self.parent[y] = x
            self.sizes[x] += self.sizes[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 size(self, x):
        return self.sizes[self.find(x)]


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

u = UnionFind(N)


for m in range(M):
    xyz = [int(i)-1 for i in input().split()]
    u.unite(xyz[0],xyz[1])

    

cnt = [0]*N
for n in range(N):
    cnt[u.parent[n]] = 1
    

print(sum(cnt))

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.total = 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 same_check(self, x, y):
        return self.par[x] == self.par[y]
    def unite(self, x, y):
        if self.same_check(x, y):
            return
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.total -= 1
        else:
            self.par[y] = x
            self.total -= 1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
n,m = map(int, input().split())
union = UnionFind(n)
for i in range(m):
    x,y,z = map(int, input().split())
    union.unite(x-1, y-1)
print(union.total)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, N):
        # par[a]=b : b is parent of a
        self.par = [i for i in range(N)]
    
    def root(self, x):
        if self.par[x] == x: return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]
    
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry: self.par[max(rx,ry)] = min(rx,ry)

    def same(self, x, y):
        return self.root(x) == self.root(y)
            
N, M = list(map(int, input().split()))
uf = UnionFind(N)

edges = [list(map(int, input().split())) for i in range(M)]
for u, v, w in edges:
    uf.unite(u-1, v-1)

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

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)
        self.total = 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 same_check(self, x, y):
        return self.par[x] == self.par[y]
    def unite(self, x, y):
        if self.same_check(x, y):
            return
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.total -= 1
        else:
            self.par[y] = x
            self.total -= 1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
n,m = map(int, input().split())
union = UnionFind(n)
for i in range(m):
    x,y,z = map(int, input().split())
    union.unite(x, y)
print(len(set(union.par))-1)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, N):
        # par[a]=b : b is parent of a
        self.par = [i for i in range(N)]
    
    def root(self, x):
        if self.par[x] == x: return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]
    
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry: self.par[rx] = ry

    def same(self, x, y):
        return self.root(x) == self.root(y)
            
N, M = list(map(int, input().split()))
uf = UnionFind(N)

edges = [list(map(int, input().split())) for i in range(M)]
for u, v, w in edges:
    uf.unite(u-1, v-1)

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

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)
        self.total = 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 same_check(self, x, y):
        return self.par[x] == self.par[y]
    def unite(self, x, y):
        if self.same_check(x, y):
            return
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.total -= 1
        else:
            self.par[y] = x
            self.total -= 1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
n,m = map(int, input().split())
union = UnionFind(n)
for i in range(m):
    x,y,z = map(int, input().split())
    union.unite(x, y)
print(union.total)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, N):
        # par[a]=b : b is parent of a
        self.par = [i for i in range(N)]
    
    def root(self, x):
        if self.par[x] == x: return x
        self.par[x] = self.root(self.par[x])
        return self.par[x]
    
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry: self.par[rx] = ry

    def same(self, x, y):
        return self.root(x) == self.root(y)
            
N, M = list(map(int, input().split()))
uf = UnionFind(N)

edges = [list(map(int, input().split())) for i in range(M)]
for u, v, w in edges:
    uf.unite(u-1, v-1)

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

Submission status: Wrong Answer

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

for i, j, k in paths:
    nodes[i-1].append(j-1)
    nodes[j-1].append(i-1)

queue = [0]
group = [N+1]*N
for i in range(N):
    group[i] = min(group[i], i)
    for node in nodes[i]:
        group[node] = min(group[node], group[i])


count = 0
for i in range(N):
    if group.count(i) > 0: count += 1
print(count)

Submission status: Wrong Answer

Solution code:
class DisjointSet:
    def __init__(self):
        self.rank = {}
        self.p = {}

    def makeSet(self, x):
        self.p[x] = x
        self.rank[x] = 0

    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 x == y:
            return
        if(self.rank[x] > self.rank[y]):
            self.p[y] = x
        else:
            self.p[x] = 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]


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

ds = DisjointSet()
for i in range(N):
    ds.makeSet(i+1)

for i in range(M):
    X, Y, Z = map(int, input().split())
    ds.unite(X, Y)

print(len(set(ds.p.values())))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

# -*- coding: utf-8 -*-
"""
Created on Sat Apr 13 09:53:12 2019

@author: Owner
"""
import numpy as np
import sys
import collections
import scipy.misc
import math
from operator import itemgetter
import itertools
import copy
import bisect

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


"""
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
dp = np.zeros((N+1, 4,4,4))
    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break
# 累積和
add = 1 # 問題によって決まる
res = 0
sums = [0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
for i in range(0, len(nums), 2):
    left = i
    right = min(i+add, len(nums))
    tmp = sums[right] - sums[left]
    res = max(tmp, res)

#２分探索
li, ri = bisect.bisect_left(p_ac, l[i]-1), bisect.bisect_right(p_ac, r[i]-1)    

#ソート関数
org_list = [3, 1, 4, 5, 2]
new_list = sorted(org_list)
print(org_list)
print(new_list)
# [3, 1, 4, 5, 2]
# [1, 2, 3, 4, 5]

#Distance Transformation
    for h in range(0,H):
        for w in range(0,W):
            if h == 0 and w == 0:
                pass
            elif h == 0:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h-1][W-w]+1)
            elif w == 0:   
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1)
            else:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1, D[H-h-1][W-w]+1, D[H-h][W-w]+2)
            d_max = max(D[H-h-1][W-w-1], d_max)

"""

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

    def find(self, x):
        """
        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 と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]
    
N, M = list(map(int, input().split()))
X = [0]*M
Y = [0]*M
Z = [0]*M

for m in range(M):
    X[m], Y[m], Z[m] = map(int, input().split())


    


def main(): 
    uf = UnionFind(N)
    for i in range(M):
        uf.union(X[m]-1, Y[m]-1)
    num = set()
    for n in range(N):
        num.add(uf.find(n))        
    print(len(num))
                
                
                
            
            
                

    
if __name__ == '__main__':
    main()

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 ans(self):
        print(len(set(self.par))-1)

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

for i in range(m):
    a,b,c=map(int,input().split())
    uf.union(a,b)

uf.ans()

Submission status: Wrong Answer

Solution code:
import re
a = []
def One(n,m,a):
    b = []
    k = 1
    d = [i+1 for i in range(n)]     
    b.append(a[0])
    b.append(a[1])
    if m!=1:
        for i in range(int((len(a)-3)/2)+1):
            if (a[(i+1)*2] not in b) and (a[2*i+3] not in b):
                k = k+1
                b.append(a[(i+1)*2])
                b.append(a[2*i+3])
            else:
                b.append(a[(i+1)*2])
                b.append(a[2*i+3])
    c = list(filter(lambda a:a not in b,d))
    return k+len(c)
n,m = map(int, input().split())
#s = [input() for i in range(m)]
for _ in range(m) :
    X, Y, Z = map(int, input().split())
    a.append(X)
    a.append(Y)
print(One(n,m,a))

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)]
        self.sizes = [1 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
            self.sizes[y] += self.sizes[x]
        else:
            self.parent[y] = x
            self.sizes[x] += self.sizes[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 size(self, x):
        return self.sizes[self.find(x)]


N,M = map(int, input().split())
#xyz = [[int(i) for i in input().split()] for j in range(N)]

u = UnionFind(N)

for m in range(M):
    xyz = [int(i)-1 for i in input().split()]
    u.unite(xyz[0],xyz[1])

    

ans = N
for n in range(N):
    if u.rank[n]:
        ans -= u.size(n)-1

print(ans)

Submission status: Wrong Answer

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

cnt = [1]*N
ans = 0
for m in range(M):
    xyz = [int(i)-1 for i in input().split()]
    if cnt[xyz[0]] == 1 and cnt[xyz[1]] == 1:
        ans += 1
    cnt[xyz[0]] = 0
    cnt[xyz[1]] = 0

    

ans += sum(cnt)

print(ans)

Submission status: Wrong Answer

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

cnt = [1]*N
ans = 0
for m in range(M):
    xyz = [int(i)-1 for i in input().split()]
    if xyz[0] == xyz[2]:
        if cnt[xyz[0]] == 1 and cnt[xyz[1]] == 1:
            ans += 1    
        cnt[xyz[0]] = 0
        cnt[xyz[1]] = 0
    elif xyz[1] == xyz[2]:
        if cnt[xyz[0]] == 1 and cnt[xyz[1]] == 1:
            ans += 1
        cnt[xyz[0]] = 0
        cnt[xyz[1]] = 0
    else:
        if cnt[xyz[0]] == 1 and cnt[xyz[1]] == 1 and cnt[xyz[2]] == 1:
            ans += 2
        elif cnt[xyz[0]] == 1 and cnt[xyz[1]] == 1:
            ans += 1
        elif cnt[xyz[1]] == 1 and cnt[xyz[2]] == 1:
            ans += 1
        cnt[xyz[0]] = 0
        cnt[xyz[1]] = 0
        cnt[xyz[2]] = 0
    #print(cnt)

ans += sum(cnt)

print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a = set()
for i in range(m):
  b,c,d = map(int,input().split())
  if b in a and c in a:
    m = m-1
    continue
  a.add(b)
  a.add(c)
print(n-m)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a = []
for i in range(m):
  b,c,d = map(int,input().split())
  if b in a and c in a:
    m = m-1
  a.append(b)
  a.append(c)
print(n-m)

Submission status: Wrong Answer

Solution code:
class Unionfind():
  def __init__(self,size):
    self.parent = [i for i in range(size)]
    self.rank = [0 for i 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
import collections
N,M = map(int,input().split())
t = Unionfind(N)
for _ in range(M):
  x,y,z = map(int,input().split())
  x,y = x-1,y-1
  t.unite(x,y)
ans = collections.Counter(t.parent)
print(len(ans))

Submission status: Wrong Answer

Solution code:
import collections
N,M = map(int,input().split())
v = [i for i in range(N)]
for _ in range(M):
  x,y,z = map(int,input().split())
  x,y = x-1,y-1
  v[y] = x
for i in range(N):
  if v[i]!=i:
    x = i
    while v[x]!=x:
      x = v[x]
    v[i]=x
ans = collections.Counter(v)
print(len(ans))

Submission status: Wrong Answer

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

parent = [i for i in range(N+1)]
rank = [0] * (N+1)

def root(x) :
	while x != parent[x] :
		x = parent[x]
	
	return x

def unite(x, y) :
	root_x = root(x)
	root_y = root(y)

	if root_x == root_y :
		return

	if (rank[root_x] < rank[root_y]) :
		parent[root_x] = root_y
	else :
		parent[root_y] = root_x
		if rank[root_x] == rank[root_y] :
			rank[root_x] += 1

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

print(len(set(parent)) - 1)

Submission status: Wrong Answer

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

checked = [x for x in range(1,n+1)] #checked = 0
ans=n
for i in range(m):
    x,y,z = map(int,input().split())
    if x in checked and y in checked:
        checked[x-1]=0
        checked[y-1]=0
        ans-=1 #no check
    elif x in checked or y in checked:
        checked[x-1]=0
        checked[y-1]=0
        ans-=1 #one check
    else:
        pass
print(ans)

Submission status: Wrong Answer

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

no_hints = [i for i in range(1, N+1)]
budgets = []
for i in range(1, M+1):
    x, y, z = list(map(int, input().split()))
    if x in no_hints:
        no_hints.remove(x)
    if y in no_hints:
        no_hints.remove(y)

    is_new = True
    for j, budget in enumerate(budgets):
        if x in budget:
            budgets[j].append(y)
            is_new = False
            continue
        if y in budget:
            budgets[j].append(x)
            is_new = False
            continue
    if is_new:
        budgets.append([x, y])

print(len(budgets) + len(no_hints))

Submission status: Wrong Answer

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

checked = [x for x in range(1,n+1)] #checked = 0
xyz.sort()
ans=n
for i in xyz:
    x,y,z = i
    if x in checked and y in checked:
        checked[x-1]=0
        checked[y-1]=0
        ans-=1 #no check
    elif x in checked or y in checked:
        checked[x-1]=0
        checked[y-1]=0
        ans-=1 #one check
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N, M = map(int, input().split())
A = [0]*N
input_X = []
input_Y = []
count = 0
zero_lis = []
for _ in range(M):
    X, Y, _ = map(int, input().split())
    input_X.append(X)
    input_Y.append(Y)
flag = True
while flag:
    flag = False
    for X, Y in zip(input_X, input_Y):
        if A[X-1] == 1 or A[Y-1] == 1:
            A[X-1], A[Y-1] = 1, 1
        else:
            zero_lis.append(X-1)
            zero_lis.append(Y-1)
            flag = True
    for num, _ in Counter(zero_lis).most_common():
        if A[num] != 1:
            A[num] = 1
            count += 1
            zero_lis.clear()
            break
for a in A:
    if a == 0:
        count += 1
print(count)

Submission status: Wrong Answer

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

p = list(range(n))


def find(x):
    if p[x] != x:
        p[x] = find(p[x])
    return p[x]


def union(x, y):
    x, y = find(x), find(y)
    p[y] = x


for i in range(m):
    x, y, z = [int(i) - 1 for i in input().split()]
    if find(x) != find(y):
        union(x, y)

print(len(set(p)))

Submission status: Wrong Answer

Solution code:
def solve():
    N, M = [int(_) for _ in raw_input().split()]
    grp = [0] * N
    tmp_grp = 0
    closed_grp = set()
    for i in range(M):
        Xi, Yi, Zi = [int(_) for _ in raw_input().split()]
        if grp[Xi - 1] == 0 and grp[Yi - 1] == 0:
            tmp_grp += 1
            grp[Xi - 1] = tmp_grp
            grp[Yi - 1] = tmp_grp
        elif grp[Xi - 1] != 0:
            if grp[Xi - 1] == grp[Yi - 1]:
                closed_grp.add(grp[Xi - 1])
            else:
                grp[Yi - 1] = grp[Xi - 1]
        elif grp[Yi - 1] != 0:
            if grp[Xi - 1] == grp[Yi - 1]:
                closed_grp.add(grp[Xi - 1])
            else:
                grp[Xi - 1] = grp[Yi - 1]
    ret = tmp_grp - len(closed_grp)
    for i in range(N):
        if grp[i] == 0:
            ret += 1
    print str(ret)

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
def solve():
    N, M = [int(_) for _ in raw_input().split()]
    grp = [0] * N
    tmp_grp = 0
    for i in range(M):
        Xi, Yi, Zi = [int(_) for _ in raw_input().split()]
        if grp[Xi - 1] == 0 and grp[Yi - 1] == 0:
            tmp_grp += 1
            grp[Xi - 1] = tmp_grp
            grp[Yi - 1] = tmp_grp
        elif grp[Xi - 1] != 0:
            grp[Yi - 1] = grp[Xi - 1]
        elif grp[Yi - 1] != 0:
            grp[Xi - 1] = grp[Yi - 1]
    ret = tmp_grp
    for i in range(N):
        if grp[i] == 0:
            ret += 1
    print str(ret)

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import re
def One(n,m,s):
    a = []
    b = []
    k = 1
    d = [i+1 for i in range(n)]     
    for i in range(m):
        a.append(re.findall(r"(\d+)\s",s[i])[0])
        a.append(re.findall(r"\s(\d+)\s",s[i])[0])
    b.append(a[0])
    b.append(a[1])
    if m!=1:
        for i in range(int((len(a)-3)/2)+1):
            if (a[(i+1)*2] not in b) and (a[2*i+3] not in b):
                k = k+1
                b.append(a[(i+1)*2])
                b.append(a[2*i+3])
            else:
                b.append(a[(i+1)*2])
                b.append(a[2*i+3])
    c = list(filter(lambda a:str(a) not in b,d))
    return k+len(c)
n,m = map(int, input().split())
s = [input() for i in range(m)]
print(One(n,m,s))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = [0]*N
count = 0
for _ in range(M):
    X, Y, _ = map(int, input().split())
    if A[X-1] == 0 and A[Y-1] == 0:
        count += 1
    A[X-1], A[Y-1] = 1, 1
for num in A:
    if num == 0:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
import sys


class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

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

    def unite(self, x, y):
        if self.is_same(x, y):
            return
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.root[rx] = ry
        else:
            self.root[ry] = rx
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

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

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    uft = UnionFind(N)
    for _ in range(M):
        x, y, _ = map(int, input().split())
        uft.unite(x, y)

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


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

Submission status: Wrong Answer

Solution code:
import sys


class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n)]
        self.rank = [0] * n

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

    def unite(self, x, y):
        if self.is_same(x, y):
            return
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.root[rx] = ry
        else:
            self.root[ry] = rx
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

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

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    uf = UnionFind(N)
    for _ in range(M):
        x, y, _ = map(int, input().split())
        uf.unite(x-1, y-1)

    return len(set(uf.root))


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

Submission status: Wrong Answer

Solution code:
N,M=input().split()
N,M=int(N),int(M)
dic = {}
count=N
for iii in range(M):
  [x,y,z]=input().split()
  z=int(z)
  if x not in dic or y not in dic:
    count-=1
  dic[x]=0
  dic[y]=0
print(count)