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:
# E問題
# X_i,Y_iで触れられていない数については魔法を使う必要がある.
# X_i、Y_iのペアのウチ、片方が分かればもう片方の偶奇も決定する.
# つまりグラフが何個に分割されているかが分かれば良い
n, m = map(int, input().split())
graph = []
presence = {} # graph配列の何番目にその数が現れるか
for i in range(m):
    x, y, z = map(int, input().split())
    if(x in presence and y in presence):
        # 何もしないでいい
        1
    elif((x not in presence) and (y not in presence)):
        # どちらも初出.
            graph.append([x,y])
            presence[x] = len(graph) - 1
            presence[y] = len(graph) - 1
    else:
        if(y not in presence):
            graph[presence[x]].append(y)
            presence[y] = presence[x]
        else:
            graph[presence[y]].append(x)
            presence[x] = presence[y]
            break
print(len(graph) + n - len(presence))

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
l = []
c = 0
for _ in range(m):
  x,y,z = map(int,input().split())
  if ((x in l) or (y in l)):
    if x not in l:
      l.append(x)
    if y not in l:
      l.append(y)
  else:
    c += 1
    l.append(x)
    l.append(y)
c += n-len(l)
print(c)

Submission status: Wrong Answer

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

import numpy as np
#import scipy, scipy.special

# Python 3 modules: https://docs.python.org/3/library/

import sys
import math, itertools, operator
from math import *
from math import factorial as fact
from itertools import permutations, combinations
from functools import reduce
# Use scipy for stats: https://docs.scipy.org/doc/scipy/reference/stats.html
# Before Python 3.5
from fractions import gcd

inf = float('inf')

def lcm(a, b):
    return a * b // gcd(a,b)

def perm(a, b):
    import scipy.special
    return scipy.special.perm(a, b, exact = True)

def comb(a, b):
    import scipy.special
    return scipy.special.comb(a, b, exact = True)

def dfact(n):
    import scipy.special
    return scipy.special.factorial2(n, exact = True)

def prod(l):
    return reduce(operator.mul, l)

def input_ints(inp = input, sep = ' ', conv = int):
    return map(conv, inp().split(sep = sep))

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

sys.setrecursionlimit(20000)

N, M = input_ints()

# D[i][j]: Card i has a rel. with card j
D = [[] for i in range(N)]
for i in range(M):
    x, y, z = input_ints()
    x -= 1
    y -= 1
    D[x].append(y)
# Lengths
L = [len(x) for x in D]
Lvalid = N - L.count(0)
Ldone = 0
known = [False for i in range(N)]
done = 0
cost = 0

def magic(n):
    global done, known, L, D, Ldone
    for idx in D[n]:
        if not known[idx]:
            known[idx] = True
            done += 1
            L[idx] = -1
            Ldone += 1
            magic(idx)

#print(L)
#print(list(reversed(np.argsort(L))))
while done < N:
    n = np.argmax(L)
    done += 1
    Ldone += 1
    #if Ldone == Lvalid:
    if L[n] == 0:
        cost += N - Lvalid - 1
        break
    L[n] = -1
    cost += 1
    known[n] = 1
    magic(n)

print(cost)

Submission status: Wrong Answer

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

info_lst = []
constrain = M
for i in range(M):
  if (X[i][0] in info_lst) and (X[i][1] in info_lst):
    constrain -= 1
  else:
    if (X[i][0] not in info_lst):
      info_lst.append(X[i][0])
    if (X[i][1] not in info_lst):
      info_lst.append(X[i][1])
      
ans = N - constrain
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
box = []
for i in range(m):
    li = list(map(int, input().split()))
    for j in range(len(box)):
        if li[0] in box[j] or li[1] in box[j]:
            if not li[0] in box[j]:
                box[j].append(li[0])
            if not li[1] in box[j]:
                box[j].append(li[1])
            break
    else:
        box.append([li[0], li[1]])

count = 0
for i in box:
    count += len(i)

result = len(box) + (n - count)
print(result)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

list=input().split(" ")
n=int(list[0])
m=int(list[1])

siki=[]

for i in range(m):
    list=input().split(" ")
    a=int(list[0])
    b=int(list[1])
    siki.append([a,b])

#print(siki)
#siki.sort(key=itemgetter(1))
#print(siki)

katamari=[]
katamari.append(siki[0])
dekai=siki[0][1]
nanko=2

