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: Runtime Error

Solution code:
def solve():
    N = int(input())
    uvw = []
    w = []
    result = [-1] * N
    for _ in range(N - 1):
        lst = [int(i) for i in input().split()]
        uvw.append([lst[0] if lst[0] <= lst[1] else lst[1],
                    lst[1] if lst[0] <= lst[1] else lst[0],
                    lst[2]])
    uvw.sort()
    # print(uvw)
    # 木の頂点を求める
    # -> 任意の場所で良い. 1 とする.
    # 頂点から順に塗っていく
    result[0] = False
    result = paint(uvw, 1, result)
    for i in result:
        print(int(i))


def paint(uvw, num, result):
    target_uvw = []
    for t in uvw:
        if t[0] == num or t[1] == num:
            target_uvw.append(t)
            uvw.remove(t)
    next_nums = []
    for t in target_uvw:
        target = t[0] if t[0] != num else t[1]
        result[target - 1] = result[num - 1] if t[2] % 2 == 0 else not(result[num - 1])
        next_nums.append(target)
    # print('探索中の番号:', num)
    # print('ヒットしたデータ', target_uvw)
    # print('現在の結果', result)
    for nn in next_nums:
        result = paint(uvw, nn, result)
    return result


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

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

UF = list(range(N + 1))


def find(x):
    if UF[x] != x:
        UF[x] = find(UF[x])
    return UF[x]


def unite(x, y):
    UF[find(x)] = find(y)


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


for x, y, z in XYZ:
    unite(x, y)
for i in range(1, N + 1):
    find(i)
print(len(set(UF[1:])))

Submission status: Runtime Error

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

a = {}
b = {}
for i in range(M):
  X, Y, Z = [int(i) for i in input().strip().split(' ')]
  if X not in a:
    a[X] = set()
    b[X] = 0
  if Y not in a:
    a[Y] = set()
    b[Y] = 0

  a[X].add(Y)
  b[X] += 1
  a[Y].add(X)
  b[Y] += 1

b = sorted(list(b.items()), key=lambda e: e[1], reverse=True)


def make_keys(keys, key):
  if key in keys:
    return
  keys.add(key)
  for k in a[key]:
    make_keys(keys, k)


counter = 0
# print(b)
for key, v in b:
  if key not in a:
    continue
  keys = set()
  make_keys(keys, key)

  for k in keys:
    if k in a:
      del a[k]

  counter += 1

print(counter + N - len(b))

Submission status: Runtime Error

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


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

    def union(self, i, j):
        i = self.root(i)
        j = self.root(j)
        if i == j:
            return
        if self.rank[i] < self.rank[j]:
            self.parent[i] = j
        else:
            if self.rank[i] == self.rank[j]:
                self.rank[j] += 1
            self.parent[j] = i

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

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


uf = UnionFind(N)

for xyz in XYZ:
    X, Y, Z = xyz
    uf.union(X-1, Y-1)

ans = 0

for i in range(N):
    if uf.root(i) == i:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
graph_indexes=[i for i in range(N)] #それぞれの数は, どのグラフに含まれているのか
graphs=[[i] for i in range(N)] #実際のグラフ

for i in range(M):
	X,Y,Z=[int(c)-1 for c in input().split()]
	X_i=graph_indexes[X]
	Y_i=graph_indexes[Y]
	if(X_i!=Y_i):
		graphs[X_i].extend(graphs[Y_i].copy())
		graphs[Y_i]=[]
		graph_indexes[Y]=graph_indexes[X]
i=0
for g in graphs:
	if(g!=[]):
		i+=1
print(i)

Submission status: Runtime Error

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

a = {}
b = {}
for i in range(M):
  X, Y, Z = [int(i) for i in input().strip().split(' ')]
  if X not in a:
    a[X] = set()
    b[X] = 0
  if Y not in a:
    a[Y] = set()
    b[Y] = 0

  a[X].add(Y)
  b[X] += 1
  a[Y].add(X)
  b[Y] += 1

b = sorted(list(b.items()), key=lambda e: e[1], reverse=True)


