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

union = UnionFind(n)

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

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

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

union = UnionFind(n)

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

key = union.par
already = [False]*n

ans = 0
for i in range(1, n+1):
  k = key[i]
  if already[k-1]:
    continue
  ans += 1
  already[k-1] = True
print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n=0):
        self.d = [-1]*n
        self.u = n

    def root(self, x):
        if self.d[x] < 0:
            return x
        self.d[x] = self.root(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x == y:
            return False

        if self.d[x] == -1 or self.d[y] == -1:
            self.u -= 1

        if x > y:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x

        return True

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

    def size(self, x):
        return -self.d[self.root(x)]

    def num_union(self):
        return self.u


N, M, *X = map(int, open(0).read().split())
X = tuple(zip(*[iter(X)]*3))

uf = UnionFind(N)
for x, y, z in X:
    uf.unite(x-1, y-1)

print(uf.num_union())

Submission status: Wrong Answer

Solution code:
def find(x):
    if x == par[x]:
        return x
    par[x] = find(par[x])
    return par[x]
 
def union(x,y):
    x,y = find(x),find(y)
    if x == y:
        return
    par[y] = x
 
n,m = map(int,input().split())
par = {i:i for i in range(1,n+1)}
for _ in range(m):
    a,b,c = map(int,input().split())
    union(a,b)
print(len(set(par.values())))

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
As = [True]*N
for i in range(M):
  x,y,z = map(int, input().split())
  As[y-1] = False
print(sum(As))

Submission status: Wrong Answer

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

parent = list(range(N))

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

def unite(src, dst):
    r_src = find(src)
    r_dst = find(dst)
    if r_src != r_dst:
        parent[src] = r_dst
        unite(parent[src], r_dst)
    
for i, (Xi, Yi, Zi) in enumerate(XYZ):
    unite(Xi - 1, Yi - 1)

# cnt = {}
# for i in range(N):
#     key = str(find(i))
#     cnt[key] = cnt.setdefault(key, 0) + 1

# # print("#", parent, cnt)
# print(len(cnt.keys()))

# print("#", [find(i) for i in range(N)])
ans = len(set([find(i) for i in range(N)]))
print(ans)

Submission status: Wrong Answer

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

parent = list(range(N))

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

for i, (Xi, Yi, Zi) in enumerate(XYZ):
    dst = find(Xi - 1)
    parent[Xi - 1] = dst
    parent[Yi - 1] = dst

cnt = {}
for i in range(N):
    key = str(find(i))
    cnt[key] = cnt.setdefault(key, 0) + 1

# print("#", parent, cnt)
print(len(cnt.keys()))

Submission status: Wrong Answer

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

parent = list(range(N))

for i, (Xi, Yi, Zi) in enumerate(XYZ):
    dst = min(Xi - 1, Yi - 1)
    src = max(Xi - 1, Yi - 1)
    parent[dst] = src

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

cnt = {}
for i in range(N):
    key = str(find(i))
    cnt[key] = cnt.setdefault(key, 0) + 1

# print("#", parent, cnt)
print(len(cnt.keys()))

Submission status: Wrong Answer

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

parent = list(range(N))

for i, (Xi, Yi, Zi) in enumerate(XYZ):
    parent[Xi - 1] = Yi - 1

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

cnt = {}
for i in range(N):
    key = str(find(i))
    cnt[key] = cnt.setdefault(key, 0) + 1

# print("#", parent, cnt)
print(len(cnt.keys()))

Submission status: Wrong Answer

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

group = list(range(N))

for i, (Xi, Yi, Zi) in enumerate(XYZ):
    unite = min(group[Xi - 1], group[Yi - 1])
    group[Xi - 1] = unite
    group[Yi - 1] = unite

def easyfind(arg):
    if group[arg] == arg:
        return arg
    else:
        return easyfind(group[arg])

cnt = {}
for i in range(N):
    cnt[str(group[i])] = cnt.setdefault(str(group[i]), 0) + 1

# print("#", group, cnt)
print(len(cnt.keys()))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
b = [[int(i) for i in input().split(" ")] for j in range(m)]
lis = [b[0][:-1]]
for i in range(1, m):
    tm = b[i][:-1]
    flag = 0
    for j in range(len(lis)):
        if tm[0] in lis[j] or tm[1] in lis[j]:
            if not tm[0] in lis[j]:
                lis[j].append(tm[0])
            if not tm[1] in lis[j]:
                lis[j].append(tm[1])
            flag = 1
            break
    if flag == 1:
        lis.append(tm)
c = n - sum([len(k) for k in lis])
print(len(lis) + c)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
merge = [i for i in range(N+1)]
XYZ = [list(map(int,input().split())) for _ in range(M)]
for i in range(M):
    merge[XYZ[i][1]] = merge[XYZ[i][0]]
s = set(merge)

print(len(s)-1)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
merge = [i for i in range(N+1)]
XYZ = sorted([list(map(int,input().split())) for _ in range(M)])
for i in range(M):
    merge[XYZ[i][1]] = merge[XYZ[i][0]]
s = set(merge)

print(len(s)-1)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
UF = [-1] * (N+1)
def find(x):
    global UF
    if UF[x] == -1:
        return x
    else:
        UF[x] = find(UF[x])
        return UF[x]
def union(x,y):
    global UF
    xx = find(x)
    yy = find(y)
    if UF[xx] == UF[yy] == -1:
        UF[y] = xx
    elif xx == yy:
        return 
    else:
        UF[yy] = xx
    
for _ in range(M):
    x, y, z = map(int, input().split())
    union(x,y)
    
print(sum([i < 0 for i in UF[1:]]))

Submission status: Wrong Answer

Solution code:
import sys


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

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if 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 is_same_group(self, x, y):
        return self.find(x) == self.find(y)


N, M = map(int, sys.stdin.readline().split())
uf = UnionFind(N)
for _ in range(M):
    x, y, z = map(int, sys.stdin.readline().split())
    x -= 1
    y -= 1
    uf.unite(x, y)

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

Submission status: Wrong Answer

Solution code:
import sys


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

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if 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 is_same_group(self, x, y):
        return self.find(x) == self.find(y)


N, M = map(int, sys.stdin.readline().split())
uf = UnionFind(N)
for _ in range(M):
    x, y, z = map(int, sys.stdin.readline().split())
    x -= 1
    y -= 1

    if uf.find(x) != uf.find(y):
        uf.unite(x, y)

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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
par = [i for i in range(N)]
rank = [0 for i in range(N)]
def root(x):
  if par[x] == x:
    return x
  else:
    par[x] = root(par[x])
    return par[x]
def unite(x, y):
  x, y = root(x), root(y)
  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-1, Y-1)