siki=siki[1:]

for sk in siki:
    aswitch=0
    bswitch=0
    #print(katamari)
    ais=0
    bis=0
    for kt in katamari:
        if sk[0] in kt:
            aswitch=1
            break
        else:
            ais+=1
    for kt in katamari:
        if sk[1] in kt:
            bswitch=1
            break
        else:
            bis+=1
    if aswitch==0:
        if bswitch==0:
            katamari.append(sk)
            nanko+=2
        else:
            katamari[bis].append(sk[0])
            nanko+=1
    else:
        if bswitch==0:
            katamari[ais].append(sk[1])
            nanko+=1
        else:
            pass

#print(katamari)
#print(n-nanko)
print(len(katamari)+n-nanko)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
d={i:[] for i in range(n)}
for i in range(m):
    x,y,z=map(int,input().split())
    d[x-1].append(y-1)
cnt=0
c=set()
for i in range(n):
    if i in c:
        continue
    c.add(i)
    q=[i]
    while(q):
        p=q.pop(0)
        l=d[p]
        for x in l:
            if x in c:
                continue
            q.append(x)
            c.add(x)
    cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
S,E=set(),set()
count=0
for i in range(m):
  x,y,z=map(int,input().split())
  if x in S and y in E:
    continue
  else:
    count+=1
    S.add(x)
    E.add(y)
print(n-count)

Submission status: Wrong Answer

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

# Union-Find
parent = [i for i in range(N*2)]
rank = [1] * (N*2)
def get_root(node):
  global parent
  if parent[node] == node:
    return node
  root = get_root(parent[node])
  parent[node] = root
  return root

def is_group(a, b):
  return get_root(a) == get_root(b)

def union(a, b):
  global rank
  root_a = get_root(a)
  rank_a = rank[root_a]
  root_b = get_root(b)
  rank_b = rank[root_b]
  if rank_a < rank_b:
    parent[root_a] = root_b
  else:
    parent[root_b] = root_a
    if rank_a == rank_b:
      rank[root_a] += 1

for _ in range(M):
  x, y, z = map(int, input().split())
  x -= 1
  y -= 1
  if z % 2:
    # x + y が奇数: 違うグループ
    union(x, y+N)
    union(x+N, y)
  else:
    # x + y が偶数: 同じグループ
    union(x,y)
    union(x+N, y+N)

# グループ数 / 2 が答え
print(len(set(parent)) // 2)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
info=[0]*n
mp=0
for i in range(m):
  x,y,z=list(map(int,input().split()))
  if info[x-1]==0 and info[y-1]==0:
    mp+=1
    info[x-1]=1
    info[y-1]=1
  elif info[x-1]==0:
    info[x-1]==1
  elif info[y-1]==0:
    info[y-1]==1
print(mp+n-sum(info))

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

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

    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    
n,m=map(int, input().split())
uf1=UnionFind(n)
for i in range(m):
    a,b,c=map(int, input().split())
    uf1.union(a-1,b-1)
print(len(set(uf1.par)))

Submission status: Wrong Answer

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

graph = {}
for i in range(1, n+1):
	graph[i] = []

for i in range(m):
	u, v, w = map(int, input().strip().split())
	graph[u].append(v)

visited = [False]*(n+1)
def dfs(node):
	# if already visited, backtrack
	if visited[node]:
		return
	# else visit current and then recur on other nodes
	visited[node] = True
	for other in graph[node]:
		dfs(other)

def connectedComponents(graph, n):
	components = 0
	for i in range(1, n+1):
		if not visited[i]:
			components += 1
			dfs(i)
	return components

print(connectedComponents(graph, n))

Submission status: Wrong Answer

Solution code:
# segtree

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

parent = list(range(N + 1))

for _ in range(M):
    x, y, _ = map(int, input().split())
    x_list = [x]
    parent[x] = y
    while x != parent[x]:
        x = parent[x]
        x_list.append(x)
    for a in x_list:
        parent[a] = x

for i in range(N + 1):
    x = i
    x_list = [i]
    while x != parent[x]:
        x = parent[x]
        x_list.append(x)
    for a in x_list:
        parent[a] = x

res = [0] * (N + 1)
res_c = 0
for i in range(1, N + 1):
    j = parent[i]
    if res[j] == 0:
        res_c += 1
    res[j] += 1

print(N - (sum(res) - res_c))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
 
n,m = map(int,input().split())
 
#Union Find
par = [] #親
rank = [] #木の深さ
 
#初期化
for i in range(n):
    #par[i]:i rank[i]:0
    par.append(i)
    rank.append(0)
 
#木の根を求める
def find(x,par):
    if par[x] == x:
        return x
    else:
        return find(par[x],par)
 
#xとyの属する集合の併合
def unite(x,y,par,rank):
    x = find(x,par)
    y = find(y,par)
    
    if x != y:
        #xとyの属している集合が異なる時
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x]==rank[y]:
                rank[x] += 1
 