def make_keys(keys, key):
  if key in keys:
    return
  keys.add(key)
  for k in a[key]:
    make_keys(keys, k)


counter = 0
#print(b)
for key, v in b:
  if key not in a:
    continue
  keys = set()
  make_keys(keys, key)

  for k in keys:
    del a[k]

  counter += 1

print(counter + N - len(b))

Submission status: Runtime Error

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

UF = list(range(N))


def find(x):
    if UF[x] != x:
        UF[x] = find(UF[x])
    return UF[x]


def unite(x, y):
    UF[find(x)] = find(y)


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


for x, y, z in XYZ:
    unite(x - 1, y - 1)
for i in range(N):
    find(i)
print(len(set(UF)))

Submission status: Runtime Error

Solution code:
n,m=[int(i) for i in input().split()]
ls=[]
for i in range(m):
    l=input().split()
    l.pop(2)
    ls.append([int(i) for i in l].sort())

from itertools import chain
count=len(set(range(n+1))-set(chain.from_iterable(ls))-{0})
sorted(ls)
while len(ls) != 0:
    ls = [i for i in ls if not (i.__contains__(ls[0][0]) or i.__contains__(ls[0][1]))]
    count+=1
print(count)

Submission status: Runtime Error

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

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

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

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

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]
uf = UnionFind(N)
cnt = 0
for i in range(M):
  x, y, z = map(int, input().split())
  if not uf.is_same(x, y):
    cnt += 1
    uf.union(x,y)
    
print(N-cnt)

Submission status: Runtime Error

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)
    D[y].append(x)

visited = [False for i in range(N)]
def dfs(n):
    for idx in D[n]:
        if not visited[idx]:
            visited[idx] = True
            dfs(idx)

cnt = 0
for n in range(N):
    if not visited[n]:
        visited[n] = True
        dfs(n)
        cnt += 1
print(cnt)

Submission status: Runtime Error

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

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

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

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

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]
uf = UnionFind(N)
cnt = 0
for i in range(M):
  x, y, z = map(int, input().split())
  if !uf.is_same(x, y):
    cnt += 1
    uf.union(x,y)
    
print(N-cnt)

Submission status: Runtime Error

Solution code:
def func(c,x):
    c[x][0] = 1
    for i in c[x][1:]:
        if c[i][0] == 0:
            func(c,i)
    return c

# 入力
N,M = map(int,input().split())
XYZ = list(list(map(int,input().split()))for i in range(M))
############################################
card = [[0]for i in range(N)]
set = 0
############################################
# グラフを描く
for x,y,z in XYZ:
    card[x-1].append(y-1)
    card[y-1].append(x-1)
############################################
for i in range(N):
    if card[i][0] == 0:
        set += 1
        card = func(card,i)
ans = set
############################################
for c in card:
    if c == 0:
        ans += 1
print(ans)

Submission status: Runtime Error

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

