分数: 366 分
问题陈述
高桥是一家体育俱乐部的教练, N 玩家。最初,每个玩家都属于一个仅由他们自己组成的单独团队。每个团队可以有一种旗帜颜色,但在初始状态下,没有团队被分配旗帜颜色。
高桥表演 M 操作按顺序进行。
在 i第次操作,完成以下操作:
- 哪个球员所在的球队 U_i 所属球队以及球员所属球队 V_i 所属部门合并为一个团队。但是,如果两名玩家已经属于同一团队,则不会执行合并,并且该团队将用作目标。
- 结果球队的旗帜颜色设置为 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