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 math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        for _ in range(num): return []
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list,zip(*read_all))

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

#強連結成分分解
#label：グループ数
#group[i]：i個目のノードが所属するグループ
def scc(N, G, RG):
    used = [False]*N
    group = [None]*N
    order = []
    def dfs(s):
        used[s] = 1
        for t in G[s]:
            if not used[t]:
                dfs(t)
        order.append(s)
    for i in range(N):
        if not used[i]:
            dfs(i)
    print(order)
    def rdfs(S,col):
        used[S[0]] = True
        while S:
            v1 = S.pop()
            for v1_to in RG[v1]:
                if not used[v1_to]:
                    used[v1_to] = True
                    S.append(v1_to)
            group[v1] = col
    used = [False]*N
    label = 0
    for s in reversed(order):
        if not used[s]:
            rdfs([s], label)
            label += 1
    return label, group

N,M = II()
X,Y,Z = Line(M,3)

graph = [[] for _ in range(N)]
for i in range(M):
    graph[X[i]-1].append(Y[i]-1)
    graph[Y[i]-1].append(X[i]-1)

label,group = scc(N,graph,graph)
print(label)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        for _ in range(num): return []
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list,zip(*read_all))

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

from operator import itemgetter
def index_sort(A):
    x = []
    for i,a in enumerate(A):
        x.append((a,i))
    return sorted(x, key=itemgetter(0),reverse=True)

N,M = II()
X,Y,Z = Line(M,3)

pair = defaultdict(list)
num = [0]*N
for i in range(M):
    pair[X[i]-1].append(Y[i]-1)
    pair[Y[i]-1].append(X[i]-1)
    num[X[i]-1] += 1
    num[Y[i]-1] += 1

num = index_sort(num)
decided = [False]*N
ans = 0
for i in range(N):
    if not decided[num[i][1]]:
        ans += 1
        decided[num[i][1]] = True
        for j in pair[num[i][1]]:
            decided[j] = True
    else:
        for j in pair[num[i][1]]:
            decided[j] = True

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        for _ in range(num): return []
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list,zip(*read_all))

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

from operator import itemgetter
def index_sort(A):
    x = []
    for i,a in enumerate(A):
        x.append((a,i))
    return sorted(x, key=itemgetter(0),reverse=True)

N,M = II()
X,Y,Z = Line(M,3)

pair = defaultdict(list)
num = [0]*N
for i in range(M):
    pair[X[i]-1].append(Y[i]-1)
    pair[Y[i]-1].append(X[i]-1)
    num[X[i]-1] += 1
    num[Y[i]-1] += 1

num = index_sort(num)
decided = [False]*N
ans = 0
for i in range(N):
    if not decided[num[i][1]]:
        ans += 1
        decided[num[i][1]] = True
        for j in pair[num[i][1]]:
            decided[j] = True

print(ans)

Submission status: Wrong Answer

Solution code:
#標準入力
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())
#辞書のkeyに値を、値に振り分け番号を
c = {}
sorting = 0
count = 0
for i in range(m):
    if x[i] in c and not(y[i] in c):
        c[y[i]] = c[x[i]]
    elif y[i] in c and not(x[i] in c):
        c[x[i]] = c[y[i]]
    elif x[i] in c and y[i] in c:
        if c[x[i]] != c[y[i]]:
            for key,word in c.items():
                if word == c[y[i]]:
                    c[key] = c[x[i]]
    else:
        c[x[i]] = sorting
        c[y[i]] = sorting
        sorting += 1
#振り分け番号の種類数を答える
keylist = []
wordlist = []
for key, word in c.items():
    keylist.append(key)
    wordlist.append(word)
setword = set(wordlist)
#x,yで言及されなかった1~nの個数を足して出力
setn = set(range(1,n+1))
notmentionxy = setn - set(keylist)
print(len(setword) + len(notmentionxy))

