Problem:


Score : 500 points

Problem Statement

There are N cards placed face down in a row. On each card, an integer 1 or 2 is written.

Let A_i be the integer written on the i-th card.

Your objective is to guess A_1, A_2, ..., A_N correctly.

You know the following facts:

For each i = 1, 2, ..., M, the value A_{X_i} + A_{Y_i} + Z_i is an even number.

You are a magician and can use the following magic any number of times:

Magic: Choose one card and know the integer A_i written on it. The cost of using this magic is 1.

What is the minimum cost required to determine all of A_1, A_2, ..., A_N?

It is guaranteed that there is no contradiction in given input.

Constraints

All values in input are integers.

2 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq X_i < Y_i \leq N

1 \leq Z_i \leq 100

The pairs (X_i, Y_i) are distinct.

There is no contradiction in input. (That is, there exist integers A_1, A_2, ..., A_N that satisfy the conditions.)

Input

Input is given from Standard Input in the following format:

N M
X_1 Y_1 Z_1
X_2 Y_2 Z_2
\vdots
X_M Y_M Z_M

Output

Print the minimum total cost required to determine all of A_1, A_2, ..., A_N.

Sample Input 1

3 1
1 2 1

Sample Output 1

2

You can determine all of A_1, A_2, A_3 by using the magic for the first and third cards.

Sample Input 2

6 5
1 2 1
2 3 2
1 3 3
4 5 4
5 6 5

Sample Output 2

2

Sample Input 3

100000 1
1 100000 100

Sample Output 3

99999



Sample input:
3 1
1 2 1


Sample output:
2

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
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)
A=UnionFind(n)
for i in range(m):
    a,b,c=map(int,input().split())
    A.union(a,b)
List=A.par
del List[0]
List=set(List)
print(len(List))

Submission status: Wrong Answer

Solution code:
#1 or 2
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())
XY = []
for i in range(M):
    XY.append([X[i],Y[i]])
XY.sort()
R = [1]*N
for i in range(M):
    if R[XY[i][1]-1] == 0:
        R[XY[i][0]-1] = 0
    else:
        R[XY[i][1]-1] = 0
count = 0
for i in range(N):
    if R[i] != 0:
        count = count + 1
print(count)

Submission status: Wrong Answer

Solution code:
#1 or 2
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())
for i in range(M):
    if X[i] > Y[i]:
        L = X[i]
        X[i] = Y[i]
        Y[i] = L
XY = []
for i in range(M):
    XY.append([X[i],Y[i]])
XY.sort()
R = [1]*N
for i in range(M):
    if R[XY[i][1]-1] == 0:
        R[XY[i][0]-1] = 0
    else:
        R[XY[i][1]-1] = 0
count = 0
for i in range(N):
    if R[i] != 0:
        count = count + 1
print(count)

Submission status: Wrong Answer

Solution code:
#1 or 2
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())
for i in range(M):
    if X[i] > Y[i]:
        L = X[i]
        X[i] = Y[i]
        Y[i] = L
XY = []
for i in range(M):
    XY.append([X[i],Y[i]])
XY.sort()
R = [1]*N
for i in range(M):
    if R[XY[i][1]-1] == 0:
        R[XY[i][0]-1] = 0
    else:
        R[XY[i][1]-1] = 0
count = 0
for i in range(N):
    if R[i] != 0:
        count = count + 1
print(XY)
print(count)

Submission status: Wrong Answer

Solution code:
#1 or 2
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())
for i in range(M):
    if X[i] > Y[i]:
        L = X[i]
        X[i] = Y[i]
        Y[i] = L
XY = []
for i in range(M):
    XY.append([X[i],Y[i]])
XY.sort()
R = [1]*N
for i in range(M):
    if R[XY[i][1]-1] == 0:
        pass
    else:
        R[XY[i][1]-1] = 0
count = 0
for i in range(N):
    if R[i] != 0:
        count = count + 1
print(count)

Submission status: Wrong Answer

Solution code:
#1 or 2
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())
for i in range(M):
    if X[i] > Y[i]:
        L = X[i]
        X[i] = Y[i]
        Y[i] = L
R = [1]*N
for i in range(M):
    if R[Y[i]-1] == 0:
        pass
    else:
        R[Y[i]-1] = 0
