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 collections

class UnionFind:
    def __init__(self, n):
        self.par = [k for k 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]:
                #もし二つの木の高さが同じ状態で片方をもう片方に結合すると
                #結合後の木全体の高さは元々より1高くなる
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    def tree_count(self):
        l = collections.Counter(self.par[1:])
        return len(l)


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

uf = UnionFind(n)

#print(uf.par)
for i in range(m):
    x,y,z = map(int,input().split())
    uf.union(x,y)
    #print(uf.par)

print(uf.tree_count())

Submission status: Wrong Answer

Solution code:
class UnionFind(object):
    def __init__(self, nodes):
        self.__parents = {node: None for node in nodes}

    def union(self, a, b):
        root_of_a = self.find(a)
        self.__parents[a] = b

    def find(self, a):
        if self.__parents[a] is None:
            return a
        root = self.find(self.__parents[a])
        self.__parents[a] = root
        return root

    @property
    def roots(self):
        return set(node for node, parent in self.__parents.items() if parent is None)

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

xyzs = [tuple(map(int, input().split())) for _ in range(m)]

union_find = UnionFind(range(1, n+1))
for x, y, z in xyzs:
    union_find.union(x, y)

print(len(union_find.roots))

Submission status: Wrong Answer

Solution code:
N, M = (int(x) for x in input().split())

xyz = [list(map(int, input().split())) for _ in range(M)]

# 魔法実行回数
magic_act_num = 0

known = [False for x in range(N)]
judge = 0

for x, y, _ in xyz:
    x = x - 1
    y = y - 1
    if known[x] and known[y]:
        continue;

    # zは気にしなくてよい
    if known[x]:
        if known[y] is False:
            known[y] = True
            judge += 1
    else:
        if known[y]:
            known[x] = True
            judge += 1
        else:
            known[x] = True
            known[y] = True
            judge += 2
            magic_act_num += 1

magic_act_num += (N-judge)

print(magic_act_num)

Submission status: Wrong Answer

Solution code:
N, M = (int(x) for x in input().split())

xyz = [list(map(int, input().split())) for _ in range(M)]

# 魔法実行回数
magic_act_num = 0

known = [False for x in range(N)]
judge = 0

for x, y, _ in xyz:
    x = x-1
    y = y-1
    if known[x] and known[y]:
        continue;

    # zは気にしなくてよい
    if known[x]:
        if known[y] is False:
            known[y] = True
            judge += 1
    else:
        if known[y]:
            known[x] = True
            judge += 1
        else:
            known[x] = True
            known[y] = True
            judge += 2
            magic_act_num += 1

    del xyz[0]

    for a, b, _ in xyz:
        a = a - 1
        b = b - 1
        if known[a] is x and known[b] is y:
            continue
        if known[a] is y and known[b] is x:
            continue
        if known[a] is x:
            if known[b] is not y:
                known[b] = True
        if known[a] is y:
            if known[b] is not x:
                known[b] = True
        if known[b] is x:
            if known[a] is not y:
                known[a] = True
        if known[b] is y:
            if known[a] is not x:
                known[a] = True

magic_act_num += (N-judge)

print(magic_act_num)

Submission status: Wrong Answer

Solution code:
N, M = (int(x) for x in input().split())

xyz = [list(map(int, input().split())) for _ in range(M)]

# 魔法実行回数
magic_act_num = 0

known = [False for x in range(N)]
judge = 0

for x, y, _ in xyz:
    x = x-1
    y = y-1
    if known[x] and known[y]:
        continue;

    # zは気にしなくてよい
    if known[x]:
        if known[y] is False:
            known[y] = True
            judge += 1
    else:
        if known[y]:
            known[x] = True
            judge += 1
        else:
            known[x] = True
            known[y] = True
            judge += 2
            magic_act_num += 1
    del xyz[0]
    for a, b, _ in xyz:
        a = a - 1
        b = b - 1
        if known[a] is x and known[b] is y:
            continue
        if known[a] is y and known[b] is x:
            continue
        if known[a] is x:
            if known[b] is not y:
                known[b] = True
        if known[a] is y:
            if known[b] is not x:
                known[b] = True
        if known[b] is x:
            if known[a] is not y:
                known[a] = True
        if known[b] is y:
            if known[a] is not x:
                known[a] = True