Submission status: Wrong Answer

Solution code:
#標準入力
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())
#辞書のkeyに値を、値に振り分け番号を
c = {}
sorting = 0
count = 0
for i in range(m):
    if x[i] in c and not(y[i] in c):
        c[y[i]] = c[x[i]]
    elif y[i] in c and not(x[i] in c):
        c[x[i]] = c[y[i]]
    elif x[i] in c and y[i] in c:
        if c[x[i]] != c[y[i]]:
            count += 1
    else:
        c[x[i]] = sorting
        c[y[i]] = sorting
        sorting += 1
#振り分け番号の種類数を答える
keylist = []
wordlist = []
for key, word in c.items():
    keylist.append(key)
    wordlist.append(word)
setword = set(wordlist)
#x,yで言及されなかった1~nの個数を足して出力
setn = set(range(1,n+1))
notmentionxy = setn - set(keylist)
print(len(setword) + len(notmentionxy) - count)

Submission status: Wrong Answer

Solution code:
#標準入力
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())
#辞書のkeyに値を、値に振り分け番号を
c = {}
sorting = 0
for i in range(m):
    if x[i] in c:
        c[y[i]] = c[x[i]]
    elif y[i] in c:
        c[x[i]] = c[y[i]]
    else:
        c[x[i]] = sorting
        c[y[i]] = sorting
        sorting += 1
#振り分け番号の種類数を答える
keylist = []
wordlist = []
for key, word in c.items():
    keylist.append(key)
    wordlist.append(word)
setword = set(wordlist)
#x,yで言及されなかった1~nの個数を足して出力
setn = set(range(1,n+1))
notmentionxy = setn - set(keylist)
print(len(setword) + len(notmentionxy))

Submission status: Wrong Answer

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

input = sys.stdin.readline

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

ans = list(range(N))
def root(a):
    if a==ans[a]:
        return a
    else:
        ans[a] = root(ans[a]) 
        return ans[a]

for _ in range(M):
    x, y, _ = map(lambda a: int(a)-1, input().split())
    rx, ry = root(x), root(y)
    if rx != ry:
        ans[ry] = rx


print(len(set(ans)))

Submission status: Wrong Answer

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

input = sys.stdin.readline

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

ans = list(range(N))
def root(a):
    if a==ans[a]:
        return a
    else:
        return root(ans[a])

for _ in range(M):
    x, y, _ = map(lambda a: int(a)-1, input().split())
    if root(x) != root(y):
        rx = root(x)
        ry = root(y)
        while y != ry:
            ans[y], y = rx, ans[y]
        ans[ry] = rx

print(len(set(ans)))

Submission status: Wrong Answer

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

input = sys.stdin.readline

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

ans = list(range(N))
def root(a):
    if a==ans[a]:
        return a
    else:
        return root(ans[a])

for _ in range(M):
    x, y, _ = map(lambda a: int(a)-1, input().split())
    if root(x) != root(y):
        rx = root(x)
        ry = root(y)
        while y != ry:
            ans[y], y = rx, ans[y]
        ans[ry] = rx

A = {}
for a in ans:
    A[a] = 1

print(len(A))

Submission status: Wrong Answer

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

ans = list(range(N))
def root(a):
    if a==ans[a]:
        return a
    else:
        return root(ans[a])

for _ in range(M):
    x, y, _ = map(lambda a: int(a)-1, input().split())
    if root(x) != root(y):
        rx = root(x)
        ry = root(y)
        while y != ry:
            ans[y], y = rx, ans[y]
        ans[ry] = rx

A = {}
for a in ans:
    A[a] = 1

print(len(A))

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
cnt = [0 for _ in range(n)]
ans = n
for _ in range(m):
  x,y,z = map(lambda x: int(x)-1, input().split())
  if cnt[x] & cnt[y] == 0:
    cnt[x] = 1
    cnt[y] = 1
    ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque

N, M = map(int, input().split())
E = defaultdict(list)
for i in range(M):
    x, y, z = map(int, input().split())
    E[x - 1].append(y - 1)
visited = [False] * N
ans = 0
q = deque()
for i in range(N):
    if not visited[i]:
        ans += 1
        visited[i] = True
        q.append(i)
        while q:
            nxt = q.pop()
            for j in E[nxt]:
                visited[j] = True
                q.append(j)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
# input関係の定義
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
# template


# PyPyだと再帰が遅いので注意
# BEGIN CUT HERE
class UnionFind():
    '''
    UnionFind木

    Parameters
    --------
        n (int): UnionFind木のサイズ

    Methods
    --------
        unite(x: int, y: int) -> None
            ノード x とノード y を結合する
        same(x: int, y: int) -> bool
            ノード x とノード y が同じ集合に属するか判定する
        size(x: int) -> int
            ノード x を含む集合の要素数を返す

    '''

    def __init__(self, n):
        self._data = [-1] * n

    def unite(self, x: int, y: int) -> bool:
        '''x と y を結合'''
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False  # 元々結合されている場合はFalseを返し終了する
        elif self._data[x] > self._data[y]:
            x, y = y, x  # swap
        self._data[x] += self._data[y]
        self._data[y] = x
        return True

    def root(self, x: int) -> int:
        '''ノード x の親を返す'''
        while self._data[x] >= 0:
            x = self._data[x]
        return self._data[x]

    def same(self, x: int, y: int) -> bool:
        '''x と y が同じグループに属するか判定'''
        return self.root(x) == self.root(y)

    def size(self, x: int) -> int:
        '''x を含むグループのノード数を返す'''
        return self._data[self.root(x)]

# END CUT HERE

# BEGIN CUT HERE
class QuickFind():
    def __init__(self, n):
        self.i2g = [i for i in range(n)]  # i2g[i] := アイテム i の所属するグループの番号
        self.g2i = [[i]for i in range(n)]  # g2i[g]: = グループ g に所属するアイテムたち

    def unite(self, ia, ib):
        '''アイテム ia の所属するグループとアイテム ib の所属するグループを 1 つにする'''
        # ia と ib が同じグループに属しているならば return
        if self.same(ia, ib):
            return
        # ia の所属するグループが ib の所属するグループより小さくならないようにする
        if len(self.g2i[self.i2g[ia]]) < len(self.g2i[self.i2g[ib]]):
            ia, ib = ib, ia
        ga, gb = self.i2g[ia], self.i2g[ib]
        # グループ gb に所属する全てのアイテムをグループ ga に移す
        for j in self.g2i[gb]:
            self.i2g[j] = ga
        self.g2i[ga].extend(self.g2i[gb])
        self.g2i[gb] = []


    def same(self, ia, ib):
        '''アイテム ia とアイテム ib は同じグループに所属しているか？'''
        return self.i2g[ia] == self.i2g[ib]

    def size(self, x: int) -> int:
        '''アイテム x の属する集合のサイズを返す'''
        return len(self.g2i[self.i2g[x]])

    def group(self, x: int) -> list:
        '''アイテム x の属する集合を返す'''
        return self.g2i[self.i2g[x]]

    def __str__(self):
        '''デバッグ用出力'''
        return str([self.g2i[i] for i in range(len(self.g2i))if len(self.g2i[i]) != 0])
# END CUT HERE

def benchmark():
    import random
    N = 10**6
    uf = UnionFind(N)
    a = [(random.randint(0, 1), random.randint(0, N - 1), random.randint(0, N - 1)) for i in range(N)]
    for t, x, y in a:
        if t == 0:
            uf.unite(x, y)
        else:
            uf.same(x, y)



def AOJ_DSL_1_A():
    """http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A&lang=jp"""
    n, q = mi()
    uf = UnionFind(n)
    for _ in range(q):
        t, x, y = mi()
        if t == 0:
            uf.unite(x, y)
        else:
            if uf.same(x, y):
                print(1)
            else:
                print(0)