#xとyが同じ集合に属するかの判定
def same(x,y,par):
    return find(x,par) == find(y,par)
 
for i in range(m):
    X,Y,Z = map(int,input().split())
    unite(X-1,Y-1,par,rank)
 
print(len(set(par)))

Submission status: Wrong Answer

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

ss = []
for _ in range(k):
    x,y,z = list(map(int, input().split()))
    f = False
    if not len(ss):
        ss.append({x,y})
    for s in ss:
        if x in s or y in s:
            s.add(x)
            s.add(y)
            f = True
            continue
    if not f:
        ss.append({x,y})
ans = 0
for i in range(1,n+1):
    f = True
    for s in ss:
        if i in s:
            f = False
            continue
    if f:
        ans += 1
print(ans+len(ss))

Submission status: Wrong Answer

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

info_list =[]

for i in range(M):
    info_list.append(list(map(int, input().split())))
    
a = [info[0] for info in info_list]
b = [info[1] for info in info_list]

print(N - max(len(set(a)), len(set(b))))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
R = [i for i in range(N)]
def root(x):
  if R[x] == x:
    return x
  else:
    R[x] = root(R[x])
    return R[x]
def union(x, y):
  rx = root(x)
  ry = root(y)
  if rx < ry:
    R[ry] = rx
  else:
    R[rx] = ry
for i in range(M):
  x, y, z = map(int, input().split())
  union(x - 1, y - 1)
print(len(set(R)))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
cnt = 0
list = [False for _ in range(n)]
for _ in range(m):
  x, y, z = map(int, input().split())
  if not(list[x-1]) and not(list[y-1]):
    cnt += 1
  list[x-1] = True
  list[y-1] = True
  
for i in range(n):
  if not(list[i]):
    cnt += 1
  
print(cnt)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=[0]*n
b=0
for i in range(m):
    x,y,z=map(int,input().split())
    xi=l[x-1]
    yi=l[y-1]
    if xi==yi==0:l[x-1],l[y-1]=i+1,i+1
    elif xi==0:l[x-1]=yi
    elif yi==0:l[y-1]=xi
    elif xi==yi:pass
    else:b+=1
ans=l.count(0)
ls=len(set(l))
ans+=ls-1 if ans>0 else ls
ans-=b
print(ans)

Submission status: Wrong Answer

Solution code:
class Unionfind():
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        while(self.table[x] >= 0):
            x = self.table[x]
        return x

    def union(self, x, y):
        xp = self.find(x)
        yp = self.find(y)
        if xp != yp:
            if self.table[xp] <= self.table[yp]:
                self.table[yp] = xp
                self.table[xp] += self.table[yp]
            else:
                self.table[xp] = yp
                self.table[yp] += self.table[xp]

n, m = map(int, input().split())
clue = Unionfind(n)
for _ in range(m):
    x, y, _ = map(int, input().split())
    clue.union(x-1, y-1)
roots = set()
for i in range(n):
    roots.add(clue.find(i))
print(len(roots))

Submission status: Wrong Answer

Solution code:
n,m=map(int, input().split())
t=[0]*n
ans=n
for i in range(m):
    a,b,c=map(int, input().split())
    if t[a-1]!=1 or t[b-1]!=1:
        ans-=1
    t[a-1]=1
    t[b-1]=1
