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, k = list(map(int, input().split(' ')))

abzs = []
d = {}
exists = {}
for i in range(k):
    a, b, z = list(map(int, input().split(' ')))
    exists[a] = True
    exists[b] = True
    z = z % 2
    a, b = sorted([a, b])
    abzs.append((a, b, z))
    d[(a, b)] = 'o' if z else 'e'
# 島がいくつ別れているか調べる + 存在しないものをカウント
ans = 0
for i in range(1, n+1):
    if i not in exists:
        ans += 1
while d:
    keys = list(d.keys())
    a, b = keys[0]
    for i in range(0, len(keys)):
        x, y = keys[i]
        if a == x or a == y or b == x or b == y:
            d.pop((x, y))
    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()

# Aでxの根を求める
def find(A, x):
    p = A[x]
    if p == x:
        return x
    a = find(A, p)
    A[x] = a
    return a

# Aでxとyの属する集合の併合
def union(A, x, y):
    if find(A, x) > find(A, y):
        bx, by = find(A, y), find(A, x)
    else:
        bx, by = find(A, x), find(A, y)
    # 根をbx(値の小さい方)に統一 
    A[by] = bx

V = [i for i in range(N)]
for i in range(M):
    x, y, z = lr()
    if find(V, x-1) != find(V, y-1):
        union(V, x-1, y-1)

answer = [find(V, x) for x in set(V)]
print(len(answer))
# 36

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()

# Aでxの根を求める
def find(A, x):
    p = A[x]
    if p == x:
        return x
    a = find(A, p)
    A[x] = a
    return a

# Aでxとyの属する集合の併合
def union(A, x, y):
    if find(A, x) > find(A, y):
        bx, by = find(A, y), find(A, x)
    else:
        bx, by = find(A, x), find(A, y)
    # 根をbx(値の小さい方)に統一 
    A[by] = bx

V = [i for i in range(N)]
for i in range(M):
    x, y, z = lr()
    if find(V, x-1) != find(V, y-1):
        union(V, x-1, y-1)

print(len(set(V)))
# 36

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()

# Aでxの根を求める
def find(A, x):
    p = A[x]
    if p == x:
        return x
    a = find(A, p)
    A[x] = a
    return a

# Aでxとyの属する集合の併合
def union(A, x, y):
    if find(A, x) > find(A, y):
        bx, by = find(A, y), find(A, x)
    else:
        bx, by = find(A, x), find(A, y)
    # 根をbx(値の小さい方)に統一 
    A[by] = bx

V = [i for i in range(N)]
for i in range(M):
    x, y, z = lr()
    if find(V, x-1) != find(V, y-1):
        union(V, x-1, y-1)

print(len(set(V)))
# 36

Submission status: Wrong Answer

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

for i in range(M):
  x,y,z = map(int,input().split())
  x-=1
  y-=1
  z%=2
  Aconnect[x].append(i)
  Aconnect[y].append(i)
  XYZ.append([x,y,z])
  
ans=0
for i in range(N):
  if len(Aconnect[i])==0:
    ans+=1
  else:
    flag = 0
    for j in Aconnect[i]:
      if Mflag[j]==1:
        flag=1
      Mflag[j]=1
    if flag==0:
      ans+=1 
      
print(ans)

Submission status: Wrong Answer

Solution code:

def search(x,y):
    global group
    for g in group:
        if (x in g) and (y not in g):
            g.append(y)
            return
        elif (x not in g) and (y in g):
            g.append(x)
            return
        elif (x in g) and (y in g):
            return
    group.append([x,y])
    return

if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    LIST=[list(map(int,input().split())) for i in range(M)]
    group=[]
    for l in LIST:
        x,y=l[0],l[1]
        search(x,y)

    temp=len(group)
    temp_set=set(range(1,N+1))
    for g in group:
        temp_set-=set(g)
    print(temp+len(temp_set))

Submission status: Wrong Answer

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
#import numpy as np

