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:
from collections import Counter

INF = float('inf')

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

j = 0
while j < N:
    k = par[j]
    if k >= 0:
        par[j] = par[k]
    j += 1

print(len(Counter(par)))

Submission status: Wrong Answer

Solution code:
from collections import Counter

INF = float('inf')

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

j = N - 1
while j >= 0:
    O = []
    i = j
    q = INF
    while True:
        q = par[i]
        if not(0 <= q <= N):
            break
        O.append(i)
        i = q
    for o in O:
        par[o] = q
    j -= 1

print(len(Counter(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())
uni = UnionFind(n-1)

for i in range(m):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    uni.union(a,b)
print(len(set(uni.par)))

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

for i in range(N):
    i = N - i - 1
    q = par[i]
    O = []
    while 0 <= q <= N:
        O.append(i)
        i = q
        q = par[i]
    for o in O:
        par[o] = q

print(len(Counter(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())
    if a.same_check(X,Y):
        pass
    else:
        a.union(X,Y)
answer=set()
for i in range(1,N+1):
    answer.add(a.par[i])
print(len(answer))

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 range(1,n+1):
    answer.add(a.par[i])
print(len(answer))

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())
uni = UnionFind(n-1)

for i in range(m):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    uni.union(a,b)
print(len(set(uni.par)))

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline
N, M = map(int, input().split())
pair = {}
rank = {}
def root(x):
    if x == pair[x]:
        return x
    else:
        pair[x] = root(pair[x])
    return pair[x]

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
      return
    if rx > ry:
        pair[rx] = pair[ry]
    else:
        pair[ry] = pair[rx]

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

for i in range(1, N+1):
    pair.setdefault(i, i)

for i in range(1, N+1):
    rank.setdefault(i, 0)

for i in range(M):
    x, y, z = map(int, input().split())
    if not same(x, y):
        if x < y:
            unite(x, y)
        else:
            unite(y, x)
cnt = set()
for k, y in pair.items():
    # y = root(y)
    cnt.add(y)
print(len(cnt))

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline
N, M = map(int, input().split())
pair = {}
rank = {}
def root(x):
    if x == pair[x]:
        return x
    else:
        pair[x] = root(pair[x])
    return pair[x]

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx > ry:
        pair[rx] = pair[ry]
    else:
        pair[ry] = pair[rx]

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

for i in range(1, N+1):
    pair.setdefault(i, i)

for i in range(1, N+1):
    rank.setdefault(i, 0)

for i in range(M):
    x, y, z = map(int, input().split())
    if not same(x, y):
        if x < y:
            unite(x, y)
        else:
            unite(y, x)
cnt = set()
for k, y in pair.items():
    # y = root(y)
    cnt.add(y)
print(len(cnt))

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline
N, M = map(int, input().split())
pair = {}
rank = {}
def root(x):
    if x == pair[x]:
        return x
    else:
        pair[x] = root(pair[x])
    return pair[x]

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx > ry:
        pair[rx] = pair[ry]
    else:
        pair[ry] = pair[rx]

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

for i in range(1, N+1):
    pair.setdefault(i, i)

for i in range(1, N+1):
    rank.setdefault(i, 0)

for i in range(M):
    x, y, z = map(int, input().split())
    if not same(x, y):
        unite(x, y)
    """
    if x < y:
        unite(x, y)
    else:
        unite(y, x)
    """

cnt = set()
for k, y in pair.items():
    # y = root(y)
    cnt.add(y)
print(len(cnt))

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline
N, M = map(int, input().split())
pair = {}
rank = {}
def root(x):
    if x == pair[x]:
        return x
    else:
        pair[x] = root(pair[x])
    return pair[x]

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx > ry:
        pair[rx] = pair[ry]
    else:
        pair[ry] = pair[rx]

for i in range(1, N+1):
    pair.setdefault(i, i)

for i in range(1, N+1):
    rank.setdefault(i, 0)

tmp = []
for i in range(M):
    tmp.append(list(map(int, input().split())))
tmp.sort()
for i in range(M):
    x, y = tmp[i][0], tmp[i][1]
    if x < y:
        unite(x, y)
    else:
        unite(y, x)

cnt = set()
for k, y in pair.items():
    cnt.add(y)
print(len(cnt))

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline
N, M = map(int, input().split())
pair = {}
rank = {}
def root(x):
    if x == pair[x]:
        return x
    else:
        pair[x] = root(pair[x])
    return pair[x]

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx > ry:
        pair[rx] = pair[ry]
    else:
        pair[ry] = pair[rx]

for i in range(1, N+1):
    pair.setdefault(i, i)

for i in range(1, N+1):
    rank.setdefault(i, 0)

tmp = []
for i in range(M):
    tmp.append(list(map(int, input().split())))
tmp.sort()
for i in range(M):
    x, y = tmp[i][0], tmp[i][1]
    unite(x, y)

cnt = set()
for k, y in pair.items():
    cnt.add(y)
print(len(cnt))

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline
N, M = map(int, input().split())
pair = {}
rank = {}
def root(x):
    if x == pair[x]:
        return x
    else:
        pair[x] = root(pair[x])
    return pair[x]

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rank[rx] < rank[ry]:
        pair[rx] = ry
    else:
        pair[ry] = rx
        if rx == ry:
            rank[rx] += 1

for i in range(1, N+1):
    pair.setdefault(i, i)

for i in range(1, N+1):
    rank.setdefault(i, 0)

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

cnt = set()
for k, y in pair.items():
    cnt.add(y)
print(len(cnt))

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline
N, M = map(int, input().split())
pair = {}
rank = {}
def root(x):
    if x == pair[x]:
        return x
    else:
        pair[x] = root(pair[x])
    return pair[x]

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rank[rx] < rank[ry]:
        pair[rx] = ry
    else:
        pair[ry] = rx
        if rx == ry:
            rank[rx] += 1

for i in range(1, N+1):
    pair.setdefault(i, i)

for i in range(1, N+1):
    rank.setdefault(i, 0)

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

cnt = set()
for k, y in pair.items():
    # ry = root(y)
    cnt.add(y)
print(len(cnt))

Submission status: Wrong Answer

Solution code:
N,M = (int(i) for i in input().split())
e = [[int(i) for i in input().split()] for i in range(M)]
hoge = set()

zenbu = {int(i + 1) for i in range(N)}
result = 0

for i in e:
    if {i[0]}.issubset(hoge) == False and {i[1]}.issubset(hoge) == False:
        result += 1
    hoge.add(i[0])
    hoge.add(i[1])

hoge_difference = zenbu - hoge
result += len(hoge_difference)


print(result)

Submission status: Wrong Answer

Solution code:
ans,n=map(int,input().split())
l=[list(map(int,input().split())) for i in range (n)]
a=set()
for i in range (n):
    if l[i][0] in a and l[i][1] in a:
        continue
    else:
        ans-=1
        a.add(l[i][0])
        a.add(l[i][1])
print(ans)

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

pairs = XYZ[:]
known = [False] * (N)

pairs = sorted(pairs)

# UnionFindの元
class UnionFind:
    def __init__(self, n):
        # n : ノード数（ノード番号は0始まり）
        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 is_group(self, x, y):
        return self.find(x) == self.find(y)
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

# UnionFindでグループ化
def create_union(edges, v_num):
    # edges: 辺
    # v_num: ノード数
    u = UnionFind(v_num)
    for x,y in edges:
        u.union(x,y)
    return u.par
    
    
edges = [(x,y) for x,y,z in pairs]

parents = create_union(edges, N+1)
union = set()
for p in parents:
    union.add(p)
union_num = len(union) -1
print(union_num)

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))
    
pairs = XYZ[:]
known = [False] * (N)

pairs = sorted(pairs)

ans = 0
for x,y,z in pairs:
    x = x-1
    y = y-1
    if (not known[x]) and (not known[y]):
        ans += 1
        known[x] = True
        known[y] = True
    else:
        known[x] = True
        known[y] = True
ans += known.count(False)
print(ans)

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))
pairs = XYZ[:]
known = [False] * (N)

