← 返回题目列表

AtCoder · awc0068_c

C. 队旗颜色

中文机器翻译题面 查看原题

分数: 366 分

问题陈述

高桥是一家体育俱乐部的教练, N 玩家。最初,每个玩家都属于一个仅由他们自己组成的单独团队。每个团队可以有一种旗帜颜色,但在初始状态下,没有团队被分配旗帜颜色。

高桥表演 M 操作按顺序进行。

在 i第次操作,完成以下操作:

  1. 哪个球员所在的球队 U_i 所属球队以及球员所属球队 V_i 所属部门合并为一个团队。但是,如果两名玩家已经属于同一团队,则不会执行合并,并且该团队将用作目标。
  2. 结果球队的旗帜颜色设置为 C_i。任何先前的标志颜色都会被覆盖。

完成所有操作后,考虑分配了旗帜颜色的团队。确定这些团队中显示为旗帜颜色的不同颜色的数量。从未成为任何操作目标的团队(未分配旗帜颜色的团队)将被忽略。

约束

  • 1 \leq N \leq 200000
  • 1 \leq M \leq 150000
  • 1 \leq U_i, V_i \leq N
  • U_i \neq V_i
  • 1 \leq C_i \leq 10^9
  • 所有输入值均为整数。

输入

N M
U_1 V_1 C_1
U_2 V_2 C_2
:
U_M V_M C_M
  • 第一行包含一个整数 N 代表玩家数量和一个整数 M 代表操作次数,以空格分隔。
  • 以下 M 行每行包含以下信息 i第次操作:玩家编号 U_i,玩家编号 V_i和标志颜色 C_i,用空格分隔。
  • 玩家编号是以下整数 1 to N.
  • C_i 是一个整数,表示该操作设置的标志颜色。

输出

在所有操作完成后,在已分配旗帜颜色的团队中,在单行上打印作为旗帜颜色出现的不同颜色的数量。


示例输入 1

4 3
1 2 10
3 4 20
2 3 10

示例输出 1

1

示例输入 2

5 4
1 2 7
2 3 8
1 3 7
4 5 8

示例输出 2

2

示例输入 3

10 9
1 2 10
2 3 20
4 5 10
6 7 30
8 9 30
1 3 40
5 6 20
7 4 50
9 10 50

示例输出 3

2

示例输入 4

15 16
1 2 1
3 4 2
5 6 3
7 8 4
9 10 5
11 12 6
13 14 7
2 3 8
6 7 9
10 11 5
1 4 1
8 5 3
12 9 6
4 5 8
14 15 7
1 8 2

示例输出 4

3

示例输入 5

2 1
1 2 1000000000

示例输出 5

1