print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self,N):
        self.par=[i for i in range(N+1)]
        self.rank=[0 for _ in range(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 same_check(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

n,m=map(int,input().split())
uf=UnionFind(n)
#print(uf.par,uf.rank)
for i in range(m):
    x,y,z=map(int,input().split())
    uf.union(x,y)
print(len(set(uf.par))-1)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

mi = lambda: map(int, input().split())

N, M = mi()
check_cards = []
check = 0

for _ in range(M):
  X, Y, _ = mi()
  if X not in check_cards and Y not in check_cards:
    check += 1
  check_cards += [X,Y]
  
print(check + N - len(set(check_cards)))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
 
 
class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n)]
        self.sizes = [1] * n
        self.rank = [0] * n
    def find(self, i):
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.find(self.parents[i])
            return self.parents[i]
    def unite(self, i, j):
        pi = self.find(i)
        pj = self.find(j)
        if pi != pj:
            if self.rank[pi] < self.rank[pj]:
                self.sizes[pj] += self.sizes[pi]
                self.parents[pi] = pj 
            else: 
                self.sizes[pi] += self.sizes[pj]
                self.parents[pj] = pi 
                if self.rank[pi] == self.rank[pj]:
                    self.rank[pi] += 1
        
uf = UnionFind(N)
for m in range(M):
    a,b,c = map(int, input().split())
    uf.unite(a-1, b-1)
print (len(set(uf.parents)))

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

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

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

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

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

n,m = getList()
uf = UnionFind(n)
for i in range(m):
    x, y, _ = getList()
    if not uf.same_check(x,y):
        uf.union(x,y)

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

Submission status: Wrong Answer

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

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

sets = list()
for i in range(M):
    x, y, z = list(map(int, input().split()))
    flag = True
    for s in sets:
        if x in s or y in s:
            s |= {x, y}
            flag = False
    else:
        if flag:
            sets.append({x, y})

# merge
merged = []
for s in sets:
    for m in merged:
        if len(m & s) > 0:
            m |= s
            break
    else:
        merged.append(s)

# calc len
num = sum([len(m) - 1 for m in merged])
total = sum([len(m) for m in merged])
print((total-num) + N-total)

Submission status: Wrong Answer

Solution code:
import sys, math, collections, heapq, itertools
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0: a, b = b, a % b
    return b

def find(a, L):
    if L[a] == a: return a
    else: 
        L[a] = find(L[a], L)
        return L[a]

def unite(a, b, L, R):
    a = find(a, L)
    b = find(b, L)
    if a == b: return
    if R[a] < R[b]:
        L[a] = b
    else:
        L[b] = a
        if R[a] == R[b]: R[a] += 1
    
  
def solve():
    N, M = map(int, line_input())
    parent = [int(i) for i in range(N)]
    rank = [0] * N
    decided = [False] * N
    for i in range(M):
        x, y, z = map(int, line_input())
        unite(x-1, y-1, parent, rank)
        if z == 2: decided[x] = True
    for i in range(N):
        if decided[i]: parent[i] = True

    parent = set(parent)
    cost = 0
    for key in parent:
        if not decided[key]: cost += 1
    print(cost)
    
    return 0
  
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
def find(x):
    if root[x] == x:
        return x
    else:
        return find(root[x])

def unite(x,y):
    x = find(x)
    y = find(y)
    if x != y:
        if rank[x] < rank[y]:
            root[x] = y
        else:
            root[y] = x
            if rank[x]==rank[y]:
                rank[x] += 1

n,m = map(int,input().split())
root = [0]*n
for i in range(n):
    root[i] = i
rank = [1]*n
size = [1]*n
for i in range(m):
    x,y,z = [int(i)-1 for i in input().split()]
    unite(x,y)
res = set()
for r in root:
    if r not in res:
        res.add(r)
print(len(res))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
  n, m = map(int, input().split())
  c = set()

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

    if x not in c or y not in c:
      c.add(x)
      c.add(y)
      n -= 1

  print(n)


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

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

reader = [i for i in range(n)]
count = [1 for i in range(n)]

for xy in xyz:
    if reader[xy[0]-1] != reader[xy[1]-1]:
        a = max(xy[0],xy[1])-1
        b = min(xy[0],xy[1])-1
        reader[b] = reader[a]
        count[a] += count[b]
        count[b] = 0
print(n-count.count(0))

Submission status: Wrong Answer

Solution code:
import sys
import math
def input(): return sys.stdin.readline().strip()

mi = lambda: map(int, input().split())

N, M = mi()
cards = [i for i in range(1, N+1)]
check = 0

for _ in range(M):
  X, Y, _ = mi()
  if X in cards and Y in cards:
    check += 1
  if X in cards:
    cards.remove(X)
  if Y in cards:
    cards.remove(Y)
  
print(check + len(cards))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

def Find(x):    #xの根を返す
    global table

    if table[x] == x:
        return x
    else:
        table[x] = Find(table[x])    #親の更新(根を直接親にして参照距離を短く)
        size[x] = size[table[x]]
        return table[x]

def Unite(x,y):    #xとyを繋げる
    global size
    global rank
    x = Find(x)
    y = Find(y)
    sx = Size(x)
    sy = Size(y)

    if x == y:
        return

    if rank[x] > rank[y]:
        table[y] = x
        size[x] = sx + sy
    else:
        table[x] = y
        size[y] = sx + sy
        if rank[x] == rank[y]:
            rank[y] += 1

def Check(x,y):
    if Find(x) == Find(y):
        return True
    else:
        return False

def Size(x):
    return size[Find(x)]

N,M = inpl()

table = [i for i in range(N)]    #木の親 table[x] == x なら根
rank  = [1 for i in range(N)]    #木の長さ
size  = [1 for i in range(N)]    #集合のサイズ

for i in range(M):
    x,y,z = inpl()
    x -= 1
    y -= 1
    if not Check(x,y):
        Unite(x,y)

#print(table)

print(len(set(table)))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


class UnionFind(object):
    """重み付きUnionFind木
    """

    def __init__(self, N, unity=0):
        self.tree = list(range(N))
        self.rank = [0] * N
        self.diff_weight = [unity]*N

    def root(self, i):
        if self.tree[i] == i:
            return i
        else:
            r = self.root(self.tree[i])
            self.diff_weight[i] += self.diff_weight[self.tree[i]]
            self.tree[i] = r
            return r

    def weight(self, i):
        self.root(i)
        return self.diff_weight[i]

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

    def unite(self, x, y, w):
        w += self.weight(x)
        w -= self.weight(y)
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.rank[x] < self.rank[y]:
            x, y = y, x
            w = -w
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.tree[y] = x
        self.diff_weight[y] = w
        return True

    def diff(self, x, y):
        return self.weight(x) - self.weight(y)


def solve(N: int, M: int, X: "List[int]", Y: "List[int]", Z: "List[int]"):
    uf = UnionFind(N)
    for x, y, z in zip(X, Y, Z):
        uf.unite(x-1, y-1, z)

    print(len(set(uf.tree)))

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    X = [int()] * (M)  # type: "List[int]"
    Y = [int()] * (M)  # type: "List[int]"
    Z = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        X[i] = int(next(tokens))
        Y[i] = int(next(tokens))
        Z[i] = int(next(tokens))
    solve(N, M, X, Y, Z)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# E問題
# X_i,Y_iで触れられていない数については魔法を使う必要がある.
# X_i、Y_iのペアのウチ、片方が分かればもう片方の偶奇も決定する.
# つまりグラフが何個に分割されているかが分かれば良い
n, m = map(int, input().split())
graph = []
presence = {}
for i in range(m):
    x, y, z = map(int, input().split())
    presence[x] = 1
    presence[y] = 1
    for j in graph:
        if(x in j or y in j):
            j.append(x)
            j.append(y)
            break
    else:
        graph.append([x,y])
print(len(graph) + n - len(presence))

Submission status: Wrong Answer

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

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

  def unite(self,x,y):
    s1=self.find(x)
    s2=self.find(y)
    if s1==s2:
      pass
    else:
      if self.rank[s1]>self.rank[s2]:
        self.Tree[s2]=s1
      elif self.rank[s1]<self.rank[s2]:
        self.Tree[s1]=s2
      else:
        self.Tree[s2]=s1
        self.rank[s1]+=1

N,M=map(int,input().split())        
uf=Unionfind(N)        
for i in range(M):
  x,y,w=map(int,input().split())
  uf.unite(x-1,y-1)
used=[False]*N
ans=0
for i in range(N):
  if not used[uf.Tree[i]]:
    ans+=1
  used[uf.Tree[i]]=True
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math 
import numpy as np
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()
N,K=na()
n=N
k=10**9
cnt=0

while(N<K):
    #print(N,K)
    K=math.ceil(K/2)
    cnt+=1
k=K

ans=0
first=True
while(True):
    if(first):
        ans+=(N-k+1)*(0.5**cnt)
        first=False
    else:
        ans+=(N-k)*(0.5**cnt)

    #print("ddd",(N-k+1)*(0.5**cnt),"N",N,"k",k,"n-k+1",N-k+1,"cnt",cnt)
    #print("ans",ans)
    cnt+=1
    N=k
    k=math.ceil(k/2)
    #print("k",k)
    if(k==1):
        ans+=1*(0.5**cnt)
        #print("ddd",1*(0.5**cnt))
        #print("cnt",cnt)
        break
#print(ans,n)
ans=ans/n
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


class UnionFind:
    def __init__(self, node: int) -> None:
        self.n = node
        self.par = [i for i in range(self.n)]
        self.rank = [0 for i in range(self.n)]

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

    def unite(self, x: int, y: int) -> bool:
        if self.isSame(x, y):
            # print("x and y has already united")
            return False

        rx = self.find(x)
        ry = self.find(y)

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

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

        return True

    def isSame(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)


n,m = li()
uf = UnionFind(n)
for _ in range(m):
    x,y,z = li()
    x -= 1
    y -= 1
    uf.unite(x,y)

pars = set()
for i in range(n):
    pars.add(uf.par[i])

print(len(pars))

Submission status: Wrong Answer

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

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

#Union Find
par = [] #親
rank = [] #木の深さ

#初期化
for i in range(n):
    #par[i]:i rank[i]:0
    par.append(i)
    rank.append(0)

#木の根を求める
def find(x,par):
    if par[x] == x:
        return x
    else:
        return find(par[x],par)

#xとyの属する集合の併合
def unite(x,y,par,rank):
    x = find(x,par)
    y = find(y,par)
    
    if x != y:
        #xとyの属している集合が異なる時
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x]==rank[y]:
                rank[x] += 1