ans = 0
for x,y,z in pairs:
    x = x-1
    y = y-1
    if (not known[x]) and (not known[y]):
        ans += 1
        known[x] = True
        known[y] = True
    else:
        known[x] = True
        known[y] = True
ans += known.count(False)
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
XYZ = []
for _ in range(M):
    x,y,x = map(int, input().split())
    XYZ.append((x,y,x))
    
pairs = XYZ[:]
known = [False] * (N)

ans = 0
for x,y,z in pairs:
    x = x-1
    y = y-1
    if (not known[x]) and (not known[y]):
        ans += 1
        known[x] = True
        known[y] = True
    else:
        known[x] = True
        known[y] = True
ans += known.count(False)
print(ans)

Submission status: Wrong Answer

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

count=0
for i in range(m):
  x,y,z=map(int,input().split())
  if x not in cards and y not in cards:
    count+=1
    cards.append(x)
    cards.append(y)
  elif x in cards and y not in cards:
    cards.append(y)
  elif x not in cards and y in cards:
    cards.append(x)

count+=n-len(cards)
 
print(count)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
in_list=[]
cards=[]
z_list=[]
count=0
for i in range(m):
  in_list.append(list(map(int,input().split())))
 
in_list=sorted(in_list)
 
for j in range(m):
  if in_list[j][0] not in cards and in_list[j][1] not in cards:
    count+=1
  cards.append(in_list[j][0])
  cards.append(in_list[j][1])
 