count = 0
for i in range(N):
    if R[i] != 0:
        count = count + 1
print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
from collections import deque

input = sys.stdin.readline
def dfs(start, G):
    stack = deque()
    stack.append(start)
    visited = [0]*len(G)
    while stack:
        label = stack.pop()
        visited[label-1]= 1
        for i in G[label-1]:
          if not visited[i-1]:
            #visited[label-1]= 1
            stack.append(i)
    return visited    
 
N, M =map(int, input().split())
G  = [[] for _ in range(N)]
for i in range(M):
    a,b ,_= map(int, input().split())
    G[a-1].append(b)
    G[b-1].append(a)
 
count = 0
"""
visit = np.array([0]*N)
for i in range(1,N+1):
  if visit[i-1]:
    continue
  if G[i-1]:  
    v_temp = dfs(i,G)
    visit = np.logical_or(visit, v_temp)
  else:
    visit[i-1] = 1
  count += 1
"""
 
print(count)

Submission status: Wrong Answer

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

parent=[i for i in range(n)]
rank=[0 for i in range(n)]

def find(a):
  if parent[a]==a:
    return a
  else:
    return find(parent[a])

def union(a,b):
  ar=find(a)
  br=find(b)
  if ar==br:
    return
  if rank[a]>rank[b]:
    parent[b]=a
  else:
    parent[a]=b
    if rank[a]==rank[b]:
      rank[a]+=1
      
def same(a,b):
  ar=find(a)
  br=find(b)
  return ar==br

q=[None]*m

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

for i in range(len(q)):
  union(q[i][0],q[i][1])
  
roots=set()
for p in parent:
  roots.add(find(p))
  
print(len(roots))

Submission status: Wrong Answer

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

parent=[i for i in range(n)]
rank=[0 for i in range(n)]

def find(a):
  while parent[a]!=a:
    a=parent[a]
  return parent[a]

def union(a,b):
  ar=find(a)
  br=find(b)
  if ar==br:
    return
  if rank[a]>rank[b]:
    parent[b]=a
  else:
    parent[a]=b
    if rank[a]==rank[b]:
      rank[a]+=1
      
def same(a,b):
  ar=find(a)
  br=find(b)
  return ar==br

q=[None]*m

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

for i in range(len(q)):
  union(q[i][0],q[i][1])
  
roots=set()
for p in parent:
  roots.add(find(p))
  
print(len(roots))

Submission status: Wrong Answer

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

parent=[i for i in range(n)]
rank=[0 for i in range(n)]

def find(a):
  while parent[a]!=a:
    a=parent[a]
  return a

def union(a,b):
  ar=find(a)
  br=find(b)
  if ar==br:
    return
  if rank[a]>rank[b]:
    parent[b]=a
  else:
    parent[a]=b
    if rank[a]==rank[b]:
      rank[a]+=1
      
def same(a,b):
  ar=find(a)
  br=find(b)
  return ar==br

q=[None]*m

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

for i in range(len(q)):
  union(q[i][0],q[i][1])
  
roots=set()
for p in parent:
  roots.add(find(p))
  
print(len(roots))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
res=[0]*n

datas=[None]*m
for i in range(m):
  x,y,z=map(int,input().split())
  datas[i]=[min(x-1,y-1),max(x-1,y-1)]

datas=sorted(datas,key=lambda x:x[0])

maxi=0
for i in range(len(datas)):
  d=datas[i]
  if res[d[0]]==0 and res[d[1]]==0:
    maxi+=1
    res[d[0]]=maxi
    res[d[1]]=maxi
  elif res[d[0]]==0 and res[d[1]]!=0:
    res[d[0]]=res[d[1]]
  elif res[d[0]]!=0 and res[d[1]]==0:
    res[d[1]]=res[d[0]]

print(res.count(0)+maxi)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
res=[0]*n

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

maxi=0
for i in range(len(datas)):
  if res[datas[i][0]-1]==0 and res[datas[i][1]-1]==0:
    maxi+=1
    res[datas[i][0]-1]=maxi
    res[datas[i][1]-1]=maxi
  elif res[datas[i][0]-1]==0 and res[datas[i][1]-1]!=0:
    res[datas[i][0]-1]=res[datas[i][1]-1]
  elif res[datas[i][0]-1]!=0 and res[datas[i][1]-1]==0:
    res[datas[i][1]-1]=res[datas[i][0]-1]
    
