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:
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
import sys
s = sys.stdin.readlines()
N, M = map(int, s[0].split())
look_set_list = []
for e in s[1:]:
    X, Y, Z = map(int, e.split())
    flg = 0
    for ls in look_set_list:
        if X in ls:
            ls.add(X)
            ls.add(Y)
            flg = 1
            break
        elif Y in ls:
            ls.add(X)
            ls.add(Y)
            flg = 1
            break
    if flg == 0:
    	look_set_list.append(set([X, Y]))

num_of_uniq_num = 0
for ls in look_set_list:
  num_of_uniq_num += len(ls)
O = N - num_of_uniq_num + len(look_set_list)
print(O)

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

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

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

a = UnionFind(n)
for i in range(m):
    x,y,z = map(int, input().split())
    x-=1
    y-=1
    a.union(x,y)

print(len(set(a.par)))

Submission status: Wrong Answer

Solution code:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.root(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if i < j:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

    def same(self, i, j):
        return self.root(i) == self.root(j)


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


def main():
    n, m = intin()
    xyzlist = intinl(m)

    u = UnionFind(n)
    for x, y, z in xyzlist:
        u.unite(x - 1, y - 1)

    return

    ansset = set()
    for i in range(n):
        ansset.add(u.root(i))

    print(len(ansset))



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


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

hints = []
for i in range(M):
    hints += [list(map(int, input().split()))]

union = UnionFind(N)
for hint in hints:
    x = hint[0]
    y = hint[1]
    union.union(x, y)

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

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
ans = [0]*N
x,y,z = map(int,input().split())
ans[x-1] = 1
ans[y-1] = 1
if M >= 2:
  for i in range(M-2):
    x,y,z = map(int,input().split())
    if ans[x-1] == 0 and ans[y-1] == 0:
      ans[x-1] = 1
      ans[y-1] = 1
print(N-sum(ans))

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 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 = UnionFind(n)
for i in range(m):
    x,y,z = map(int, input().split())
    x-=1
    y-=1
    a.union(x,y)
print(len(set(a.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 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 = UnionFind(n)
for i in range(m):
    x,y,z = map(int, input().split())
    x-=1
    y-=1
    a.union(x,y)
print(a.par)
print(len(set(a.par)))

Submission status: Wrong Answer

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

    # 検索
    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())

a = UnionFind(n)
for i in range(m):
    x,y,z = map(int, input().split())
    x-=1
    y-=1
    a.union(x,y)

print(len(set(a.par[:n])))

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self,n):
        self.parent=[i for i in range(n)]
        self.rank=[0 for _ in range(n)]

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

    def union(self,x,y):
        rootx=self.find(x)
        rooty=self.find(y)
        if self.rank[rootx]<self.rank[rooty]:
            self.parent[rootx]=rooty
        else:
            self.parent[rooty]=rootx
            if self.rank[rootx]==self.rank[rooty]:
                self.rank[rootx]+=1

n,m=map(int,input().split())
xyz=[list(map(int,input().split())) for _ in range(m)]
uf=UnionFind(n)
for x,y,z in xyz:
    x,y=x-1,y-1
    uf.union(x,y)

# print(uf.parent)
print(len(set(uf.parent)))

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())
a=UnionFind(n)
for i in range(m):
    x,y,z=map(int,input().split())
    if a.same_check(x,y):
        pass
    else:
        a.union(x,y)
answer=set()
for i in a.par:
    if not i==0:
        answer.add(i)
print(len(answer))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
par=[]
rank=[]
for i in range(n+1):
  par.append(i)
  rank.append(0)
def find(x,par):
  if par[x] == x:
    return x
  else:
    return find(par[x],par)
def unite(x,y,par,rank):
  x = find(x,par)
  y = find(y,par)
  if x != y:
    if rank[x] < rank[y]:
      par[x] = y
    else:
      par[y] = x
      if rank[x]==rank[y]:
        rank[x] += 1
for i in range(m):
  x,y,z=map(int,input().split())
  unite(x,y,par,rank)
print(len(set(par))-1)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
xy = [list(map(int,input().split())) for _ in range(M)]
par = [-1] * N

def get_parent(n):
  if par[n] == -1:
    return n
  else:
    par[n] = get_parent(par[n])
    return par[n]

  def merge(i,j):
    i = get_parent(i)
    j = get_parent(j)
    if i != j:
      par[j] = i
      return

    for x, y in xy:
      merge(x-1, y-1)

      print(par.count(-1))

Submission status: Wrong Answer

Solution code:
class Union_Tree:
    def __init__(self, N):
        self.group_num = [i for i in range(N)]
        self.childs = [[] for i in range(N)]

    def change_group(self, _from, num):
        self.group_num[_from] = num
        for child in self.childs[_from]:
            self.group_num[child] = num
        self.childs[num].extend(self.childs[_from])
        self.childs[_from].clear()

    def unite(self, a, b):
        a_par = self.group_num[a]
        b_par = self.group_num[b]
        if len(self.childs[a_par]) >= len(self.childs[b_par]):
            # bの親グループをaのグループに統合
            self.change_group(b_par, a_par)
        else:
            self.change_group(a_par, b_par)



N, M = map(int, input().split(" "))
ut = Union_Tree(N)

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

print(len(set(ut.group_num)))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
appeared = set()
sets = []
for _ in range(m):
    x, y, z = map(int, input().split())
    appeared.add(x)
    appeared.add(y)

    inset = []
    for i in range(len(sets)):
        if x in sets[i] or y in sets[i]:
            inset.append(i)
    if inset:
        sets[inset[0]].add(x)
        sets[inset[0]].add(y)

        for i in range(1, len(inset)):
            sets[inset[0]] |= sets[i]
        for i in reversed(inset[1:]):
            del sets[i]
    else:
        sets.append({x, y})

print(n - len(appeared) + len(sets))

Submission status: Wrong Answer

Solution code:
N,M = input().split()
N = int(N)
M = int(M)
list = []
A_list = []

for i in range(M):
    x,y,z = input().split()
    x,y,z = int(x),int(y),int(z)
    list.append([x,y,z])

A_list.append([list[0][0]])
for data in list:
    check = 0
    for A_data in A_list:
        if data[0] in A_data:
            A_data.append(data[1])
            check = 0
        elif data[1] in A_data:
            A_data.append(data[0])
            check = 0
        elif not data[0] in A_data and not data[1] in A_data:
            check = 1
    if check:
        A_list.append([data[0],data[1]])

print(len(A_list))

Submission status: Wrong Answer

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

k = []
j = list(range(1, n+1))

for _l in l:
    if _l[0] in j:
        j.remove(_l[0])
    if _l[1] in j:
        j.remove(_l[1])
    for _k in k:
        if _l[0] in _k:
            if _l[1] not in _k:
                _k.append(_l[1])
            break
    else:
        k.append([_l[0], _l[1]])

print(len(k)+len(j))

Submission status: Wrong Answer

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

# Union Find
# N = 100
PARENT = list(range(N))

used = set()

def root(n):
    if PARENT[n] == n:
        return n
    else:
        ret = root(PARENT[n])
        PARENT[n] = ret
        return ret

def same(n1, n2):
    return root(n1) == root(n2)

def unite(n1, n2):
    n1 = root(n1)
    n2 = root(n2)
    if n1 == n2:
        return
    PARENT[n1] = n2



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

    used.add(x)
    used.add(y)
    rootX = root(x)
    rootY = root(y)

    if z % 2 == 0:
        unite(x, y)


ans = len(set(PARENT))//2 + (N-len(used))
print(ans)

Submission status: Wrong Answer

Solution code:
N,M=list(map(int,input().split()))
hoge=[i for i in range(1,N+1)]
total=0
for i in range(M):
    tmp=list(map(int,input().split()))
    if not(tmp[0] in hoge):
        try:
            hoge.remove(tmp[1])
        except:
            pass
    if not(tmp[1] in hoge):
        try:
            hoge.remove(tmp[0])
        except:
            pass
    if (tmp[0] in hoge)and(tmp[1] in hoge):
        hoge.remove(tmp[0])
        hoge.remove(tmp[1])
        total+=1
        
print(total+len(hoge))

Submission status: Wrong Answer

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

condition = []
for i in range(M):
    condition.append(list(map(int, input().split(' '))))
#print(condition)

A = [0] * N
cost = 0
for cond in condition:
    if(A[cond[0] - 1] == 0 and A[cond[1] - 1] == 0):
        cost += 1
    A[cond[0] - 1] = A[cond[1] - 1] = 1

for a in A:
    if(a == 0):
        cost += 1

print(cost)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

validDict = defaultdict(int)
valid = 0

for key in dd:
    for e in dd[key]:
        if validDict[key] == 1 and validDict[e] == 1:
            continue
        validDict[key] = 1
        validDict[e] = 1
        valid += 1

ans = N - valid
print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n + 1)]
        self.rank = [0 for _ in range(n + 1)]
        self.size = [1] * (n + 1)
        self.group = [[i] for i in range(n + 1)]
 
    def find(self, x):
        # If x is root
        if self.parent[x] == x:
            return x
        # If x is not root, search again by using x's parent
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
 
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        # Make an edge from the root of lower tree to the root of higher tree
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[y] = x
            self.size[x] += self.size[y]
            # If the height of tree the tree is the same, increase one of the heights by 1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
 
    def check_same(self, x, y):
        return self.find(x) == self.find(y)
 
    def get_size(self, x):
        return self.size[self.find(x)]
 
    def merge(self, x, y):
        """
        "データ構造をマージする一般的なテク"
        """
        x = self.find(x)
        y = self.find(y)
        if len(self.group[x]) < len(self.group[y]):
            x, y = y, x
        self.group[x].extend(self.group[y])
        self.group[y] = []
        self.parent[y] = x
 
 
 