cards=set(cards)
 
count+=n-len(cards)
 
print(count)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
in_list=[]
cards=[]
z_list=[]
count=0
for i in range(m):
  x,y,z=map(int,input().split())
  if x not in cards and y not in cards:
    count+=1
  cards.append(x)
  cards.append(y)

cards=set(cards)
count+=n-len(cards)
 
print(count)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
in_list=[]
cards=[]
z_list=[]
count=0
for i in range(m):
  in_list.append(list(map(int,input().split())))
  if in_list[i][0] not in cards and in_list[i][1] not in cards:
    count+=1
    cards.append(in_list[i][0])
    cards.append(in_list[i][1])
 
cards=set(cards)
 
count+=n-len(cards)
 
print(count)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
in_list=[]
cards=[]
z_list=[]
count=0
for i in range(m):
  in_list.append(list(map(int,input().split())))
  if in_list[i][0] not in cards and in_list[i][1] not in cards:
    count+=1
  cards.append(in_list[i][0])
  cards.append(in_list[i][1])
 
cards=set(cards)
 
count+=n-len(cards)
 
print(count)

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:
        if x2 not in r_list and x2 not in d_list:
            r_list.add(x1)
            d_list.add(x2)
            continue
        else:
            d_list.add(x1)
            continue
    else:
        d_list.add(x2)
        continue
       

print(n - len((d_list)))

Submission status: Wrong Answer

Solution code:
def change_par(num, val):
    tmp_par = par[num]
    par[num] = val
    if tmp_par != val:
        change_par(tmp_par, val)

N, M = map(int, input().split(" "))
par = [i for i in range(N)]
ind = [i for i in range(N)]

for i in range(M):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    par_x = par[x]
    par_y = par[y]
    if par_x == x and par_y == y:
        par[y] = x
    elif par_x == x and par_y != y:
        par[par_y] = par_x
    elif par_y == y and par_x != x:
        par[par_x] = par_y
    elif par_x != x and par_y != y:
        par[x] = par_y
        change_par(par_x, par_y)
        change_par(par_y, par_y)

count = 0
for i in range(N):
    if par[i] == i:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split(" "))
par = [i for i in range(N)]

def change_par(num, val):
    par[num] = val
    if par[num] != num:
        change_par(par[num], val)

for i in range(M):
    x, y, z = map(int, input().split(" "))
    x -= 1
    y -= 1
    par_x = par[x]
    par_y = par[y]
    if par_x == x and par_y == y:
        par[y] = x
    elif par_x == x and par_y != y:
        par[par_y] = par_x
    elif par_y == y and par_x != x:
        par[par_x] = par_y
    elif par_x != x and par_y != y:
        change_par(par_x, par_y)
        change_par(par_y, par_y)


count = 0
for i in range(N):
    if par[i] == i:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split(" "))