def main():
	n,m=map(int,input().split())
	A=[0]*(n+1)
	ans=n
	
	for i in range(m):
		x,y,z=map(int,input().split())
		if A[x]==0 or A[y]==0:
			ans-=1
		A[x]+=1;A[y]+=1
	
	print(ans)
	
	
	
	
	


	
if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from operator import itemgetter


def solve():
    N, M = map(int, input().split())
    xy_dict = defaultdict(int)
    xy = [[] for _ in range(N)]
    for _ in range(M):
        x, y, z = map(lambda j: int(j)-1, input().split())
        xy_dict[x] += 1
        xy_dict[y] += 1
        xy[x].append(y)
        xy[y].append(x)
    
    xy_sorted = sorted(xy_dict.items(), key=itemgetter(1), reverse=True)
    opened = [0 for _ in range(N)]
    ans = N
    length = len(xy_sorted)
    for i in range(length):
        parent = xy_sorted[i][0]
        if opened[parent] == 1:
            for child in xy[parent]:
                if opened[child] == 0:
                    opened[child] = 1
                    ans -= 1
            continue
        opened[parent] = 1
        for child in xy[parent]:
            opened[child] = 1
        ans -= xy_dict[parent]
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

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

par = [i for i in range(n+1)]
rank = [0 for i in range(n+1)]

def find(x):
    if x==par[x]:
        return x
    else:
        par[x]=find(par[x])
        return par[x]

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

def some(x,y):
    return find(x)==find(y)

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

for i in range(n):
    find(i)
    
ans=len(set(par))-1

print(ans)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,m = LI()
def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]

def same(x,y):
    return root(x) == root(y)

def union(x,y):
    x = root(x)
    y = root(y)

    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

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

xyz = [LI() for _ in range(m)]
for x,y,z in xyz:
    if root(x-1) != root(y-1):
        union(x-1,y-1)
ans = len(list(Counter(par).items()))
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
ans = 0
G = [[] for i in range(N+1)]
for i in range(M):
    x,y,z = map(int,input().split())
    G[x].append(y)
S = [i for i in range(1,N+1)]
T = []
R = []
while len(S) != 0:
    ans += 1
    x = S.pop(0)
    T.append(x)
    while len(T) != 0:
        y = T.pop()
        R.append(y)
        for i in G[y]:
            if i not in T:
                if i not in R:
                    S.remove(i)
                    T.append(i)
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
ans = 0
G = [[] for i in range(N+1)]
for i in range(M):
    x,y,z = map(int,input().split())
    G[x].append(y)
S = [i for i in range(1,N+1)]
T = []
R = []
while len(S) != 0:
    ans += 1
    x = S.pop(0)
    T.append(x)
    while len(T) != 0:
        y = T.pop()
        R.append(y)
        for i in G[y]:
            if i not in T:
                if i not in R:
                    S.remove(i)
                    T.append(i)
print(ans)

Submission status: Wrong Answer

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

tree=[[] for _ in range(n)]
for i in range(m):
    x,y,w = map(int,input().split())
    tree[x-1].append(y-1)
    tree[y-1].append(x-1)

singles = [ i for i in range(n) if tree[i]==[]]

visited=[False]*n
for i in singles:
    visited[i] = True
ans=len(singles)

from collections import deque
while False in visited:
    ans+=1
    restart = visited.index(False)
    visited[restart]=True
    q = deque( [(restart,tree[restart][0])] )
    while q:
        parent,x = q.pop()
        visited[x]=True
        for y in tree[x]:
            if visited[y]:
                continue
            q.append((x,y))
print(ans)

Submission status: Wrong Answer

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

tree=[[] for _ in range(n)]
for i in range(m):
    x,y,w = map(int,input().split())
    tree[x-1].append(y-1)
    tree[y-1].append(x-1)

singles = [ i for i in range(n) if tree[i]==[]]
tree_dict=dict()
for i in range(n):
    if tree[i]!=[]:
        tree_dict[i]=tree[i]

visited=[False]*n
for i in singles:
    visited[i] = True
ans=len(singles)