N, M = map(int, input().split())
 
items = []
visible = set()
uf = UnionFind(N)
for i in range(M):
    x, y, z = map(int, input().split())
    uf.union(x, y)
    items.append((x, y, z))
 
se = set()
ans = 0
for i in range(1, N+1):
    tmp = uf.find(i)
    if tmp in se:
        continue
    else:
        ans += 1
        se.add(i)
 
print(ans)

Submission status: Wrong Answer

Solution code:

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

A = [0 for i in range(N)]
HINT = []

for i in range(M):
    (X, Y, Z) = map(int, input().split(" "))
    A[X - 1] += 1
    A[Y - 1] += 1
    HINT.append([X - 1, Y - 1])
    
ansCount = 0
checked = 0

for i in range(N):
    if A[i] == 0:
        ansCount += 1
        checked += 1
        
while(checked != N):
    maxIndex = A.index(max(A))
    checked += 1
    ansCount += 1
    
    for i in range(len(HINT)):
        if HINT[i][0] == maxIndex or HINT[i][1] == maxIndex:
            checked += 1
            A[HINT[i][0]] = 0
            A[HINT[i][1]] = 0


print(ansCount)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
import sys
s = sys.stdin.readlines()
N, M = map(int, s[0].split())
look_set = set([])
counter = 0
for e in s[1:]:
    X, Y, Z = map(int, e.split())
    if X not in look_set:
        if Y not in look_set:
            counter += 1
    look_set.add(X)
    look_set.add(Y)
 