par = [i for i in range(N)]

for i in range(M):
    x, y, z = map(int, input().split(" "))
    x -= 1
    y -= 1
    par_x = par[x]
    par_y = par[y]
    if par_x == x and par_y == y:
        par[y] = x
    elif par_x == x and par_y != y:
        par[par_y] = par_x
    elif par_y == y and par_x != x:
        par[par_x] = par_y
    elif par_x != x and par_y != y:
        if par_y != par_x:
            if par[par_x] != par_y and par[par_y] != par_x:
                par[par_y] = par_x


count = 0
for i in range(N):
    if par[i] == i:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10**8)
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 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[x] += 1

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

#####
N, M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
    ui, vi, wi = map(int, input().split())
    uf.union(ui, vi)
print(len(np.unique(uf.par[1:])))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split(" "))
par = [i for i in range(N)]

for i in range(M):
    x, y, z = map(int, input().split(" "))
    x -= 1
    y -= 1
    par_x = par[x]
    par_y = par[y]
    if par_x == x and par_y == y:
        par[y] = x
    elif par_x == x and par_y != y:
        par[par_y] = par_x
    elif par_y == y and par_x != x:
        par[par_x] = par_y
    elif par_x != x and par_y != y:
        if par[par_x] != par_y:
            par[par_y] = par_x


count = 0
for i in range(N):
    if par[i] == i:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10**8)
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())
uf = UnionFind(N)
for i in range(M):
    ui, vi, wi = map(int, input().split())
    uf.union(ui, vi)
print(len(np.unique(uf.par[1:])))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split(" "))
par = [i for i in range(N)]

for i in range(M):
    x, y, z = map(int, input().split(" "))
    x -= 1
    y -= 1
    par_x = par[x]
    par_y = par[y]
    if par_x == x and par_y == y:
        par[y] = x
    else:
        if par_x == x and par_y != y:
            par[par_y] = par_x
        elif par_y == y and par_x != x:
            par[par_x] = par_y

count = 0
for i in range(N):
    if par[i] == i:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split(" "))
par = [i for i in range(N)]

for i in range(M):
    x, y, z = map(int, input().split(" "))
    x -= 1
    y -= 1
    par_x = par[x]
    par_y = par[y]
    if par_x == x and par_y == y:
        par[y] = x
    else:
        if par_x == x and par_y != y:
            if par_y != x:
                par[par_x] = par_y
        elif par_y == y and par_x != x:
            if par_x != y:
                par[par_y] = par_x

count = 0
for i in range(N):
    if par[i] == i:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split(" "))
par = [i for i in range(N)]

for i in range(M):
    x, y, z = map(int, input().split(" "))
    x -= 1
    y -= 1
    par_x = par[x]
    par_y = par[y]
    if par_x == x and par_y == y:
        par[y] = x
    else:
        if par_x == x and par_y != y:
            if par_y != x:
                par[x] = par_y
        elif par_y == y and par_x != x:
            if par_x != y:
                par[y] = par_x

count = 0
for i in range(N):
    if par[i] == i:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split(" "))
par = [i for i in range(N)]

for i in range(M):
    x, y, z = map(int, input().split(" "))
    x -= 1
    y -= 1
    par_x = par[x]
    par_y = par[y]
    if par_x == x and par_y == y:
        par[y] = x
    else:
        if par_x == x and par_y != y:
            par[x] = par_y
        elif par_y == y and par_x != x:
            par[y] = par_x

count = 0
for i in range(N):
    if par[i] == i:
        count += 1
        
print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np
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())
uf = UnionFind(N)
for i in range(M):
    ui, vi, wi = map(int, input().split())
    uf.union(ui, vi)