while False in visited:
    ans+=1
    restart = visited.index(False)
    visited[restart]=True
    q = [(restart,tree_dict[restart][0])]
    while q:
        parent,x = q.pop()
        visited[x]=True
        for y in tree_dict[x]:
            if visited[y]:
                continue
            q.append((x,y))
print(ans)

Submission status: Wrong Answer

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

tree=[[] for _ in range(n)]
for i in range(m):
    x,y,w = map(int,input().split())
    tree[x-1].append(y-1)
    tree[y-1].append(x-1)

singles = [ i for i in range(n) if tree[i]==[]]

visited=[False]*n
for i in singles:
    visited[i] = True
ans=len(singles)

while False in visited:
    ans+=1
    restart = visited.index(False)
    visited[restart]=True
    if tree[restart]==[]:
        continue
    q = [(restart,tree[restart][0])]
    while q:
        parent,x = q.pop()
        visited[x]=True
        for y in tree[x]:
            if visited[y]:
                continue
            q.append((x,y))
print(ans)

Submission status: Wrong Answer

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

tree=[[] for _ in range(n)]
for i in range(m):
    x,y,w = map(int,input().split())
    tree[x-1].append(y-1)
    tree[y-1].append(x-1)
    
ans=0
visited=[False]*n
while False in visited:
    ans+=1
    restart = visited.index(False)
    visited[restart]=True
    if tree[restart]==[]:
        continue
    q = [(restart,tree[restart][0])]
    while q:
        parent,x = q.pop()
        visited[x]=True
        for y in tree[x]:
            if visited[y]:
                continue
            q.append((x,y))
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

N,M=map(int,input().split())
#親のノードを格納　2の親が4のとき par[2]=4
par=[0]
#木の深さを格納　根が2の深さが3の時 rank[2]=3
rank=[0]
 
#初期化
for i in range(1,N+1):
    par.append(i)
    rank.append(0)
 
#xの根を探す、同時に通過したノードすべてを根に直接つける
def find(x):
    #xの親がxならば根なのでxを返す
    if par[x]==x:
        return x
    else:
        #違う場合は親の親を捜し自分の親にする
        par[x] = find(par[x])
        #再帰的に行うと根が見つかる
        return par[x]
 
#xが属する木とyが属する木を併合する
def unite(x,y):
    #根を探す
    root_x=find(x)
    root_y=find(y)
    
    #根が同じなら元からつながっているので終わり
    if root_x == root_y:
        return
    
    #ランクが大きい木の根の直下にランクが小さい木を結合
    if rank[root_x] < rank[root_y]:
        par[root_x] = root_y
    
    else:
        par[root_y] = root_x
    
    #ランクが等しいときのみランクが増える
    if rank[root_x]==rank[root_y]:
        rank[root_x]+=1
    
#xとyが同じ木に存在するかを調べる
def same(x,y):
    return find(x)==find(y)
    
#main
for i in range(M):
    a,b,z=map(int,input().split())
    unite(a,b)
l=[]
for i in range(1,N+1):
    if par[i] in l:
        continue
    else:
        l.append(par[i])
print(len(l))

Submission status: Wrong Answer