print(res.count(0)+maxi)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
datas=[None]*m
for i in range(m):
  x,y,z=map(int,input().split())
  datas[i]=[x,y]
  
sets=[]
sets.append(set([datas[0][0],datas[0][1]]))

for i in range(1,len(datas)):
  found=False
  for j in range(len(sets)):
    if datas[i][0] in sets[j] or datas[i][1] in sets[j]:
      sets[j].add(datas[i][0])
      sets[j].add(datas[i][1])
      found=True
      break
  if not found:
    sets.append(set([datas[i][0],datas[i][1]]))

allsets=set()
for i in range(len(sets)):
  allsets=allsets | sets[i]
  
iso=n-len(allsets)

print(iso+len(sets))

Submission status: Wrong Answer

Solution code:
class Unionfind():
    def __init__(self,N,weighted=False):
        self.root = list(range(N))
        self.depth = [1 for _ in range(N)]
        self.weighted = False
        if weighted:
            self.weighted = True
            self.weight = [0 for _ in range(N)]
    def find(self,x):
        if self.root[x] == x:
            return x
        else:
            r = self.find(self.root[x])
            if self.weighted:
                self.weight[x] += self.weight[self.root[x]]
            self.root[x] = r
            return r
    def unite(self,a,b,x=0):
        A = self.find(a)
        B = self.find(b)
        if self.weighted:
            wa = self.weight[a]
            wb = self.weight[b]
        if A == B:
            return
        elif self.depth[A] > self.depth[B]:
            self.root[B] = A
            self.depth[A] += self.depth[B]
            if self.weighted:
                self.weight[B] = wa -wb + d
        else:
            self.root[A] = B
            self.depth[B] += self.depth[A]
            if self.weighted:
                self.weight[A] = wb - wa - d
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)
root_set = set()
for e in uf.root:
    root_set.add(e)
print(len(root_set))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def main():
    n, m = map(int, input().split())
    # xy = [None]*m
    # grps = [set(map(int, input().split()))]
    grps = []
    ng = 0

    for _ in range(m):
        x, y, z = map(int, input().split())
        flag = True
        for grp in grps:
            if x in grp and y in grp:
                ng += 1
                flag = False
                break

            elif x in grp and y not in grp:
                grp.add(y)
                flag = False
                break

            elif x not in grp and y in grp:
                grp.add(x)
                flag = False
                break

        if flag:
            grps.append({x, y})

    for i in range(len(grps)):
        if not grps[i]:
            continue
        for j in range(i+1, len(grps)):
            if not grps[j]:
                continue
            dup = len(grps[i] & grps[j])
            if dup != 0:
                ng += dup-1
                grps[i] |= grps[j]
                grps[j].clear()

    ans = n - m + ng
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():

    N, M = map(int, input().split())
    parent = [i for i in range(N)]
    level = [1 for _ in range(N)]

    def find(i):
        if parent[i] != i:
            parent[i] = find(parent[i])
        return parent[i]

    def union(i, j):
        pi, pj = find(i), find(j)
        if pi != pj:
            if level[pi] < level[pj]:
                parent[i] = pj
                level[pj] = 1+level[pi]
            else:
                parent[j] = pi
                level[pj] = 1+level[pj]

    for _ in range(M):
        i, j, z = map(int, input().split())
        union(i-1, j-1)

    for i in range(N): find(i)

    ans = len(set(parent))
    return ans

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

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
f = [False for _ in range(n)]
a = [[] for _ in range(n)]
res = 0

def dfs(k):
    f[k] = True
    for g in a[k]:
        if not f[g]:
            dfs(g)

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

for i in range(n):
    if not f[i]:
        res += 1
        dfs(i)

print(res)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
f = [False for _ in range(n)]
a = [[] for _ in range(n)]
res = 0

def dfs(k):
    f[k] = True
    for g in a[k]:
        if not f[g]:
            dfs(g)

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

for i in range(n):
    if not f[i]:
        res += 1
        dfs(i)

print(res)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
f = [False for _ in range(n)]
a = [[] for _ in range(n)]
res = 0

def dfs(k):
    global f
    global a
    f[k] = True
    for g in a[i]:
        if not f[g]:
            dfs(g)

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