O = N - len(look_set) + counter
print(O)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
xyz = [list(map(int, input().split())) for _ in range(m)]
type_a = []
type_b = []
for i in range(m):
    if xyz[i][2] % 2 == 1:
        # z が奇数 = ax と ay は奇遇が異なる
        if xyz[i][0] in type_a:
            type_b.append(xyz[i][1])
        elif xyz[i][0] in type_b:
            type_a.append(xyz[i][1])
        else:
            type_b.append(xyz[i][1])
    else:
        # z が偶数 = ax と ay は奇遇が同じ
        if xyz[i][0] in type_a:
            type_a.append(xyz[i][1])
        elif xyz[i][0] in type_b:
            type_b.append(xyz[i][1])
        else:
            type_a.append(xyz[i][1])
uniq_a = list(set(type_a))
uniq_b = list(set(type_b))
print(n - len(uniq_a) - len(uniq_b))

Submission status: Wrong Answer

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

k = []
j = list(range(1, n+1))

for _l in l:
    if _l[0] in j:
        j.remove(_l[0])
    if _l[1] in j:
        j.remove(_l[1])
    for _k in k:
        if _l[0] in _k:
            if _l[1] not in _k:
                _k.append(_l[1])
            break
    else:
        k.append([_l[0], _l[1]])
        