D = {}
for i in par:
  D[i] = 1
print(len(D))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
par = [i for i in range(N)]
rank = [0 for i in range(N)]
def root(x):
  if par[x] == x:
    return x
  else:
    par[x] = root(par[x])
    return par[x]
def unite(x, y):
  x, y = root(x), root(y)
  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-1, Y-1)
D = {}
for i in par:
  if i not in D:
    D[i] = 1
print(len(D))

Submission status: Wrong Answer

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

re = [1]*N
ans = [1]*N
for k in range(N):
  ans[k] = k
 
A = 0
 
for i in range(M):
  X, Y, Z = map(int, input().split())
  if ans[X-1] != ans[Y-1]:
    if re[X-1] == 0 :
      ans[Y-1] = ans[X-1]
      re[Y-1] = 0
    elif re[Y-1] == 0:
      ans[X-1] = ans[Y-1]
      re[X-1] = 0
    else:
      ans[X-1] = ans[Y-1]
      re[X-1] = 0
      re[Y-1] = 0


    A = A+1
 
print(N-A)

Submission status: Wrong Answer

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

ans = [1]*N
for k in range(N):
  ans[k] = k+1

A = 0

for i in range(M):
  X, Y, Z = map(int, input().split())
  if ans[X-1] != ans[Y-1]:
    ans[X-1] = ans[Y-1]
    A = A+1

print(N-A)

Submission status: Wrong Answer

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

ans = [1]*N
for i in range(N):
  ans[i] = i

A = 0

for i in range(M):
  X, Y, Z = map(int, input().split())
  if ans[X-1] != ans[Y-1]:
    ans[Y-1] = ans[X-1]
    A = A+1

print(N-A)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
ans = [1]*N
A = 0

for i in range(M):
  X, Y, Z = map(int, input().split())
  if ans[X-1] == 1 or ans[Y-1] == 1:
    ans[X-1] = 0
    ans[Y-1] = 0
    A = A+1

print(N-A)

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n, m = MAP()
arr = [-1 for _ in range(n)]
tmp = [0, 1]
ans = 0
for i in range(m):
    x, y, z = MAP()
    x -= 1
    y -= 1
    if arr[x] == -1 and arr[y] == -1:
        ans += 1
    arr[x] = 1
    arr[y] = 1