class UnionFindTree:
    def __init__(self, n):
        self.nodes = list(range(n+10))
    def find(self, x):
        if self.nodes[x] == x:
            return x
        parent = self.find(self.nodes[x])
        self.nodes[x] = parent
        return parent
    def unite(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return
        self.nodes[a] = self.nodes[b]
    def is_same(self, a, b):
        return self.find(a) == self.find(b)

uf = UnionFindTree(N)
for i in range(K):
    i,j,k=map(int, input().split())
    uf.unite(i,j)

st = set()
for i in range(1,N+1):
    par = uf.find(i)
    st.add(par)

print(len(st))

Submission status: Runtime Error

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

class UnionFindTree:
    def __init__(self, n):
        self.nodes = list(range(n+1))
    def find(self, x):
        if self.nodes[x] == x:
            return x
        parent = self.find(self.nodes[x])
        self.nodes[x] = parent
        return parent
    def unite(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return
        self.nodes[a] = self.nodes[b]
    def is_same(self, a, b):
        return self.find(a) == self.find(b)

uf = UnionFindTree(N)
for i in range(K):
    i,j,k=map(int, input().split())
    uf.unite(i,j)

st = set()
for i in range(1,N+1):
    par = uf.find(i)
    st.add(par)

print(len(st))

Submission status: Runtime Error

Solution code:
class UnionFind():
    # 負の値は根で集合の個数
    # 正の値は次の要素を返す
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    # 集合の代表を求める
    def find(self, x):
        if self.table[x] < 0:
            return x
        root = self.find(self.table[x])
        self.table[x] = root
        return root
        # while self.table[x] >= 0:
        #     #根に来た時,self.table[根のindex]は負の値なのでx = 根のindexで値が返される。
        #     x = self.table[x]
        # return x

    # 併合
    def union(self, x, y):
        s1 = self.find(x)  # 代表のIndexを取得する
        s2 = self.find(y)
        if s1 != s2:  # 代表のIndexが違う場合
            if self.table[s1] < self.table[s2]:  # 要素数の多い方へMergeする
                self.table[s2] += self.table[s1]  # 子の和を増やす(-)
                self.table[s1] = s2  # Mergeされる側の代表をする側のインデックスに
            else:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
        return

    def size(self, x):
        # while self.table[x] >= 0:
        #     #根に来た時,self.table[根のindex]は負の値なのでx = 根のindexで値が返される。
        #     x = self.table[x]
        return -self.table[self.find(x)]


N, M = [int(n) for n in input().split()]
X = [0]*M
Y = [0]*M
Z = [0]*M
UF = UnionFind(N)
adj = [[0, []] for _ in range(N)]
for i in range(M):
    X[i], Y[i], Z[i] = [int(n) for n in input().split()]
    Z[i] %= 2
    X[i] -= 1
    Y[i] -= 1
    # adj[X[i]][0] += 1
    # adj[Y[i]][0] += 1
    # adj[X[i]][1].append((Y[i], Z[i]))
    # adj[Y[i]][1].append((X[i], Z[i]))
    UF.union(X[i], Y[i])
s = set([UF.find(0)])
ans = 1

for i in range(1, N):
    tmp = UF.find(i)
    if not(tmp in s):
        ans += 1
        s.add(tmp)
print(ans)

Submission status: Runtime Error

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):
        # 何もしないでいい
    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: Runtime Error

Solution code:
N,M = map(int,input().split())
#count chain node
cou_cha = [1 for i in range(N)]
cha_node = [[i]for i in range(N)]
for _ in range(M):
  x,y,z = map(int,input().split())
  cou_cha[x-1]+=1
  cou_cha[y-1]+=1
  cha_node[x-1].append(y-1)
  cha_node[y-1].append(x-1)
ans = cou_cha.count(1)
def f(x):
  global cou_cha,cha_node
  if cou_cha[x]==1:
    return
  cou_cha[x]=1
  for chi in cha_node[x]:
    f(chi)
while cou_cha.count(1)!=N:
  ans+=1
  f(cou_cha.index(max(cou_cha)))

print(ans)

Submission status: Runtime Error

Solution code:
class UnionFindTree:
    """Tested https://atc001.contest.atcoder.jp/tasks/unionfind_a
    """

    def __init__(self, size: int):
        self.size = size

        # all are root at first
        self._par = [i for i in range(size)]

    def find(self, x: int) -> int:
        if self._par[x] == x:  # root
            return x
        else:
            self._par[x] = self.find(self._par[x])  # path compression
            return self._par[x]

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

    def union(self, x: int, y: int):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            self._par[x] = y


def main():
    N, M = map(int, input().split())

    tree = UnionFindTree(N)
    for _ in range(M):
        x, y, z = map(int, input().split())
        tree.union(x-1, y-1)

    for i in range(N):
        tree.find(i)
    s = set(tree._par)
    print(len(s))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
def func(c,x,n):
    c[x][0] = n
    for i in c[x][1:]:
        if c[i][0] == 0:
            func(c,i,n)
    return c
XYZ = list(list(map(int,input().split()))for i in range(M))
card = [[0]for i in range(N)]
set = 0

for x,y,z in XYZ:
    card[x-1].append(y-1)
    card[y-1].append(x-1)
for i in range(N):
    if card[i][0] == 0:
        set += 1
        card = func(card,i,set)
ans = set
for c in card:
    if c == 0:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
# 連結成分 + 1
# UF tree

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

root = list(range(N+1))
depth = [0] * (N+1)

def find_root(x):
  y = root[x]
  if x == y:
    return x
  z = find_root[y]
  root[x] = z
  return z

def merge(x,y):
  global n_component
  xx = find_root(x)
  yy = find_root(y)
  if xx == yy:
    return
  n_component -= 1
  if depth[xx] >= depth[yy]:
    root[yy] = xx
    depth[xx] += 1
  else:
    root[xx] = yy
    depth[yy] += 1
  
for _ in range(M):
  x,y,z = [int(x) for x in input().split()]
  merge(x,y)


answer = n_component
print(answer)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
h = {}
c = {}
for i in range(N):
    h[i + 1] = []
    c[i + 1] = 0

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

ans = 0
rest = N

while len(h) > 0:
    p = max([[len(v), k] for k, v in h.items()])
    if p[0] == 0:
        break
    rest = rest - p[0] - 1
    for n in h[p[1]]:
        del h[n]
    del h[p[1]]
    ans += 1

print(ans + rest)

Submission status: Runtime Error

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


class UnionFind(object):
    """UnionFind木
    """

    def __init__(self, N):
        self.tree = list(range(N))

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

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.tree[x] = y


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

    print(len(set([uf.root(i) for i in range(N)])))

    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: Runtime Error

Solution code:
import sys
# input = sys.stdin.readline
inf = 10 ** 18

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

grp = [0] * N
moushiokuri = []
idx = 1
for i, (Xi, Yi, Zi) in enumerate(XYZ):
    if grp[Xi - 1] == grp[Yi - 1] == 0:
        grp[Xi - 1] = grp[Yi - 1] = idx
        idx += 1
    elif grp[Xi - 1] == 0:
        grp[Xi - 1] = grp[Yi - i]
    elif grp[Yi - 1] == 0:
        grp[Yi - 1] = grp[Xi - 1]
    else:
        moushiokuri.append((grp[Xi - 1], grp[Yi - 1]))

for src, dst in moushiokuri:
    for i, grpi in enumerate(grp):
        if grpi == src:
            grp[i] = dst

# print("#", grp)

ans = len(set(grp))
if 0 in grp:
    ans -= 1
    ans += grp.count(0)

print(ans)

Submission status: Runtime Error

Solution code:
/*********************************************JMD**********************************************/
//                                  |\  |     | |   |   /\                                   //
    //                              | \ |     | |---|  /--\                              //
        //                          |  \| |___| |   | /    \1999                     //
/*******************************************************************************************/
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;

#define mp make_pair
#define pb push_back
#define pf push_front
#define ss second
#define ff first
#define mem(x,val) memset(x,val,sizeof(x))
#define forr(i,a,b) for(ll i=a;i<b;i++)
#define f(i,n) forr(i,0,n)
#define sz(x) ll((x).size())
#define all(x) ((x).begin(),(x).end())
#define asc(x) ((int)(x))
#define precision(x) cout<<fixed<<setprecision((x));

const ll mod=1e9 + 7;

/*******************************************************************************************/
vector<vector<ll> > g;
vector<ll> vis;

void dfs(ll x)
{
    vis[x]=1;
    f(i,g[x].size())
    {
        if(!vis[g[x][i]]) dfs(g[x][i]);
    }
}
void solve()
{
    ll n,m;
    cin>>n>>m;
    g.resize(n);
    vis.resize(n);

    f(i,m)
    {
        ll x,y,z;
        cin>>x>>y>>z;
        x--,y--;

        g[x].pb(y);
        g[y].pb(x);
    }

    ll ans=0;

    f(i,n)
    {
        if(!vis[i]) dfs(i),ans++;
    }

    cout<<ans<<"\n";
    return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll t=1;
    //cin>>t;
    clock_t launch=clock();

    while(t--)
    {
        solve();
    }

    clog<<((long double)(clock()-launch)/CLOCKS_PER_SEC)<<"\n";
}