magic_act_num += (N-judge)

print(magic_act_num)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
E - 1 or 2
https://atcoder.jp/contests/abc126/tasks/abc126_e

"""
import sys


class DisjointSet(object):
    def __init__(self, n):
        self.rank = [0] * n
        self.p = list(range(n))
        self.size = [1] * n

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

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if self.rank[x] > self.rank[y]:
            self.size[self.p[x]] += self.size[self.p[y]]
            self.p[y] = self.findSet(x)
        else:
            self.size[self.p[y]] += self.size[self.p[x]]
            self.p[x] = self.findSet(y)
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def findSet(self, x):
        if x != self.p[x]:
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]


def solve(N, M, hints):
    d = DisjointSet(N+1)
    for x, y, z in hints:
        d.link(x, y)
    ans = set(d.p)
    ans.discard(d.p[0])
    return len(ans)


def main(args):
    N, M = map(int, input().split())
    hints = [[int(i) for i in input().split()] for _ in range(M)]
    ans = solve(N, M, hints)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
ls=[]
for i in range(M):
    X,Y,Z=map(int,input().split())
    set1={X,Y}
    ls.append(set1)
ls=sorted(ls,key=lambda x:len(x))
set2=set()
cost=0
for set3 in ls:
    if len(set3)==1:
        set2=set2|set3
    else:
        if len(set2&set3)==0:
            cost+=1
            set2=set2|set3
        else:
            set2=set2|set3
if len(set2)==N:
    print(cost)
else:
    print(N-len(set2)+cost)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
ls=[]
for i in range(M):
    ls.append(set(map(int,input().split())))
ls=sorted(ls,key=lambda x:len(x))
set1=set()
cost=0
for set2 in ls:
    if len(set2)==1:
        set1=set1|set2
    if len(set2)==2:
        set3=set1&set2
        if len(set3)==0:
            cost+=1
            set1=set1|set2
        if len(set3)==1:
            set1=set1|set2
        if len(set3)==2:
            continue
    if len(set2)==3:
        set3=set1&set2
        if len(set3)==0:
            cost+=2
            set1=set1|set2
        if len(set3)==1:
            cost+=1
            set1=set1|set2
        if len(set3)==2:
            set1=set1|set2
        if len(set3)==3:
            continue
if len(set1)==N:
    print(cost)
else:
    print(N-len(set1)+cost)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=[list(map(int,input().split()))for i in range(m)]
b=[i for i in range(n+1)]
c=[1]*(n+1)
def root(x):
    if b[x]==x:
        return x
    x=b[x]
    return root(x)
def unite(x,y):
    p=root(x)
    q=root(y)
    if p!=q:
        if c[x]>c[y]:
            b[y]=x
            c[x]+=1
        else:
            b[x]=y
            c[y]+=1
for i,j,t in a:
    unite(i,j)
for i in range(n+1):
    b[i]=root(i)
print(len(set(b[1:])))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=[list(map(int,input().split()))for i in range(m)]
b=[i for i in range(n+1)]
c=[1]*(n+1)
def root(x):
    if b[x]==x:
        return x
    x=b[x]
    return root(x)
def unite(x,y):
    p=root(x)
    q=root(y)
    if p!=q:
        if c[x]>c[y]:
            b[y]=x
            c[x]+=1
        else:
            b[x]=y
            c[y]+=1
for i,j,t in a:
    unite(i,j)
for i in range(n+1):
    b[i]=root(b[i])
print(len(set(b[1:])))

Submission status: Wrong Answer

Solution code:
# Union Find Tree
class UnionFindTree():
    def __init__(self, N):
        self.parent = [-1]*(N+1)
        self.rank = [1]*(N+1)
        self.size = [1]*(N+1)
        self.count = 0

    def find(self, i):
        if self.parent[i] == -1:
            group = i
        else:
            group = self.find(self.parent[i])
            self.parent[i] = group
        return group

    def unite(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.rank[px] == self.rank[py]:  # rank is same
                self.rank[px] += 1
            elif self.rank[px] < self.rank[py]:
                px, py = py, px

            self.parent[py] = px
            self.size[px] += self.size[py]
        self.count += 1

    def getsize(self, x):
        return self.size[self.find(x)]

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


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

UFT = UnionFindTree(N)
for x, y, z in A:
    x -= 1
    y -= 1
    UFT.unite(x, y)
print(N - UFT.count)

Submission status: Wrong Answer

Solution code:
from collections import Counter

N,M = map(int,input().split(" "))
par = list(range(N))
for i in range(M):
    x,y,z = map(int,input().split(" "))
    par[y-1] = x-1

for i in range(N):
    if par[i] != i:
        par[i] = par[par[i]]

print(len(Counter(par)))

Submission status: Wrong Answer

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

checked = []
cost = 0
for _ in range(M):
    x,y,z = map(int, input().split())

    if x in checked:
        if not y in checked:
            checked.append(y)
        continue
    if y in checked:
        if not x in checked:
            checked.append(x)
        continue
    cost += 1
    checked.append(x)
    checked.append(y)

print(N - len(set(checked)) + cost)

Submission status: Wrong Answer

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

checked = []
cost = 0
for _ in range(M):
    x,y,z = map(int, input().split())

    if x in checked:
        if not y in checked:
            checked.append(y)
        continue
    if y in checked:
        if not x in checked:
            checked.append(x)
        continue
    cost += 1
    checked.append(x)
    checked.append(y)

print(N - len(checked) + cost)

Submission status: Wrong Answer

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

xyz = []
for _ in range(M):
    x,y,z = map(int, input().split())
    xyz.append((x,y,z))

nodes = []
def check_relation(a, b):
    for nn in nodes:
        if a in nn:
            nn.append(b)
            return
        if b in nn:
            nn.append(a)
            return
    nodes.append([a,b])

for x,y,z in xyz:
    check_relation(x,y)

result = N
for n in nodes:
    result -= len(set(n))-1
print(result)

Submission status: Wrong Answer

Solution code:
class UnionFind:
	def __init__(self, n):
		self.par = [i for i in range(n)]  # 親
		self.rank = [1] * n  # 深さ
		self.size = [1] * n  # size[i]はiを根とするグループのサイズ

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

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			if self.rank[x] < self.rank[y]:
				self.par[x] = y
				self.size[y] += self.size[x]
			else:
				self.par[y] = x
				self.size[x] += self.size[y]
				if self.rank[x] == self.rank[y]:
					self.rank[x] += 1

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

	def group_size(self, x):
		return self.size[self.find(x)]

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

uf = UnionFind(N)

for j in range(M):
	uf.unite(X[j] - 1, Y[j] - 1)

ans = 0
root = []
for k in range(M):
	tmp = uf.find(X[k])
	if tmp not in root:
		ans += 1
		root.append(tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind:
	def __init__(self, n):
		self.par = [i for i in range(n)]  # 親
		self.rank = [1] * n  # 深さ
		self.size = [1] * n  # size[i]はiを根とするグループのサイズ

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

	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			if self.rank[x] < self.rank[y]:
				self.par[x] = y
				self.size[y] += self.size[x]
			else:
				self.par[y] = x
				self.size[x] += self.size[y]
				if self.rank[x] == self.rank[y]:
					self.rank[x] += 1

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

	def group_size(self, x):
		return self.size[self.find(x)]

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

uf = UnionFind(N)

for j in range(M):
	uf.unite(X[j] - 1, Y[j] - 1)

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

Submission status: Wrong Answer

Solution code:
n,m=[int(_) for _ in input().split()]
l=[set() for _ in range(n)]
for iii in range(m):
  x,y,z=[int(_) for _ in input().split()]
  x-=1
  y-=1
  l[x].add(y)
  l[y].add(x)
out=0
ls=[set()]
for iii in range(n):
  ds=l[iii]
  if ds==set():
    out+=1
    continue
  else:
    inflag=0
    for jjj in range(len(ls)):
      if iii in ls[jjj]:
        ls[jjj]=ls[jjj].union(ds)
        inflag=1
    if inflag==0:
      ds.add(iii)
      ls.append(ds)
print(len(ls)+out-1)

Submission status: Wrong Answer

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

a.sort(key=lambda x:x[0])

b = [i+1 for i in range(n)]

for i in range(m):
    b[a[i][1]-1] = b[a[i][0]-1]

print(len(set(b)))

Submission status: Wrong Answer

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

outgoing=dict()
incoming=dict()
for i in range(M):
  x,y,z=map(int, input().split())
  if x in outgoing: outgoing[x].add(y)
  else: outgoing[x]={y}
  if y in incoming: incoming[y].add(x)
  else: incoming[y]={x}
#print(outgoing)
#print(incoming)
V=set()
def dfs(v):
  if v not in V:
    V.add(v)
    """
    if v in outgoing:
      for u in outgoing[v]: dfs(u)
    """
    if v in incoming:
      for u in incoming[v]: dfs(u)
cnt=0
for i in range(1, N+1):
  if i not in V:
    cnt += 1
    dfs(i)
print(cnt)

Submission status: Wrong Answer

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

outgoing=dict()
incoming=dict()
for i in range(M):
  x,y,z=map(int, input().split())
  if x in outgoing: outgoing[x].add(y)
  else: outgoing[x]={y}
  if y in incoming: incoming[y].add(x)
  else: incoming[y]={x}
#print(outgoing)
#print(incoming)
V=set()
def dfs(v):
  if v not in V:
    V.add(v)
    if v in outgoing:
      for u in outgoing[v]: dfs(u)
    """
    if v in incoming:
      for u in incoming[v]: dfs(u)
    """
cnt=0
for i in range(1, N+1):
  if i not in V:
    cnt += 1
    dfs(i)
print(cnt)

Submission status: Wrong Answer

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

outgoing=dict()
incoming=dict()
for i in range(M):
  x,y,z=map(int, input().split())
  if x in outgoing: outgoing[x].add(y)
  else: outgoing[x]={y}
  if y in incoming: incoming[y].add(x)
  else: incoming[y]={x}
#print(outgoing)
#print(incoming)
V=set()
def dfs(v):
  if v not in V:
    V.add(v)
    """
    if v in outgoing:
      for u in outgoing[v]: dfs(u)
    if v in incoming:
      for u in incoming[v]: dfs(u)
    """
cnt=0
for i in range(1, N+1):
  if i not in V:
    cnt += 1
    dfs(i)
print(cnt)

Submission status: Wrong Answer

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

outgoing=dict()
incoming=dict()
for i in range(M):
  x,y,z=map(int, input().split())
  if x in outgoing: outgoing[x].add(y)
  else: outgoing[x]={y}
  if y in incoming: incoming[y].add(x)
  else: incoming[y]={x}
#print(outgoing)
#print(incoming)
"""
V=set()
def dfs(v):
  if v not in V:
    V.add(v)
    if v in outgoing:
      for u in outgoing[v]: dfs(u)
    if v in incoming:
      for u in incoming[v]: dfs(u)