# verified on 2019/07/02


def ABC120_D():
    """https://atcoder.jp/contests/abc120/submissions/6094323"""
    n, m = mi()
    a = [0] * m
    b = [0] * m
    for i in range(m):
        a[i], b[i] = mi()

    uf = UnionFind(n)
    ans = [0] * (m + 1)
    ans[m] = n * (n - 1) // 2

    for i in range(m - 1, -1, -1):
        a[i] -= 1
        b[i] -= 1
        ans[i] = ans[i + 1]
        if uf.same(a[i], b[i]):
            continue

        x = uf.size(a[i])
        y = uf.size(b[i])
        ans[i] -= x * y

        uf.unite(a[i], b[i])

    for i in range(1, m + 1):
        print(ans[i])

# verified on 2019/06/23
# Python3:616ms


def ABC126_E():
    """https://atcoder.jp/contests/abc126/submissions/6094497"""
    N, M = mi()
    uf = UnionFind(N)
    for i in range(M):
        _X, _Y, _Z = mi()
        uf.unite(_X - 1, _Y - 1)
    ans = 0
    for i in range(N):
        if uf.root(i) == i:
            ans += 1
    print(ans)
# verified on 2019/06/23
# Python3:468ms


def ABC131_F():
    """https://atcoder.jp/contests/abc131/submissions/6094709"""
    from collections import defaultdict
    MAX = 100010
    uf = UnionFind(2 * MAX)
    N = ii()
    for i in range(N):
        x, y = mi()
        uf.unite(x, y + MAX)

    mx = defaultdict(int)
    for i in range(MAX):
        mx[uf.root(i)] += 1
    my = defaultdict(int)
    for i in range(MAX, 2 * MAX):
        my[uf.root(i)] += 1
    ans = 0
    for i in range(2 * MAX):
        ans += mx[i] * my[i]
    print(ans - N)
# verified on 2019/06/23
# Python:580ms

def ATC001B():
    N, Q = mi()
    ANS = ["No", "Yes"]
    uf = QuickFind(N)
    for _ in range(Q):
        P, A, B = mi()
        if P == 0:
            uf.unite(A, B)
        elif P == 1:
            print(uf.group(A))
            print(ANS[uf.same(A, B)])

if __name__ == '__main__':
    # AOJ_DSL_1_A()
    # ABC120_D()
    ABC126_E()
    # ABC131_F()
    # ATC001B()
    # import cProfile
    # cProfile.run('benchmark()', sort=0)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
known = set()
unknown = set(range(1,n+1))
cost = 0
for i in range(m):
  x,y,z = map(int,input().split())
  if x in known and y in known:
    pass
  elif x in known and y not in known:
    known.add(y)
  elif x not in known and y in known:
    known.add(x)
  elif x not in known and y not in known:
    cost+=1
    known.update((x,y))
unknown = unknown - known
print(len(unknown)+cost)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
ect = [0 for _ in range(n)]
for _ in range(m):
  a,b,c = map(int,input().split())
  a -= 1
  b -= 1
  if ect[a] == ect[b] == 1:
    pass
  elif ect[a] == ect[b] == 0 and sum(ect) == n-2:
    pass
  else:
    n -= 1
  ect[a] = 1
  ect[b] = 1
print(n)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
ect = [0 for _ in range(n)]
for _ in range(m):
  a,b,c = map(int,input().split())
  a -= 1
  b -= 1
  if ect[a] == 0 or ect[b] == 0:
    n -= 1
  ect[a] = 1
  ect[b] = 1
print(n)

Submission status: Wrong Answer

Solution code:
a = input().split()
N = int(a[0])
M = int(a[1])

l = []
f = []
for i in range(N):
	temp = []
	l.append(temp)
	f.append(0)