print(len(k)+len(j))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
ans = [0]*N
x,y,z = map(int,input().split())
ans[x-1] = 1
ans[y-1] = 1
if M >= 2:
  for i in range(M-2):
    x,y,z = map(int,input().split())
    if ans[x-1] == 0 and ans[y-1] == 0:
      ans[x-1] = 1
      ans[y-1] = 1
print(N-sum(ans)+1)

Submission status: Wrong Answer

Solution code:
n, m = [int(i) for i in input().split()]
list_check = [0 for i in range(n)]
r_list = set()
d_list = set()
all_set = set([i + 1 for i in range(n)])
for i in range(m):
    x1, x2, _ = [int(i) for i in input().split()]
    if x1 not in r_list and x1 not in d_list:
        r_list.add(x1)
        d_list.add(x2)
        continue
    elif x1 in d_list and x2 not in r_list:
        d_list.add(x2)
        continue
    elif x2 not in r_list and x2 not in d_list:
        r_list.add(x2)
        d_list.add(x1)
        continue
    elif x2 in d_list and x1 not in r_list:
        d_list.add(x1)
        continue

print(n - len((d_list)))

Submission status: Wrong Answer

Solution code:
import sys
imput = sys.stdin.readline
n,m = map(int,input().split())
s = [input().split() for i in range(m)]
li = [[s[0][0],s[0][1]]]
del s[0]
for item in s:
  num_1 = item[0]
  num_2 = item[1]
  for group in li:
    if num_1 in group and num_2 in group:
      flag=0
      pass
      break
    elif num_1 in group:
      group.append(num_2)
      flag=0
      break
    elif num_2 in group:
      group.append(num_1)
      flag=0
      break
    else:
      flag = 1
  if flag:
    li.append([num_1,num_2])
count = 0
for j in li:
  count += len(j)-1
print(n-count)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

from collections import deque
from copy import copy
import sys
sys.setrecursionlimit(10 ** 6)

def dfs(n):
    stack = graph[n]
    while stack:
        x = stack.popleft()
        dfs(x)
    checked[n] = True

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

graph = {i: deque() for i in range(N)}
checked = [False for _ in range(N)]

con_com = 0

for _ in range(M):
    x, y, _ = list(map(int, input().split()))
    graph[min(x, y)-1].append(max(x, y)-1)

for i in range(N):
    if checked[i]:
        continue
    dfs(i)
    con_com += 1

print(con_com)

Submission status: Wrong Answer

Solution code:
num=[]
num=[int(i) for i in input().split()]

zyouken = []

for i in range(num[1]):
    zyouken.append(input())

count_arr = [0 for i in range(num[0])]

zyouken_2 = []
zyouken_3 =[]

for temp in zyouken:
    arr = temp.split()
    zyouken_2.append(int(arr[0]))
    zyouken_3.append(int(arr[1]))

for i,temp in enumerate(zyouken_3):
    if zyouken_2[i] != temp:
        count_arr[temp-1] = 1

print(count_arr.count(0))

Submission status: Wrong Answer

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

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

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

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]


n, m = map(int, input().split())
a = [list(map(int, input().split())) for i in range(m)]
uf = UnionFind(n)
for i in a:
    uf.union(i[0]-1,i[1]-1)

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

Submission status: Wrong Answer

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

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

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

    # 併合
    def 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)


U=UnionFind(N)
for i in range(M):
    U.union(XYZ[i][0], XYZ[i][1])

print(len(set(list(U.par)))-1)

Submission status: Wrong Answer

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

@author: Owner
"""

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

"""

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

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

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

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

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


    


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

    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
x=[]
y=[]
z=[]
for _ in range(M):
    X,Y,Z = (int(i) for i in input().split()) 
    x.append(X)
    y.append(Y)
    z.append(Z)
    
a = [-1] * N
num=0
finished=0
#nにしたい

for i in range(len(x)):
  if a[x[i]-1]<0:
    if a[y[i]-1]<0:
      a[x[i]-1]=1
      finished=finished+1
    else:
      a[x[i]-1]=1   
  a[y[i]-1]=1
  
    
finished=finished+a.count(-1)
print(finished)