Solution code:
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:
            self.root[x] = self.find(self.root[x])
            return self.root[x]

    def isSame(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.root[x] = y
        else:
            self.root[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


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

n_tree = set(uf.root)
ans = len(n_tree) - 1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n, m = map(int, input().split())
card = np.ones(n, dtype=int) * (-1)

ans = 0
xyz = []
for _ in range(m):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    if x > y:
        x, y = y, x
    z %= 2
    xyz.append((x, y, z))

for i, j in enumerate(xyz):
    x, y, z = j
    if card[x] == -1 and card[y] == -1:
        ans += 1
        card[x] = 1
        card[y] = 1 ^ z
    elif card[x] == -1:
        card[x] = card[y] ^ z
    elif card[y] == -1:
        card[y] = card[x] ^ z
    else:
        continue

ans += sum(card == -1)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n, m = map(int, input().split())
card = np.ones(n, dtype=int) * (-1)

ans = 0

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

    if card[x] == -1 and card[y] == -1:
        card[x] = 1
        ans += 1
        if z == 0:
            card[y] = 1
        else:
            card[y] = 0

    elif card[x] != -1 and card[y] == -1:
        card[y] = card[x] ^ z

    elif card[y] != -1 and card[x] == -1:
        card[x] = card[y] ^ z

ans += sum(card == -1)
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
N, M = map(int, input().split())
XYZ = [list(map(int, input().split())) for i in range(M)]
table = collections.defaultdict(int)
for x, y, z in XYZ:
    table[x-1] += 1
    table[y-1] += 1
XYZ.sort(key=lambda x: max(table[x[0]-1], table[y-1]), reverse=True)
A = [False]*N
ans = 0
for x, y, z in XYZ:
    if A[x-1] and A[y-1]:
        continue
    elif A[x-1] or A[y-1]:
        A[x-1] = True
        A[y-1] = True
    else:
        ans += 1
        A[x-1] = True
        A[y-1] = True

for i in range(N):
    if A[i] == False:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import collections
N, M = map(int, input().split())
XYZ = [list(map(int, input().split())) for i in range(M)]
table = collections.defaultdict(int)
for x, y, z in XYZ:
    table[x-1] += 1
    table[y-1] += 1
XYZ.sort(key=lambda x: table[x[0]-1], reverse=True)
A = [False]*N
ans = 0
for x, y, z in XYZ:
    if A[x-1] and A[y-1]:
        continue
    elif A[x-1] or A[y-1]:
        A[x-1] = True
        A[y-1] = True
    else:
        if z % 2 == 1:
            ans += 1
        else:
            ans += 2
        A[x-1] = True
        A[y-1] = True

for i in range(N):
    if A[i] == False:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import collections
N, M = map(int, input().split())
XYZ = [list(map(int, input().split())) for i in range(M)]
table = collections.defaultdict(int)
for x, y, z in XYZ:
    table[x-1] += 1
    table[y-1] += 1
XYZ.sort(key=lambda x: table[x[0]-1], reverse=True)
A = [False]*N
ans = 0
for x, y, z in XYZ:
    if A[x-1] and A[y-1]:
        continue
    elif A[x-1] or A[y-1]:
        A[x-1] = True
        A[y-1] = True
    else:
        ans += 1
        A[x-1] = True
        A[y-1] = True

for i in range(N):
    if A[i] == False:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
# どうせ矛盾しないんだしz要らないのでは
# クエリで登場しない数 + クエリで登場した中で完結するグループの数
# なんとなくunionfindでxとyだけみてやって最後に親をuniqする感じ
n, m = map(int, input().split())
par = [i for i in range(n)]


def root(x):
    if x == par[x]:
        return x
    xx = root(par[x])
    par[x] = xx
    return xx


def union(x, y):
    rx, ry = root(x), root(y)
    if rx != ry:
        par[ry] = rx


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

print(len(set(par)))

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

def search(x, y):
    while root[x] != x: x = root[x]
    while root[y] != y: y = root[y]
    return x, y

def rebuild(x, y, r):
    while root[x] != r: x, root[x] = root[x], r
    while root[y] != r: y, root[y] = root[y], r
        
N, M = map(int, input().split())

root = {i:i for i in range(1, N+1)}
size = {i:1 for i in range(1, N+1)}

for i in range(M):
    x, y, z = map(int, input().split())
    
    x_r, y_r = search(x, y)

    if x_r == y_r: continue
    if x_r > y_r: x_r, y_r = y_r, x_r
    
    root[y_r] = x_r
    size[x_r] += size[y_r]
    if size[x_r] < 10: rebuild(x, y, x_r)
        
print(len(set(root.values())))

Submission status: Wrong Answer

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

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.size())

Submission status: Wrong Answer

Solution code:
class UnionFind:
  
  def __init__(self, n):
    self.par = [i for i in range(n)]
    self.rank = [0]*n
  
  def find(self, x):
    if self.par[x]==x:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]
  
  def unite(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x==y:
      return
    if self.rank[x]<self.rank[y]:
      self.par[x] = y
    else:
      self.par[y] = x
      if self.rank[x]==self.rank[y]:
        self.rank[x] += 1
  
  def same(self, x, y):
    return self.find(x)==self.find(y)
  
  def size(self):
    ans = [0]*N
    for i in range(N):
      j = self.par[i]
      ans[j] |= 1
    return sum(ans)

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.size())