print(len(np.unique(uf.par[1:])))

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 = []
num_of_uniq_num = 0
for e in s[1:]:
    X, Y, Z = map(int, e.split())
    x_index = -1
    y_index = -1
    for i, ls in enumerate(look_set_list):
        if X in ls:
            x_index = i
        if Y in ls:
            y_index = i
        if x_index != -1 or y_index != -1:
            break
    if x_index == -1:
        num_of_uniq_num += 1
        if y_index == -1:
            num_of_uniq_num += 1
            look_set_list.append(set([X, Y]))
        else:
            look_set_list[y_index].add(X)
    else:
        if y_index == -1:
            num_of_uniq_num += 1
            look_set_list[y_index].add(Y)
        else:
            if x_index == y_index:
                continue
            else:
                y_set = look_set_list.pop(y_index)
                look_set_list[x_index].union(y_set)

O = N - num_of_uniq_num + len(look_set_list)
print(O)
print(num_of_uniq_num)
print(look_set_list)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)


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


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

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

used = set()

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)

uf = {root(n) for n in used}

ans = (len(uf) + 1) // 2 + (N - len(used))
print(ans)

Submission status: Wrong Answer

Solution code:
def e_one_or_two(N, M, Info):
    class UnionFind(object):
        def __init__(self, n):
            self.p = list(range(n))  # i番の頂点の親(parent)はi番とする
            self.rank = [0] * n  # 全頂点はランク0(繋がりなし)とする
            self.size = [1] * n  # 全頂点の連結成分の大きさ1とする

        def union(self, x, y):  # x, yを同じ連結成分に属させる
            u, v = self.find(x), self.find(y)
            if u == v:  # x, yは既に同じ連結成分に属していた
                return
            if self.rank[u] < self.rank[v]:
                self.p[u] = v  # ランクの大きな方につなげる
                self.size[v] += self.size[u]  # つながっている要素数だけ足す
                self.size[u] = 0  # ランクが小さかった連結成分は「解散」
            else:  # 上と同様にやる
                self.p[v] = u
                self.size[u] += self.size[v]
                self.size[v] = 0
                if self.rank[u] == self.rank[v]:
                    self.rank[u] += 1  # 根の分だけ1個「ずれる」
            # 経路圧縮を行い、連結成分の代表を更新
            self.find(x)
            self.find(y)
            return None

        def find(self, x):  # 頂点xが属する連結成分の代表(根の番号)を求める
            if self.p[x] != x:  # 頂点xの代表は他の頂点だった
                self.p[x] = self.find(self.p[x])  # 経路圧縮(xを代表につなぐ)
            return self.p[x]

        def num_connected(self):
            return len(set(self.p))

    uf = UnionFind(N)
    for x, y, z in Info:
        uf.union(x - 1, y - 1)
    return uf.num_connected()

N, M = [int(i) for i in input().split()]
Info = [[int(i) for i in input().split()] for j in range(M)]
print(e_one_or_two(N, M, Info))

Submission status: Wrong Answer

Solution code:
def ketu(x, y):
    gx = get_g(x)
    gy = get_g(y)
    if dep[gy] > dep[gx]:
        gx, gy = gy, gx
    if dep[gy] == dep[gx]:
        dep[gx] += 1
    oya[gy] = gx

def get_g(x):
    oyax = oya[x]
    if oyax == x:
        return x
    re = oya[x] = get_g(oyax)
    return re

n, m = map(int, input().split())
oya = [i for i in range(n + 1)]
dep = [1] * (n + 1)
for _ in range(m):
    x, y, z = map(int, input().split())
    ketu(x,y)
print(len(set(oya[1:])))

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x):
	return " ".join(map(str,x))

import collections
import itertools
import operator


class UnionFind:
    def __init__(self, x):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)
        self.size = collections.defaultdict(lambda: 1)
        if x is not None:
            for elem in range(x+1):
                _, _, _ = self.parent[elem], self.rank[elem],self.size[elem]

    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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if not self.are_same(x,y):
            xx = self.size[x]
            yy = self.size[y]
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += xx
            else:
                self.parent[y] = x
                self.size[x] += yy
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

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

    def are_same(self, x, y):
        '''print(x,y,self.find(x),self.find(y),self.find(x) == self.find(y))'''
        return self.find(x) == self.find(y)

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield [x for x, _ in group]

n,g = m()

u = UnionFind(n-1)
co = 0
for i in range(g):
	z,x,v = m()
	u.unite(z-1,x-1)
	co += 1

k = list(u.grouper())

print(co + len(k)-1)