for i in range(M):
	b = input().split()
	X = int(b[0]) - 1
	Y = int(b[1]) - 1
	l[X].append(Y)

cnt = 0
for i in range(N):
	if(f[i] == 0):
		cnt += 1
		f[i] = cnt
		if(len(l[i]) != 0):
			for j in range(len(l[i])):
				f[l[i][j]] = cnt
	elif(f[i] != 0):
		if(len(l[i]) != 0):
			for j in range(len(l[i])):
				f[l[i][j]] = f[i]
			
print(cnt)

Submission status: Wrong Answer

Solution code:
def solve(string):
    n, m, *xyz = map(int, string.split())
    t = [-1] * (n + 1)
    for x, y, z in zip(*[iter(xyz)] * 3):

        def search(x, y):
            tmp = [y]
            curr = x
            while curr != -1:
                tmp.append(curr)
                curr = t[curr]
            root = tmp.pop()
            for _t in tmp:
                t[_t] = root

        search(x, y)
    return str(t[1:].count(-1))


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m)+'\n'.join([input() for _ in range(m)])))

Submission status: Wrong Answer

Solution code:
def solve(string):
    n, m, *xyz = map(int, string.split())
    t = [-1] * (n + 1)
    for x, y, z in zip(*[iter(xyz)] * 3):

        def search(x, y):
            tmp = [y]
            curr = x
            while curr != -1:
                tmp.append(curr)
                curr = t[curr]
            root = tmp.pop()
            for _t in tmp:
                t[_t] = root

        search(x, y)
    return str(t[1:].count(-1))


if __name__ == '__main__':
    print(solve(input()))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
a=[[] for i in range(n)]
for i in range(m):
    u,v,w=map(int,input().split())
    a[u-1].append((v-1,w))
    a[v-1].append((u-1,w))
b=[None for i in range(n)]
def k(v,dis):
    b[v]=dis
    for next_v,w in a[v]:
        if b[next_v]!=None:
            continue
        if w%2==0:
            k(next_v,dis)
        else:
            k(next_v,1-dis)
c=0
c2=0
for i in range(n):
    if a[i]!=[] and b[i]==None:
        k(i,0)
        c2+=1
for i in b:
    if i==None:
        c2+=1
    else:
        c+=1
print(m+1-c+c2)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
a=[None for i in range(n)]
count=0
b=[]
for i in range(m):
    x,y,z=map(int,input().split())
    b.append((x,y,z))
for x,y,z in b:
    if z%2:
        if a[x-1]!=None and a[y-1]!=None:
            count-=1
        elif a[x-1]!=None:
            a[y-1]=1-a[x-1]
        elif a[y-1]!=None:
            a[x-1]=1-a[y-1]
        else:
            count+=1
            a[x-1]=0
            a[y-1]=1-a[x-1]
    else:
        if a[x-1]!=None and a[y-1]!=None:
            count-=1
        elif a[x-1]!=None:
            a[y-1]=a[x-1]
        elif a[y-1]!=None:
            a[x-1]=a[y-1]
        else:
            count+=1
            a[x-1]=0
            a[y-1]=a[x-1]
for i in a:
    if i==None:
        count+=1
print(count)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
a=[None for i in range(n)]
count=0
b=[]
for i in range(m):
    x,y,z=map(int,input().split())
    b.append((x,y,z))
b.sort()
for x,y,z in b:
    if z%2:
        if a[x-1]!=None and a[y-1]!=None:
            count-=1
        elif a[x-1]!=None:
            a[y-1]=1-a[x-1]
        elif a[y-1]!=None:
            a[x-1]=1-a[y-1]
        else:
            count+=1
            a[x-1]=0
            a[y-1]=1-a[x-1]
    else:
        if a[x-1]!=None and a[y-1]!=None:
            count-=1
        elif a[x-1]!=None:
            a[y-1]=a[x-1]
        elif a[y-1]!=None:
            a[x-1]=a[y-1]
        else:
            count+=1
            a[x-1]=0
            a[y-1]=a[x-1]
