E - 1 or 2

Contest Duration: 2019-05-19(Sun) 12:00 - 2019-05-19(Sun) 13:40 (local time) (100 minutes) Back to Home

E - 1 or 2 Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $500$ 点

問題文

$N$ 枚のカードが一列に伏せられており、各カードには整数 $1$ または $2$ が書かれています。

$i$ 番目のカードに書かれている整数を $A_i$ とします。

あなたの目的は $A_1, A_2, ..., A_N$ を当てることです。

次のことが分かっています。

$i = 1, 2, ..., M$ について $A_{X_i} + A_{Y_i} + Z_i$ は偶数である。

あなたは魔法使いです。次の魔法を何度でも使うことができます。

魔法: コストを $1$ 払う。カードを $1$ 枚選び、そのカードに書かれた整数 $A_i$ を知る。

最小で何コスト払えば、 $A_1, A_2, ..., A_N$ 全てを確実に当てることができるでしょうか。

なお、与えられる入力には矛盾がないことが保証されます。

制約

入力は全て整数である。
$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$
$(X_i, Y_i)$ の組は互いに異なる。
与えられる入力には矛盾がない(すなわち、条件を満たす $A_1, A_2, ..., A_N$ が存在する)。

入力

入力は以下の形式で標準入力から与えられる。

 $N$   $M$ 
 $X_1$   $Y_1$   $Z_1$ 
 $X_2$   $Y_2$   $Z_2$ 
 $\vdots$ 
 $X_M$   $Y_M$   $Z_M$

出力

$A_1, A_2, ..., A_N$ 全てを確実に当てるために払う必要のあるコストの合計の最小値を出力せよ。

入力例 1Copy

Copy

3 1
1 2 1

出力例 1Copy

Copy

$1$ 枚目と $3$ 枚目のカードに対してそれぞれ $1$ 回ずつ魔法を使えば、 $A_1, A_2, A_3$ 全てを当てることができます。

入力例 2Copy

Copy

出力例 2Copy

Copy

入力例 3Copy

Copy

100000 1
1 100000 100

出力例 3Copy

Copy

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 1Copy

Copy

3 1
1 2 1

Sample Output 1Copy

Copy

You can determine all of $A_1, A_2, A_3$ by using the magic for the first and third cards.

Sample Input 2Copy

Copy

Sample Output 2Copy

Copy

Sample Input 3Copy

Copy

100000 1
1 100000 100

Sample Output 3Copy

Copy