for i in range(0,n):
    if not f[i]:
        res += 1
        dfs(i)

print(res)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
lx = []
f = [False for _ in range(n)]
a = [[] for _ in range(n)]
for _ in range(m):
    x,y,z = map(int,input().split())
    a[x-1].append(y-1)

def dfs(i):
    f[i] = True
    for g in a[i]:
        if not f[g]:
            dfs(g)
res = 0
for i in range(n):
    if not f[i]:
        res += 1
        dfs(i)

print(res)

Submission status: Wrong Answer

Solution code:
# 2019/10/10

class unionfind():
    def __init__(self,n):
        self.par=list(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 is_same(self,x,y):
        return self.find(x)==self.find(y)
    
    def unite(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

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

uf=unionfind(n)

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

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

Submission status: Wrong Answer

Solution code:
# 2019/10/10

class unionfind():
    def __init__(self,n):
        self.par=list(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 is_same(self,x,y):
        return self.find(x)==self.find(y)
    
    def unite(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

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

uf=unionfind(n)

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

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

Submission status: Wrong Answer

Solution code:
# 2019/10/10

class unionfind():
    def __init__(self,n):
        self.par=list(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 is_same(self,x,y):
        return self.find(x)==self.find(y)
    
    def unite(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

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

uf=unionfind(n)

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

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

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n, k = LI()
    s = S()
    s[k-1] = s[k-1].lower()
    print("".join(s))

    return

#B
def B():
    s = S()
    a = int("".join(s[:2]))
    b = int("".join(s[2:]))
    if 0 < a <= 12:
        if 0 < b <= 12:
            print("AMBIGUOUS")
        else:
            print("MMYY")
    elif a == 0:
        if 0 < b <= 12:
            print("YYMM")
        else:
            print("NA")
    else:
        if 0 < b <= 12:
            print("YYMM")
        else:
            print("NA")
    return

#C
def C():
    n, k = LI()
    ans = 0
    if k == 1:
        print(1)
        return
    nibuiti = [None for i in range(int(math.log2(k) + 1))]
    for num in range(int(math.log2(k) + 1)):
        if num == 0:
            nibuiti[num] = 1 / 2
            continue
        nibuiti[num] = nibuiti[num-1]/2
        
    for i in range(1, n + 1):
        if i >= k:
            ans += 1
            continue
        b = nibuiti[int(math.log2((k - 1) // i))]
        ans += b
    print(ans/n)
    return

#D
def D():
    n = II()
    color = [0 for i in range(n)]
    edge = [[] for i in range(n)]
    for i in range(n - 1):
        v, u, w = LI_()
        edge[v].append((u,w+1))
        edge[u].append((v,w+1))
    check = [True for i in range(n)]
    for i in range(n):
        q = deque()
        q.append(i)
        
        while q:
            a = q.pop()
            if check:
                check[a] = False
                for k,w in edge[a]:
                    if check[k]:
                        q.append(k)
                        if w % 2:
                            color[k] = color[a] ^ 1
                        else:
                            color[k] = color[a]
    for c in color:
        print(c)
    return

#E
def E():
    n, m = LI()
    xyz = LIR_(m)
    par = [i for i in range(n)]
    size = [1] * n
    def root(a):
        if par[a] == a:
            return a
        par[a] = root(par[a])
        return par[a]

    def union(a, b):
        a = root(a)
        b = root(b)
        if size[a] < size[b]: b, a = a, b
        if a == b:
            return
        par[b] = a
        size[b] += size[a]

    for x, y, _ in xyz:
        union(x, y)
    
    print(len(set(par)))



    return

#F
def F():
    return

#Solve
if __name__ == '__main__':
    E()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n, k = LI()
    s = S()
    s[k-1] = s[k-1].lower()
    print("".join(s))

    return

#B
def B():
    s = S()
    a = int("".join(s[:2]))
    b = int("".join(s[2:]))
    if 0 < a <= 12:
        if 0 < b <= 12:
            print("AMBIGUOUS")
        else:
            print("MMYY")
    elif a == 0:
        if 0 < b <= 12:
            print("YYMM")
        else:
            print("NA")
    else:
        if 0 < b <= 12:
            print("YYMM")
        else:
            print("NA")
    return

#C
def C():
    n, k = LI()
    ans = 0
    if k == 1:
        print(1)
        return
    nibuiti = [None for i in range(int(math.log2(k) + 1))]
    for num in range(int(math.log2(k) + 1)):
        if num == 0:
            nibuiti[num] = 1 / 2
            continue
        nibuiti[num] = nibuiti[num-1]/2
        
    for i in range(1, n + 1):
        if i >= k:
            ans += 1
            continue
        b = nibuiti[int(math.log2((k - 1) // i))]
        ans += b
    print(ans/n)
    return

#D
def D():
    n = II()
    color = [0 for i in range(n)]
    edge = [[] for i in range(n)]
    for i in range(n - 1):
        v, u, w = LI_()
        edge[v].append((u,w+1))
        edge[u].append((v,w+1))
    check = [True for i in range(n)]
    for i in range(n):
        q = deque()
        q.append(i)
        
        while q:
            a = q.pop()
            if check:
                check[a] = False
                for k,w in edge[a]:
                    if check[k]:
                        q.append(k)
                        if w % 2:
                            color[k] = color[a] ^ 1
                        else:
                            color[k] = color[a]
    for c in color:
        print(c)
    return

#E
def E():
    n, m = LI()
    xyz = LIR_(m)
    par = [i for i in range(n)]
    size = [1] * n
    def root(a):
        if par[a] == a:
            return a
        par[a] = root(par[a])
        return par[a]

    def union(a, b):
        a = root(a)
        b = root(b)
        if size[a] < size[b]: b, a = a, b 
        par[b] = a
        size[b] += size[a]

    for x, y, _ in xyz:
        union(x, y)
    
    print(len(set(par)))



    return

#F
def F():
    return

#Solve
if __name__ == '__main__':
    E()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
w = [list(map(int, input().split())) for i in range(m)]
a = [0 for i in range(n)]
magic = 0
for i in range(1,m+1):
    if w[i-1][2] % 2 == 0:
        if a[w[i-1][0]-1] == 0 and a[w[i-1][1]-1] == 0:
            a[w[i-1][0]-1] = 1
            a[w[i-1][1]-1] = 1
            magic += 1
        elif a[w[i-1][0]-1] == 0:
            a[w[i-1][0]-1] = a[w[i-1][1]-1]
        elif a[w[i-1][1]-1] == 0:
            a[w[i-1][1]-1] = a[w[i-1][0]-1]
    else:
        if a[w[i-1][0]-1] == 0 and a[w[i-1][1]-1] == 0:
            a[w[i-1][0]-1] = 1
            a[w[i-1][1]-1] = 2
            magic += 1
        elif a[w[i-1][0]-1] == 0:
            a[w[i-1][0]-1] = a[w[i-1][1]-1] % 2 + 1
        elif a[w[i-1][1]-1] == 0:
            a[w[i-1][1]-1] = a[w[i-1][0]-1] % 2 + 1
for i in range(n):
    if a[i] == 0:
        magic += 1
    else:
        continue
print(magic)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
w = [list(map(int, input().split())) for i in range(m)]
a = [0 for i in range(n)]
if w[0][2] % 2 == 0:
        a[w[0][0]-1] = 1
        a[w[0][1]-1] = 1
else:
        a[w[0][0]-1] = 1
        a[w[0][1]-1] = 2
magic = 1
for i in range(2,m+1):
    if w[i-1][2] % 2 == 0:
        if a[w[i-1][0]-1] == 0 and a[w[i-1][1]-1] == 0:
            a[w[i-1][0]-1] = 1
            a[w[i-1][1]-1] = 1
            magic += 1
        elif a[w[i-1][0]-1] == 0:
            a[w[i-1][0]-1] = a[w[i-1][1]-1]
        elif a[w[i-1][1]-1] == 0:
            a[w[i-1][1]-1] = a[w[i-1][0]-1]
    else:
        if a[w[i-1][0]-1] == 0 and a[w[i-1][1]-1] == 0:
            a[w[i-1][0]-1] = 1
            a[w[i-1][1]-1] = 2
            magic += 1
        elif a[w[i-1][0]-1] == 0:
            a[w[i-1][0]-1] = a[w[i-1][1]-1] % 2 + 1
        elif a[w[i-1][1]-1] == 0:
            a[w[i-1][1]-1] = a[w[i-1][0]-1] % 2 + 1
for i in range(n):
    if a[i] == 0:
        magic += 1
    else:
        continue
print(magic)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
w = [list(map(int, input().split())) for i in range(m)]
print(w)
a = [0 for i in range(n)]
if w[0][2] % 2 == 0:
        a[w[0][0]-1] = 1
        a[w[0][1]-1] = 1
else:
        a[w[0][0]-1] = 1
        a[w[0][1]-1] = 2
magic = 1
for i in range(2,m+1):
    if w[i-1][2] % 2 == 0:
        if a[w[i-1][0]-1] == 0 and a[w[i-1][1]-1] == 0:
            a[w[i-1][0]-1] = 1
            a[w[i-1][1]-1] = 1
            magic += 1
        elif a[w[i-1][0]-1] == 0:
            a[w[i-1][0]-1] = a[w[i-1][1]-1]
        elif a[w[i-1][1]-1] == 0:
            a[w[i-1][1]-1] = a[w[i-1][0]-1]
    else:
        if a[w[i-1][0]-1] == 0 and a[w[i-1][1]-1] == 0:
            a[w[i-1][0]-1] = 1
            a[w[i-1][1]-1] = 2
            magic += 1
        elif a[w[i-1][0]-1] == 0:
            a[w[i-1][0]-1] = a[w[i-1][1]-1] % 2 + 1
        elif a[w[i-1][1]-1] == 0:
            a[w[i-1][1]-1] = a[w[i-1][0]-1] % 2 + 1
for i in range(n):
    if a[i] == 0:
        magic += 1
    else:
        continue
print(magic)

Submission status: Wrong Answer

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード

    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断

    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


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

uf = UnionFind(N)
ans = set(range(1, N+1))

for _ in range(M):
    X, Y, Z = map(int, input().split())
    uf.Unite(X, Y)
    if X != uf.Find_Root(X):
        ans.discard(X)
    if Y != uf.Find_Root(Y):
        ans.discard(Y)

print(len(ans))

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, num):
        self.rank = [0] * num
        self.par = [i for i in range(num)]
        self.n = num
 
    def find_root(self, node):
        if self.par[node] == node:
            return node
        else:
            self.par[node] = self.find_root(self.par[node])
            return self.par[node]
 
    def same_root(self, x, y):
        return self.find_root(x) == self.find_root(y)
 
    def union(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        if self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1


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

UF = UnionFind(N)
for i in range(M) :
    x,y,z = map(int,input().split())
    x -= 1
    y -= 1
    UF.union(x, y)

ans = 0
for i in range(N) :
    if i == UF.par[i] :
        continue
    else :
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, num):
        self.rank = [0] * num
        self.par = [i for i in range(num)]
        self.n = num
 
    def find_root(self, node):
        if self.par[node] == node:
            return node
        else:
            self.par[node] = self.find_root(self.par[node])
            return self.par[node]
 
    def same_root(self, x, y):
        return self.find_root(x) == self.find_root(y)
 
    def union(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        if self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

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

UF = UnionFind(N)
for i in range(M) :
    x,y,z = map(int,input().split())
    x -= 1
    y -= 1
    UF.union(x, y)

ans = len(set(UF.par))
print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, num):
        self.rank = [0] * num
        self.par = [i for i in range(num)]
        self.n = num
 
    def find_root(self, node):
        if self.par[node] == node:
            return node
        else:
            self.par[node] = self.find_root(self.par[node])
            return self.par[node]
 
    def same_root(self, x, y):
        return self.find_root(x) == self.find_root(y)
 
    def union(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        if self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
 

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

UF = UnionFind(N)
for i in range(M) :
    x,y,z = map(int,input().split())
    x -= 1
    y -= 1
    UF.union(x, y)

ans = len(set(UF.par))
print(ans)

Submission status: Wrong Answer

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


def main():
    N, M = map(int, input().split())
    Q = []
    for _ in range(M):
        x, y, z = map(int, input().split())
        Q.append([x, y])
    heapq.heapify(Q)

    called = [False]*(N+1)
    ans = N
    for _ in range(M):
        x, y = heapq.heappop(Q)
        if called[x]==False or called[y]==False:
            ans -= 1
        called[x] = called[y] = True
    
    print(ans)


if __name__ == '__main__':
    main()