for i in a:
    if i==None:
        count+=1
print(count)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
a=[None for i in range(n)]
count=0
b=[]
for i in range(m):
    x,y,z=map(int,input().split())
    b.append((x,y,z))
b.sort()
for x,y,z in b:
    if z%2:
        if a[x-1]!=None:
            a[y-1]=1-a[x-1]
        elif a[y-1]!=None:
            a[x-1]=1-a[y-1]
        else:
            count+=1
            a[x-1]=0
            a[y-1]=1-a[x-1]
    else:
        if a[x-1]!=None:
            a[y-1]=a[x-1]
        elif a[y-1]!=None:
            a[x-1]=1-a[y-1]
        else:
            count+=1
            a[x-1]=0
            a[y-1]=a[x-1]
for i in a:
    if i==None:
        count+=1
print(count)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
a=[None for i in range(n)]
count=0
b=[]
for i in range(m):
    x,y,z=map(int,input().split())
    b.append((x,y,z))
b.sort()
for x,y,z in b:
    if z%2:
        if a[x-1]!=None:
            a[y-1]=1-a[x-1]
        else:
            count+=1
            a[x-1]=0
            a[y-1]=1-a[x-1]
    else:
        if a[x-1]!=None:
            a[y-1]=a[x-1]
        else:
            count+=1
            a[x-1]=0
            a[y-1]=a[x-1]
for i in a:
    if i==None:
        count+=1
print(count)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
a=[None for i in range(n)]
count=0
for i in range(m):
    x,y,z=map(int,input().split())
    if z%2:
        if a[x-1]!=None:
            a[y-1]=1-a[x-1]
        else:
            count+=1
            a[x-1]=0
            a[y-1]=1-a[x-1]
    else:
        if a[x-1]!=None:
            a[y-1]=a[x-1]
        else:
            count+=1
            a[x-1]=0
            a[y-1]=a[x-1]
for i in a:
    if i==None:
        count+=1
print(count)

Submission status: Wrong Answer

Solution code:
import bisect

def find(l,a):
  i = bisect.bisect_left(l, a)
  if i < len(l) and l[i] == a:
    return True
  else:
    return False

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

G = []
for j in range(M):
  X,Y,Z = map(int, A[j])
  XY = [X,Y]
  flag = True
  for g in G:
    for i in range(len(XY)):
      if find(g,XY[i]):
        if not find(g, XY[1-i]):
          bisect.insort_left(g, XY[1-i])
        flag = False
        break
    if not flag:
      break
  if flag:
    G.append(XY)
#print(G)
ans = N
for g in G:
  ans -= (len(g) - 1)
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

def find(l,a):
  i = bisect.bisect_left(l, a)
  if i < len(l) and l[i] == a:
    return True
  else:
    return False

N, M = map(int, input().split())
G = []
for i in range(M):
  X,Y,Z = map(int, input().split())
  XY = [X,Y]
  flag = True
  for g in G:
    for i in range(len(XY)):
      if find(g,XY[i]):
        if not find(g, XY[1-i]):
          bisect.insort_left(g, XY[1-i])
        flag = False
        break
    if not flag:
      break
  if flag:
    G.append(XY)