ans += arr.count(-1)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n, m = MAP()
arr = [-1 for _ in range(n)]
tmp = [0, 1]
ans = 0
for i in range(m):
    x, y, z = MAP()
    x -= 1
    y -= 1
    if arr[x] == -1 and arr[y] == -1:
        arr[x] = i
        arr[y] = i
        ans += 1
    elif arr[x] == -1:
        arr[x] = arr[y]
    elif arr[y] == -1:
        arr[y] = arr[x]
ans += arr.count(-1)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n, m = MAP()
arr = [-1 for _ in range(n)]
tmp = [0, 1]
proc = []
for i in range(m):
    x, y, z = MAP()
    x -= 1
    y -= 1
    if z % 2 == 0:
        if arr[x] == -1 and arr[y] == -1:
            arr[x] = i
            arr[y] = i
        elif arr[x] == -1:
            arr[x] = arr[y]
        elif arr[y] == -1:
            arr[y] = arr[x]
        elif arr[x] != arr[y]:
            proc.append(arr[y] // 2)
            arr[y] = arr[x]
    else:
        if arr[x] == -1 and arr[y] == -1:
            arr[x] = i
            arr[y] = i
        elif arr[x] == -1:
            arr[x] = arr[y]
        elif arr[y] == -1:
            arr[y] = arr[x]
        elif arr[x] == arr[y]:
            proc.append(arr[y] // 2)
            arr[y] = arr[x]
ans = len(set(arr))
if -1 in arr:
    ans -= 1
ans += arr.count(-1)
ans -= len(proc)
print(ans)

Submission status: Wrong Answer

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

    def root(self, x):
        if x != self.par[x]:
            self.par[x] = self.root(self.par[x])
        return self.par[x]

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

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return

        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = ry
        else:
            self.par[ry] = rx
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    def update_p(self):
        for x in range(self.n):
            self.root(x)

    def get_size(self, x):
        return self.size[self.find_set(x)]




def main():
    n, m = [int(i) for i in input().split()]
    uf = UnionFind(n)
    for _ in range(m):
        x, y, _ = [int(i) for i in input().split()]
        uf.unite(x-1, y-1)
    print(len(set(uf.par)))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main():
    N,M = map(int, readline().split())
    m = map(int, read().split())
    xyz = zip(m, m, m)

    graph = [[] for _ in range(N + 1)]
    for x, y, _ in xyz:
        graph[y].append(x)
        graph[x].append(y)

    cnt = 0
    flg = [0] * (N + 1)
    for i in range(1,N+1):
        if flg[i] == 0:
            cnt += 1
            flg[i] = 1
        if graph[i] is False:
            continue
        for y in graph[i]:
            flg[y] = 1

    print(cnt)
    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

for i in range(m):
    count_list.append(list(map(int,input().split())))

number_set = set()

check_list = [0 for i in range(n)]

for i in range(m):
    if count_list[i][0] in number_set:
        check_list[count_list[i][0] - 1] = 1
    if count_list[i][1] in number_set:
        check_list[count_list[i][1]- 1] = 1

    number_set.add(count_list[i][0])
    number_set.add(count_list[i][1])

"""if count_list[m-1][0] in number_set:
    check_list[count_list[m-1][0] - 1] = 1
if count_list[m-1][1] in number_set:
    check_list[count_list[m-1][1] - 1] = 1
"""
#print(number_set)
#print(check_list)

no_exist = n - len(number_set)
#print(no_exist)
count = 0
#print(check_list)
for j in check_list:
    if j == 1:
        count += 1
#print(count)
one_count = n - count - no_exist
#one_count = n - len([n for n in check_list if 1])
#print(one_count)


if no_exist:
    ans = one_count/2
    ans += no_exist
else:
    ans = one_count
print(int(ans))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
# coding: utf-8
import sys
sys.setrecursionlimit(10000000)

#const
# my functions here!
def pin(type=int):
    return map(type,input().rstrip().split())

class UFTforest():
    def __init__(self,N):
        self.parent=[i for i in range(N)]#1-index
    
    def rooting(self,x):
        if self.parent[x]==x:return x
        else:
            self.parent[x]=self.rooting(self.parent[x])
            return self.parent[x]
    
    def find(self,i,j):
        print(["No","Yes"][self.rooting(i)==self.rooting(j)])
    
    def union(self,i,j):
        i,j=self.rooting(i),self.rooting(j)
        if i!=j:self.parent[i]=j 
        
def resolve():
    global N
    N,Q=pin()
    
    A=UFTforest(N+1)
    for i in range(Q):
        x,y,z=pin()
        A.union(x,y)
    #print(A.parent)
    for j in A.parent:
        if not(A.parent[j]==j):
            A.rooting(j-1)
    from collections import Counter as c
    print(len(c(A.parent[1:])))
        
    
"""         
#printデバッグ消した？
#前の問題の結果見てないのに次の問題に行くの？
"""
"""
お前カッコ閉じるの忘れてるだろ
"""



import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 1
1 2 1"""
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """6 5
1 2 1
2 3 2
1 3 3
4 5 4
5 6 5"""
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """100000 1
1 100000 100"""
        output = """99999"""
        self.assertIO(input, output)

if __name__=="__main__":resolve()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
# coding: utf-8
import sys
sys.setrecursionlimit(10000000)

#const
# my functions here!
def pin(type=int):
    return map(type,input().rstrip().split())

class UFTforest():
    def __init__(self,N):
        self.parent=[i for i in range(N)]#1-index
    
    def rooting(self,x):
        if self.parent[x]==x:return x
        else:
            self.parent[x]=self.rooting(self.parent[x])
            return self.parent[x]
    
    def find(self,i,j):
        print(["No","Yes"][self.rooting(i)==self.rooting(j)])
    
    def union(self,i,j):
        i,j=self.rooting(i),self.rooting(j)
        if i!=j:self.parent[i]=j 
        
def resolve():
    global N
    N,Q=pin()
    
    A=UFTforest(N+1)
    for i in range(Q):
        x,y,z=pin()
        A.union(x,y)
    for j in range(N+1):
        A.rooting(A.parent[j])
    Ap=A.parent[1:]
   # print(Ap)
    from collections import Counter as c
    a=c(Ap)
    print(len(a))
        
    
"""         
#printデバッグ消した？
#前の問題の結果見てないのに次の問題に行くの？
"""
"""
お前カッコ閉じるの忘れてるだろ
"""



import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 1
1 2 1"""
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """6 5
1 2 1
2 3 2
1 3 3
4 5 4
5 6 5"""
        output = """2"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """100000 1
1 100000 100"""
        output = """99999"""
        self.assertIO(input, output)


if __name__=="__main__":resolve()

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
par = [i for i in range(n)]
rank = [0 for i in range(n)]

def find(x, par):
    if x == par[x]:
        return par[x]
    else:
        return find(par[x], par)
def unite(x, y, par, rank):
    x = find(x, par)
    y = find(y, par)
    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-1, y-1, par, rank)

T = list(set(par))
print(len(T))

Submission status: Wrong Answer

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


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

a = [False]*N
ans=0
for i in range(M):
    x,y,z = map(int,input().split())
    if not a[x-1] and not a[y-1]:
        a[x-1]=True
        a[y-1]=True
        ans+=1
    else:
        a[x-1]=True
        a[y-1]=True

for i in range(N):
    if not a[i]:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.p = [e for e in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    def same(self, u, v):
        return self.find_set(u) == self.find_set(v)

    def unite(self, u, v):
        u = self.find_set(u)
        v = self.find_set(v)

        if u == v:
            return

        if self.rank[u] > self.rank[v]:
            self.p[v] = u
            self.size[u] += self.size[v]
        else:
            self.p[u] = v
            self.size[v] += self.size[u]
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1

    def find_set(self, u):
        if u != self.p[u]:
            self.p[u] = self.find_set(self.p[u])

        return self.p[u]

    def update_p(self):
        for u in range(self.n):
            self.find_set(u)

    def get_size(self, u):
        return self.size[self.find_set(u)]


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

uf = UnionFind(n)

for x, y, _ in xyz:
    x -= 1
    y -= 1
    uf.unite(x, y)

#uf.update_p()
ans = len(set(uf.p))
print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
import sys
sys.setrecursionlimit(10**7)
U=[i for i in range(N)]
def root(i):
    if U[i]==i:
        return i
    else:
        U[i]=root(U[i])
        return U[i]
def union(i, j):
    if root(i)==root(j):
        return
    else:
        U[root(i)]=root(j)
        return
for i in range(M):
    X,Y,Z=map(int,input().split())
    union(Y-1,X-1)
a=set()
for u in U:
    a.add(u)
print(len(a))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
U=[i for i in range(N)]
def root(i):
    if U[i]==i:
        return i
    else:
        return root(U[i])
def union(i, j):
    U[i]=root(j)
for i in range(M):
    X,Y,Z=map(int,input().split())
    union(Y-1,X-1)
a=set()
for u in U:
    a.add(u)
print(len(a))

Submission status: Wrong Answer

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

#Union-Find
par=[i for i in range(n)]
size=[1 for _ in range(n)]
rank=[0 for _ in range(n)]
 
def find(x):#木の根を求める
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
    
def merge(x,y):#併合
    x=find(x)
    y=find(y)
    if x==y:
        return
    if same(x,y):
        return
    if rank[x]>rank[y]:
        par[y]=x
        size[x]+=size[y]
    else:
        par[x]=y
        size[y]+=size[x]
        if rank[x]==rank[y]:
            rank[y]+=1
            
def same(x,y):
    return find(x)==find(y)

for _ in range(m):
    x,y,z=map(int,input().split())
    merge(x-1,y-1)
    
print(len(set([par[i] for i in range(n)])))

Submission status: Wrong Answer

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

#Union-Find
par=[i for i in range(n)]
size=[1 for _ in range(n)]
rank=[0 for _ in range(n)]
 
def find(x):#木の根を求める
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
    
def merge(x,y):#併合
    x=find(x)
    y=find(y)
    if x==y:
        return
    if rank[x]>rank[y]:
        par[y]=x
        size[x]+=size[y]
    else:
        par[x]=y
        size[y]+=size[x]
        if rank[x]==rank[y]:
            rank[y]+=1
            
def same(x,y):
    return find(x)==find(y)

for _ in range(m):
    x,y,z=map(int,input().split())
    merge(x-1,y-1)
    
print(len(set([par[i] for i in range(n)])))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
# coding: utf-8
from fractions import gcd 
from functools import reduce
import sys
sys.setrecursionlimit(200000000)
from inspect import currentframe


# my functions here!
#標準エラー出力
def printargs2err(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' : '+repr(arg) for arg in args),file=sys.stderr)
def debug(*args):
    print(*args,file=sys.stderr)

def printglobals():
    for (symbol, value) in globals().items():
        print('symbol="%s"、value=%s' % (symbol, value),file=sys.stderr)
def printlocals():
    for (symbol, value) in locals().items():
        print('symbol="%s"、value=%s' % (symbol, value),file=sys.stderr)
#入力（後でいじる）
def pin(type=int):
    return map(type,input().split())
     
#input
class UnionFindTree():
    def __init__(self,n):
        self.uft=[i for i in range(n+1)]#やっぱり0-indexedが一番だね
    def root (self,a):
        if self.uft[a]==a:
            return a
        else:
            az=self.root(self.uft[a])
            self.uft[a]=az
            return az
    def find(self,a,b):
        return self.root(a)==self.root(b)
    
    def union(self,a,b):
        if not self.find(a,b):
            s,t=min(a,b),max(a,b)
            self.uft[t]=s

class UftWRank(UnionFindTree):
    def __init__(self,n):
        super().__init__(n)
        self.rank=[0]*(n+1)
    def union(self,a,b):
        if not self.find(a,b):
            #rankの小さい方をでかい方のrootにつけるイメージ
            A,B=self.rank[a],self.rank[b]
            if A<B:
                self.uft[b]=a
            else:
                self.uft[a]=b
                if A==B:self.rank[a]+=1
                
def resolve():
    n,q=pin()
    tr=UftWRank(n)#1-indexed rootの場所が書かれてある
    for query in range(q):
        a,b,f=pin()
        tr.union(a,b)
        #printargs2err(tr.uft,tr.rank)
    for vert in range(n+1):
        tr.root(vert)
    debug(tr.uft)
    tr.uft.pop(0)#0-indexだからです
    from collections import Counter
    print(len(Counter(tr.uft)))
    #print([["NA","YYMM"],["MMYY","AMBIGUOUS"]][cMMYY][cYYMM])
#if __name__=="__main__":resolve()

"""
#printデバッグ消した？
#前の問題の結果見てないのに次の問題に行くの？
"""
"""
お前カッコ閉じるの忘れてるだろ
"""
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3 1
1 2 1"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """6 5
4 5 4
1 3 3
1 2 1
2 3 2
5 6 5"""
        output = """2"""
        self.assertIO(input, output)
     
if __name__=="__main__":resolve()