ARC229 E - Taka and Hashi

考え方

まずは、計算量を気にせず考える。

各ラベルごとにUnionFind木を作成する。
まず、ラベル $1$ で頂点 $1$ と繋がっている範囲は、全て答えである。
ではラベル $1$ で繋がっていないところに行く方法は、と考えてみる。

これは、頂点 $P$ と頂点 $Q$ が、ラベル $2$ でもラベル $3$ でも同じ連結成分にいることである。
この場合、この $2$ 頂点の間で高橋くんが移動できるので、ラベル $1$ の辺を追加で引いてしまってよい。
これを全頂点間で調査後、各頂点ごとにラベル $1$ で頂点 $1$ と同一連結成分にあるか確認をすればよい。

さて、これの計算量を考えてみると、$2$ 頂点間で確認する部分が $O(N^2\alpha(N))$ である。
アッカーマン関数の逆関数 $\alpha(N)$ はほぼ定数とみても $O(N^2)$ で間に合わない。
よって、ここを高速化する必要がある。

これは、調べているのがUnionFind木であることを活かして高速化できる。
$3$ つの頂点 $P,Q,R$ が全てラベル $2$ でもラベル $3$ でも同じ連結成分にいるとしよう。
この場合、$P-Q$ 間を連結し、$P-R$ 間を連結すると、その後 $Q-R$ 間を連結する必要はない。
つまり、条件を満たす相手が自分より小さい番号範囲に複数いるなら、そのうち $1$ つだけみつければよい。

となれば、前から頂点を $1$ つずつ見て、各ラベルでの連結成分のリーダーを調べる。
一度見たリーダー組が再び出てきたときには、それが初めて出てきたときの頂点と連結してやればよい。
これは map などを用いれば $O(N\log N)$ で実行できる。
これで全体の計算量は $O(M\alpha(N)+N\log N)$ になって、間に合う。

入力例1での動作

$1$ 番目のテストケースを考える。

入力を受け取る。

n: 5
m: 5
edges:
(1, 2, 1)
(2, 3, 2)
(3, 4, 2)
(2, 4, 3)
(4, 5, 1)

ラベル $1$ の辺は $1-2,4-5$ である。
よって、まずラベル $1$ のUnionFind木では $\{1,2\},\{3\},\{4,5\}$ がそれぞれ連結成分になる。

ラベル $2$ の辺は $2-3,3-4$ なので、連結成分は $\{1\},\{2,3,4\},\{5\}$ である。
ラベル $3$ の辺は $2-4$ なので、連結成分は $\{1\},\{2,4\},\{3\},\{5\}$ である。

各頂点について、ラベル $2$ とラベル $3$ で属する連結成分の組を調べる。

ここでは、仮に各 UnionFind 木で連結成分内の番号が最小の頂点がリーダーになるとする。
すると、各頂点のリーダー組は次のようになる。

このリーダー組をキーとして、最初にその組が出てきた頂点番号を map に保存しながら前から見ていく。

このように、頂点 $2$ と頂点 $4$ だけが同じリーダー組になる。
したがって、ラベル $1$ のUnionFind木で頂点 $2$ と頂点 $4$ を連結する。

これにより、ラベル $1$ のUnionFind木では $\{1,2,4,5\}$ が同じ連結成分になる。
頂点 $1$ と同じ連結成分にある頂点は $1,2,4,5$ なので、これらが答えである。

注意点

特になし。

別解

特になし。