C - Team Flag Colors Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は N 人の選手が所属するスポーツクラブの監督です。最初、各選手はそれぞれ 1 人だけからなる別々のチームに所属しています。各チームは旗の色を 1 つ持つことができますが、初期状態ではどのチームにも旗の色は設定されていません。

高橋君は M 回の操作を順に行います。

i 回目の操作では、次のことを行います。

  1. 選手 U_i が所属するチームと選手 V_i が所属するチームを合併して 1 つのチームにします。ただし、2 人が既に同じチームに所属している場合は、合併は行わずそのチームをそのまま対象とします。
  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
  • 1 行目には、選手の人数を表す整数 N と、操作の回数を表す整数 M が、スペース区切りで与えられる。
  • 2 行目から M 行には、i 番目の操作の情報として、選手番号 U_i 、選手番号 V_i 、旗の色 C_i がスペース区切りで与えられる。
  • 選手の番号は 1 から N までの整数である。
  • C_i はその操作で設定される旗の色を表す整数である。

出力

すべての操作終了後、旗の色が設定されているチームの旗の色として現れる、異なる色の種類数を 1 行で出力してください。

入力例 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

Score : 366 pts

Problem Statement

Takahashi is the coach of a sports club with N players. Initially, each player belongs to a separate team consisting of only themselves. Each team can have one flag color, but in the initial state, no team has a flag color assigned.

Takahashi performs M operations in order.

In the i-th operation, the following is done:

  1. The team to which player U_i belongs and the team to which player V_i belongs are merged into a single team. However, if the two players already belong to the same team, no merge is performed and that team is used as the target.
  2. The flag color of the resulting team is set to C_i. Any previous flag color is overwritten.

After all operations are completed, consider the teams that have a flag color assigned. Determine the number of distinct colors that appear as flag colors among those teams. Teams that were never the target of any operation (teams with no flag color assigned) are ignored.

Constraints

  • 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
  • All input values are integers.

Input

N M
U_1 V_1 C_1
U_2 V_2 C_2
:
U_M V_M C_M
  • The first line contains an integer N representing the number of players and an integer M representing the number of operations, separated by a space.
  • The following M lines each contain the information for the i-th operation: player number U_i, player number V_i, and flag color C_i, separated by spaces.
  • Player numbers are integers from 1 to N.
  • C_i is an integer representing the flag color set by that operation.

Output

Print on a single line the number of distinct colors that appear as flag colors among the teams that have a flag color assigned after all operations are completed.

Sample Input 1

4 3
1 2 10
3 4 20
2 3 10

Sample Output 1

1

Sample Input 2

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

Sample Output 2

2

Sample Input 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

Sample Output 3

2

Sample Input 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

Sample Output 4

3

Sample Input 5

2 1
1 2 1000000000

Sample Output 5

1