1 or 2

题目描述

有 $N$ 张牌面朝下按顺序摆成一排。每张牌上写着一个整数 $1$ 或 $2$。 设 $A_i$ 为第 $i$ 张牌上写的整数。 你的目标是正确猜出 $A_1, A_2, ..., A_N$。 你知道以下事实：

对于每个 $i = 1, 2, ..., M$，值 $A_{X_i} + A_{Y_i} + Z_i$ 是偶数。

你是一名魔术师，可以任意次数使用以下魔法： Magic：选择一张牌并得知其上写的整数 $A_i$。使用该魔法的代价是 $1$。 确定所有 $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$ 所需的最小总代价。

3 1
1 2 1

2

6 5
1 2 1
2 3 2
1 3 3
4 5 4
5 6 5

2

100000 1
1 100000 100

99999

提示

输入中的所有数值均为整数。 $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$.）你可以通过对第一张和第三张牌使用魔法来确定所有 $A_1, A_2, A_3$.

标签: AtCoder|abc126E

来源

AtCoder|abc126E