#print(G)
ans = N
for g in G:
  ans -= (len(g) - 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 show(self):
        return self.par
        
def main():
    import sys
    
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = UnionFind(N)
    for _ in range(M):
        x,y,z = map(int, input().split())
        A.union(x,y)
    B = set(A.show()[1:])
    print(len(B))
    
    
    
main()

Submission status: Wrong Answer

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

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 same_check(self, x, y):
        return self.find(x) == self.find(y)

    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

uf = UnionFind(N)
for xyz in XYZ:
    uf.union(xyz[0], xyz[1])

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

N, M = map(int, input().split())
L = [[int(v) - 1 for v in input().split()] for _ in range(M)]

class UnionFind:
    def __init__(self, n):
        self.data = [0] * N
        for i in range(N):
            self.data[i] = i
            
    def get_root(self, x):
        r = self.data[x]
        if r == x:
            return r
        p = self.get_root(r)
        self.data[x] = p
        return p
    
    def unite(self, x, y):
        rx = self.get_root(x)
        ry = self.get_root(y)
        
        if rx != ry:
            self.data[rx] = ry
            
    def same(self, x, y):
        return self.get_root(x) == self.get_root(y)
    
u = UnionFind(N)
for a, b, _ in L:
    u.unite(a, b)
    
exit()
    
s = set()
for i in range(N):
    s.add(u.get_root(i))

print(len(s))

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.depth  = [0] * n
        self.parent = list(range(n))

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

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.depth[x] < self.depth[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.depth[x] == self.depth[y]:
                self.depth[x] += 1

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

    def size(self, x):
        return self.depth[self.ind(x)]


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

T = UnionFind(N)

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

print(len(set(T.parent)))

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
cnt = 0
L = []
for i in range(m):
  x,y,z = map(int,input().split())
  if not x in L:
    cnt += 1
  L += [x,y]
  L = list(set(L))
ans = cnt + (n - len(L))  
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

done = [False] * N
ans  = N

for m in range(M):
    X, Y, Z = map(int, input().split())
    X      -= 1
    Y      -= 1
    if   done[X] == False and done[Y] == False:
          ans    -= 1
          done[X] = True
          done[Y] = True
    elif done[X] == True and done[Y] == True:
        continue
    else:
          ans    -= 1
          done[X] = True
          done[Y] = True

print(ans)

Submission status: Wrong Answer

Solution code:
K = 1

Submission status: Wrong Answer

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
import math

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

head = [-1 for i in range(N)]
for i in range(M):

	node = XYZ[i][1]
	node_base = XYZ[i][0]
	node_list=[node]
	node = head[node - 1]
	node_list.append(node)
	while node != -1:
		node = head[node - 1]
		node_list.append(node)
	node_list.remove(-1)
	if node_list[-1] != node_base:
		head[node_list[-1] - 1] = node_base
	x = node_list.pop()
	if len(node_list) > 0:
		for i in node_list:
			head[i - 1] = x

	#print(node,node_base,head,node_list)

num = 0
for i in head:
	if i == -1:
		num +=1
print(num)

Submission status: Wrong Answer

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
import math

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

head = [-1 for i in range(N)]
for i in range(M):

	node = XYZ[i][1]
	node_base = XYZ[i][0]
	node_list=[node]
	node = head[node - 1]
	node_list.append(node)
	while node != -1:
		node = head[node - 1]
		node_list.append(node)
	node_list.remove(-1)
	if node_list[-1] != node_base:
		for x in node_list:
			head[x - 1] = node_base

	#print(node, head,node_list)

num = 0
for i in head:
	if i == -1:
		num +=1
print(num)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

sys.setrecursionlimit(50000000)




class UnionFind():
    def __init__(self,n):
        self.par = [i for i in range(n+1)]
        self.rank = [0 for _ in range(n+ 1)]
    def find(self,x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find(self.par[x])
        return  self.par[x]

    def same_check(self,a,b):
            return self.find(a) == self.find(b)

    def union(self,x,y):
        if self.rank[x] > self.rank[y]:
            self.par[y] = self.par[x]
        else:
            self.par[x] = self.par[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1



N,M = list(map(int, input().split(" ")))
uf = UnionFind(N)
for _ in range(M):
    x,y,_ = list(map(int, input().split(" ")))
    uf.union(x,y)
anss = set()
for i in range(1,N+1):
    anss.add(uf.find(i))
print(len(anss))