cnt=0
for i in range(1, N+1):
  if i not in V:
    cnt += 1
    dfs(i)
print(cnt)
"""

Submission status: Wrong Answer

Solution code:
import numpy as np

N, M = map(int, input().split() )
node = np.arange(N)
conn = np.arange(N)
for i in range(M):
    X, Y ,Z = map(int, input().split())
    conn[Y-1] = conn[X-1]
land = np.unique(conn)
print(land.shape[0])

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
x, y, z = [], [], []
for i in range(m):
    xv, yv, zv = map(int, input().split())
    x.append(xv)
    y.append(yv)
    z.append(zv)

ary = [1 for i in range(n)]

for i in range(m):
    if ary[y[i]-1] == 1:
        ary[y[i]-1] = 0

print(sum(ary))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
x, y, z = [], [], []
for i in range(m):
    xv, yv, zv = map(int, input().split())
    x.append(xv)
    y.append(yv)
    z.append(zv)

ary = [1 for i in range(n)]

dec = 0
for i in range(m):
    if ary[x[i]-1] == 1 or ary[y[i]-1] == 1:
        dec += 1
    ary[x[i]-1] = 0
    ary[y[i]-1] = 0

print(n-dec)

Submission status: Wrong Answer

Solution code:
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, M = map(int,input().split())
q = []
c = [0] * N
A = [[] for i in range(N)]

for i in range(M):
	x, y, z = map(int,input().split())
	x = x - 1
	y = y - 1
	#A[x].append(y)
	A[y].append(x)

cost = 0
for i in range(N):
	if c[i] == 0:
		cost = cost + 1
		q.append(i)
		while len(q):
			j = q.pop(0)
			c[j] = 1
			for k in A[j]:
				if c[k] == 0:
					q.append(k)

print(cost)

Submission status: Wrong Answer

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

li=list(range(1,n+1))

for i in range(m):
    x, y, z=map(int, input().split())
    if z%2==0:
        li[max(x,y)-1]=li[min(x,y)-1]
    else:
        li[max(x,y)-1]=-li[min(x,y)-1]

for i in range(n):
    if li[i]<0:
        li[i]*=-1

li2=[0]*(n+1)

for i in range(n):
    li2[li[i]]=1

print(sum(li2))

Submission status: Wrong Answer

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

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

    def union(self, x, y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if self.rank[xRoot] > self.rank[yRoot]:
            self.parent[yRoot] = xRoot
        elif self.rank[xRoot] < self.rank[yRoot]:
            self.parent[xRoot] = yRoot
        elif xRoot != yRoot:
            self.parent[yRoot] = xRoot
            self.rank[xRoot] += 1

    def num_disjoint_set(self):
        return len(set(self.parent))


n, m = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(m)]

dset = DisjointSet(n)

for x, y, _ in g:
    dset.union(x - 1, y - 1)

print(dset.num_disjoint_set())

Submission status: Wrong Answer

Solution code:
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, M = map(int,input().split())
q = []
c = [0 for i in range(N)]
A = [[] for i in range(N)]

for i in range(M):
	x, y, z = map(int,input().split())
	x = x - 1
	y = y - 1
	A[x].append(y)
	#A[y].append(x)

cost = 0
for i in range(N):
	if c[i] == 0:
		cost = cost + 1
		q.append(i)
		while len(q):
			j = q.pop(0)
			c[j] = 1
			for k in A[j]:
				if c[k] == 0:
					q.append(k)

print(cost)

Submission status: Wrong Answer

Solution code:
N,M = (int(x) for x in input().split())

#魔法実行回数
magic_act_num = 0

known = [False for x in range(N)]
judge = 0
for i in range(M):
	x,y,z = (int(val) for val in input().split())

	# zは気にしなくてよい
	if i == 0:
		known[x-1]=True
		known[y-1]=True
		judge += 2
		magic_act_num+=1
	else:
		if known[x-1] == True:
			if known[y-1] == True:
				magic_act_num -= 1
				continue
			else:
				known[y-1] = True
				judge += 1
		else:
			if known[y-1] == True:
				known[x-1] = True
				judge += 1
			else:
				known[x-1] = True
				known[y-1] = True
				judge += 2
				magic_act_num += 1

magic_act_num += (N-judge)

print(magic_act_num)

Submission status: Wrong Answer

Solution code:
N,M = (int(x) for x in input().split())

#魔法実行回数
magic_act_num = 0

known = [False for x in range(N)]
judge = 0
for i in range(M):
	x,y,z = (int(val) for val in input().split())

	# zは気にしなくてよい
	if i == 0:
		known[x-1]=True
		known[y-1]=True
		judge += 2
		magic_act_num+=1
	else:
		if known[x-1] == True:
			if known[y-1] == True:
				magic_act_num-=1
				continue
			else:
				known[y-1] = True
				judge += 1
		else:
			if known[y-1] == True:
				known[x-1] = True
				judge += 1
			else:
				known[x-1] = True
				known[y-1] = True
				judge += 2
				magic_act_num+=1

magic_act_num += (N-judge)

print(magic_act_num)

Submission status: Wrong Answer

Solution code:
N,M = (int(x) for x in input().split())

#魔法実行回数
magic_act_num = 0

known = [False for x in range(N)]
judge = 0
for i in range(M):
	x,y,z = (int(x) for x in input().split())

	# zは気にしなくてよい
	if i == 0:
		known[x-1]=True
		known[y-1]=True
		judge += 2
		magic_act_num+=1
	else:
		if known[x-1] == True:
			if known[y-1] == True:
				continue
			else:
				known[y-1] = True
				judge += 1
		else:
			if known[y-1] == True:
				known[x-1] = True
				judge += 1
			else:
				known[x-1] = True
				known[y-1] = True
				judge += 2
				magic_act_num+=1

magic_act_num += (N-judge)

print(magic_act_num)

Submission status: Wrong Answer

Solution code:
N,M = (int(x) for x in input().split())

#魔法実行回数
magic_act_num = 0

known = []
judge = 0
for i in range(M):
	x,y,z = (int(x) for x in input().split())

	# zは気にしなくてよい
	if i == 0:
		known.append(x)
		known.append(y)
		judge += 2
		magic_act_num+=1
	else:
		if x in known:
			if y in known:
				continue
			else:
				known.append(y)
				judge += 1
		else:
			if y in known:
				known.append(x)
				judge += 1
			else:
				known.append(x)
				known.append(y)
				judge += 2
				magic_act_num+=1

magic_act_num += (N-judge)

print(magic_act_num)

Submission status: Wrong Answer

Solution code:
def solve(n, m, x, y, z):
    parent = {i: i for i in range(1, n+1)}
    def find(v):
        if v == parent[v]:
            return v
        else:
            return find(parent[v])
    def union(u, v):
        u = find(u)
        v = find(v)
        if u > v:
            u, v = v, u
        parent[v] = u
    for i in range(m):
        union(x[i], y[i])
    return len(set(parent.values()))

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())
print(solve(n, m, x, y, z))

Submission status: Wrong Answer

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

xy = [0 for _ in range(n + 1)]


def root(x):
    i = x
    while xy[i] != 0:
        i = xy[i]
    return i


for _ in range(m):
    x, y, z = map(int, input().split())
    r = root(y)
    if r != x:
        xy[r] = x

ans = 0
for i in xy[1:]:
    if i == 0:
        ans += 1

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())
par=[i for i in range(n)]
size=[0 for i in range(n)]
co=n

def root(a):
  if par[a]==a:
    return a
  else:
    b= root(par[a])
    par[a]=b
    return b


def unite(a,b):
  x=root(a)
  y=root(b)
  if size[a]>size[b]:
    par[b]=a
  else:
    par[a]=b
  if size[a]==size[b]:
    size[b]+=1


def check(a,b):
  return root(a)==root(b)

for i in range(m):
  if not check(x[i]-1,y[i]-1):
    co-=1
    unite(x[i]-1,y[i]-1)
print(co)

Submission status: Wrong Answer

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

xy = [0 for _ in range(n + 1)]

for _ in range(m):
    x, y, z = map(int, input().split())
    if xy[y] == 0:
        xy[y] = x

ans = -1
for i in xy:
    if i == 0:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

xy = [0 for _ in range(n + 1)]

for _ in range(m):
    x, y, z = map(int, input().split())
    if xy[y] == 0:
        xy[y] = x
    elif xy[x] == 0:
        xy[x] = y

ans = 0
for i in xy:
    if i == 0:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

xy = []
for _ in range(m):
    a = set(input().split()[:2])
    for b in xy:
        if not a.isdisjoint(b):
            b |= a
            break
    else:
        xy += [a]

for i, a in enumerate(xy):
    for b in xy[:i]:
        if not a.isdisjoint(b):
            b |= a
            xy.remove(a)
            break

s = set()
for a in xy:
    s |= a

print(n - len(s) + len(xy))

Submission status: Wrong Answer

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

xy = []
for _ in range(m):
    s = set(input().split()[:2])
    for a in xy:
        if not s.isdisjoint(a):
            a |= s
            break
    else:
        xy += [s]

for a in xy:
    for b in xy:
        if a != b:
            if not a.isdisjoint(b):
                a |= b
                xy.remove(b)

s = set()
for a in xy:
    s |= a

print(n - len(s) + len(xy))

Submission status: Wrong Answer

Solution code:
from functools import reduce
from itertools import groupby

n, m = map(int, input().split())
xy = [set(map(int, input().split()[:2])) for i in range(m)]

for a in xy:
    for b in xy:
        if not a == b:
            for c in b:
                if c in a:
                    a |= b
                    xy.remove(b)
                    break

s = set()
for a in xy:
    s |= a

print(n - len(s) + len(xy))

Submission status: Wrong Answer

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

    
    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 groupsize(self):
        self.cnt = 0
        for i, x in enumerate(self.par):
            if x == i:
                self.cnt += 1
            return self.cnt
    
    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)

N, M = map(int,input().split())
A = [list(map(int,input().split())) for i in range(M)]
uf = UnionFind(N)

for i in range(M):
    uf.union(A[i][0]-1, A[i][1]-1)

print(uf.groupsize())

Submission status: Wrong Answer

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

s = set(sum(xy, []))

for a in xy:
    for b in xy:
        if not a == b:
            for c in b:
                if c in a:
                    a = list(set(a + b))
                    xy.remove(b)
                    break

print(n - len(s) + len(xy))

Submission status: Wrong Answer

Solution code:
N,M=list(map(int,input().split()))
total=0
ans=[-1 for _ in range(N)]
for i in range(M):
    tmp=list(map(int,input().split()))
    if ans[tmp[0]-1]==-1 and ans[tmp[1]-1]==-1:
        total+=1
    ans[tmp[0]-1]=0
    ans[tmp[1]-1]=0
print(total+ans.count(-1))

Submission status: Wrong Answer

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

array = [0] * n

for _ in range(k):
    x, y, z = map(int, input().split())
    if array[x - 1] == 0 and array[y -1] == 0:
        array[x - 1] = 1

print(array.count(0))

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)

N, M = map(int, input().split())
uftree = UnionFind(N)
for i in range(M):
    X, Y, Z = map(int, input().split())
    uftree.union(X, Y)

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

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
known = [False for _ in range(N)]
cost = 0

for i in range(M):
    X, Y, Z = map(int,input().split())
    if X == Y:
      known[X-1] = True
    else:
      if not known[X-1] and not known[Y-1]:
        cost += 1
        known[X-1] = True
        known[Y-1] = True
      elif known[X-1]:
        known[Y-1] = True
      else:
        known[Y-1] = True

for i in range(N):
    if not known[i]:
        cost +=1

print(cost)

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
known = [False for _ in range(N)]
cost = 0

for i in range(M):
    X, Y, Z = map(int,input().split())
    if not known[X-1] and not known[Y-1]:
        cost += 1
        known[X-1] = True
        known[Y-1] = True
    elif known[X-1]:
        known[Y-1] = True
    else:
        known[Y-1] = True

for i in range(N):
    if not known[i]:
        cost +=1

print(cost)

Submission status: Wrong Answer

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