Submission status: Wrong Answer

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

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

par = set(union.par)
print(len(par))

Submission status: Wrong Answer

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

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

par = set(union.par)
print(len(par))

Submission status: Wrong Answer

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

XYZ.sort(key=lambda x: (x[0], x[1]))

p = 1
nums = [-1] * N 
for x, y, z in XYZ:
  if nums[x - 1] == -1 and nums[y - 1] == -1:
    nums[x - 1] = p
    nums[y - 1] = p
    p += 1
  elif nums[x - 1] == -1:
    nums[x - 1] = nums[y - 1]
  elif nums[y - 1] == -1:
    nums[y - 1] = nums[x - 1]

ans = nums.count(-1) + (p - 1)

print(ans)

Submission status: Wrong Answer

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

p = 1
nums = [-1] * N 
for _ in range(M):
  x, y, z = map(int, input().split())
  if nums[x - 1] == -1 and nums[y - 1] == -1:
    nums[x - 1] = p
    nums[y - 1] = p
    p += 1
  elif nums[x - 1] == -1:
    nums[x - 1] = nums[y - 1]
  elif nums[y - 1] == -1:
    nums[y - 1] = nums[x - 1]

ans = nums.count(-1) + (p - 1)

print(ans)

Submission status: Wrong Answer

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

nums = list(set())
apper = set()
for _ in range(M):
  x, y, z = map(int, input().split())
  apper.add(x)
  apper.add(y)
  for i, s in enumerate(nums):
#    print(s)
    if x in s or y in s:
      nums[i].add(x)
      nums[i].add(y)
      break
  else:
    nums.append(set([x, y]))
ans = N - len(apper) + len(nums)
# print(N, len(apper), len(nums))
# print(nums)
print(ans)

Submission status: Wrong Answer

Solution code:
#17:11
n,m = map(int,input().split())
pre = [-1 for i in range(n)]
for _ in range(m):
  x,y,z = map(int,input().split())
  x -= 1
  y -= 1
  X = [x]
  Y = []
  while pre[x] != -1:
    X.append(x)
    x = pre[x]
  while pre[y] != -1:
    Y.append(y)
    y = pre[y]
  if x != y:
    for xx in X:
      pre[xx] = y
    for yy in Y:
      pre[yy] = y
father = set()
ans = 0
for i in range(n):
  if pre[i] == -1:
    ans += 1
#print(pre)
print(ans)

Submission status: Wrong Answer

Solution code:
#17:11
n,m = map(int,input().split())
pre = [-1 for i in range(n)]
for _ in range(m):
  x,y,z = map(int,input().split())
  x -= 1
  y -= 1
  X = []
  Y = []
  while pre[x] != -1:
    X.append(x)
    x = pre[x]
  while pre[y] != -1:
    Y.append(Y)
    y = pre[y]
  if x != y:
    if len(X) > len(Y):
      for xx in X:
        pre[xx] = y
      for yy in Y:
        pre[yy] = y
    else:
      for xx in X:
        pre[xx] = x
      for yy in Y:
        pre[yy] = x
father = set()
ans = 0
for i in range(n):
  if pre[i] == -1:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
already = set()
cnt = 0
ls = []
parent = [i for i in range(n)]

def unite(a, b):
    if not is_same(a, b):
        parent[find_root(b)] = find_root(a)

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

def is_same(a, b):
    return find_root(a) == find_root(b)

for i in range(m):
    x, y, z = [int(i) for i in sys.stdin.readline().split()]
    x -= 1
    y -= 1
    unite(x, y)

print(len(set(parent)))

Submission status: Wrong Answer

Solution code:
import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
already = set()
cnt = 0
for i in range(m):
    x, y, z = [int(i) for i in sys.stdin.readline().split()]
    if x not in already and y not in already:
        cnt += 1
    already.update({x, y})