#xとyが同じ集合に属するかの判定
def same(x,y,par):
    return find(x,par) == find(y,par)

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

print(len(set(par)))

Submission status: Wrong Answer

Solution code:
import sys, math, collections, heapq, itertools
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0: a, b = b, a % b
    return b

def find(a, L):
    if L[a] == a: return a
    else: 
        L[a] = find(L[a], L)
        return L[a]

def unite(a, b, L, R):
    a = find(a, L)
    b = find(b, L)
    if a == b: return
    if R[a] < R[b]:
        L[a] = b
    else:
        L[b] = a
        if R[a] == R[b]: R[a] += 1
    
  
def solve():
    N, M = map(int, line_input())
    parent = [int(i) for i in range(N)]
    rank = [0] * N
    for i in range(M):
        x, y, z = map(int, line_input())
        unite(x-1, y-1, parent, rank)
    print(len(set(parent)))
    
    return 0
  
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
# union-findかな
# 蟻本によればunion-findは分割できないっぽいので、ちょっと違う? 
# 時刻を巻き戻して、橋なしから橋を建設することにすれば扱える

# 橋が崩落してA+B　がAとBに分かれたら、不便度はA*B増加する

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

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

def unite(x, y):
	x = find_root(x)
	y = find_root(y)
	if(x == y):
		return 0

	if rank[x] < rank[y]:
		par[x] = y

		temp = size[x] * size[y]
		size[y] = size[x] + size[y]
	else:
		par[y] = x
		if (rank[x] == rank[y]):
			rank[x] += 11

		temp = size[x] * size[y]
		size[x] = size[x] + size[y]
	return temp

def is_same(x,y):
	return find_root(x) == find_root(y)

# par = [0]*n
par = list(range(n))
rank = [0]*n
size = [1]*n

edges = [list(map(int, input().split()))[0:2] for _ in range(m)]
edges = [[b[0]-1, b[1]-1] for b in edges] #1-idx -> 0-idx

for b in range(m):
	unite(edges[b][0] , edges[b][1])

# print(par)
print(len(set(par)))

Submission status: Wrong Answer

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


parent = [i for i in range(N)]
rank = [0] * N


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


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


def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return

    if rank[x] > rank[y]:
        parent[y] = x
    else:
        parent[x] = y
        if rank[x] == rank[y]:
            rank[y] += 1


for i in range(M):
    X, Y, Z = map(int, input().split())
    X, Y = X - 1, Y - 1
    if not same(X, Y):
        unite(X, Y)

D = {}
num = 0
for i in range(N):
    if parent[i] not in D:
        D[parent[i]] = 1
        num += 1

print(num)