print(cnt + n - len(already))

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


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

    def get_root(self, x):
        if self.parents[x] == x:
            return x
        self.parents[x] = self.get_root(self.parents[x])
        return self.parents[x]

    def merge(self, x, y):
        x = self.get_root(x)
        y = self.get_root(y)
        if x != y:
            if self.ranks[x] < self.ranks[y]:
                self.parents[x] = y
            else:
                self.parents[y] = x
                if self.ranks[x] == self.ranks[y]:
                    self.ranks[x] += 1


n, m = ril()
uf = UnionFind(n)
for _ in range(m):
    x, y, z = ril()
    uf.merge(x - 1, y - 1)
print(len(set(uf.parents)))

Submission status: Wrong Answer

Solution code:
class union_find():
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [1 for i in range(n + 1)]

    def find(self, c):
        if self.par[c] == c:
            return c

        ret = self.find(self.par[c])
        self.par[c] = ret
        return ret

    def union(self, x, y):
        xr = self.find(x)
        yr = self.find(y)
        if xr == yr:
            return

        if self.rank[yr] > self.rank[xr]:
            self.par[xr] = yr
        else:
            self.par[yr] = xr
            if self.rank[xr] == self.rank[yr]:
                self.rank[xr] += 1

    def show(self):
        print('parent', self.par[1:])
        print('rank', self.rank[1:])

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

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


print([i == v for i, v in enumerate(uf.par[1:])].count(True))

Submission status: Wrong Answer

Solution code:
class union_find():
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [1 for i in range(n + 1)]

    def find(self, c):
        if self.par[c] == c:
            return c

        ret = self.find(self.par[c])
        self.par[c] = ret
        return ret

    def union(self, x, y):
        xr = self.find(x)
        yr = self.find(y)
        if xr == yr:
            return

        if self.rank[yr] > self.rank[xr]:
            self.par[xr] = yr
        else:
            self.par[yr] = xr
            if self.rank[xr] == self.rank[yr]:
                self.rank[xr] += 1

    def show(self):
        print('parent', self.par[1:])
        print('rank', self.rank[1:])

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

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


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

Submission status: Wrong Answer

Solution code:
class union_find():
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [1 for i in range(n + 1)]

    def find(self, c):
        if self.par[c] == c:
            return c

        ret = self.find(self.par[c])
        self.par[c] = ret
        return ret

    def union(self, x, y):
        xr = self.find(x)
        yr = self.find(y)
        if xr == yr:
            return

        if self.rank[yr] > self.rank[xr]:
            self.par[x] = yr
        else:
            self.par[y] = xr
            if self.rank[xr] == self.rank[yr]:
                self.rank[xr] += 1

    def show(self):
        print('parent', self.par[1:])
        print('rank', self.rank[1:])

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

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


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

Submission status: Wrong Answer

Solution code:
#1 or 2
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())
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:
import sys
sys.setrecursionlimit(10**6)

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

global clasta
clasta = [-1 for i in range(n)]
path = [[] for i in range(n)]
used = [0 for i in range(n)]
for _ in range(m):
    x,y,z = map(int,input().split())
    path[x-1].append(y-1)
    path[y-1].append(x-1)

def dfs(now,color):
    for y in path[now]:
        if clasta[y] == -1:
            clasta[y] = color
            dfs(y,color)
            
ans = 0
for idx,i in enumerate(clasta[::-1]):
    if i == -1:
        clasta[idx] = idx
        dfs(idx,idx)
        ans += 1

print(ans)

Submission status: Wrong Answer

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

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

global clasta
clasta = [-1 for i in range(n)]
path = [[] for i in range(n)]
for _ in range(m):
    x,y,z = map(int,input().split())
    path[x-1].append(y-1)

def dfs(now,color):
    for y in path[now]:
        if clasta[y] == -1:
            clasta[y] = color
            dfs(y,color)

for idx,i in enumerate(clasta):
    if i == -1:
        clasta[idx] = idx
        dfs(idx,idx)

print(len(set(clasta)))

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