https://www.hackerrank.com/contests/world-codesprint-11/challenges/hackerland
問題概要
N頂点M辺の有向グラフがある。
ここでQ個のクエリを処理する。
- 1 x d : 新たに頂点を1つ用意し、d=0ならxから新頂点へd=1なら新頂点からxへ有向辺をはる
- 2 x y : 頂点xから頂点yへ到達可能かを判定
必要知識
強連結成分分解
UnionfFind
トポロジカルソート
解法
https://www.hackerrank.com/contests/world-codesprint-11/challenges/hackerland/submissions/code/1301786452
まず、クエリの1番目のやつを先にやっておく。
有向グラフで到達性判定でクエリ形式だと、正攻法は厳しそう。
解法の流れは以下の通り。
1. 有向グラフを強連結成分分解する
2. 強連結成分をUnionFind
よくある有向グラフの強連結成分をまとめることで、DAGに変換するテク
ここでDAGの頂点に到達されうる頂点をbitsetで用意しておく。
3. 作ったDAGをトポロジカルソート順でbitsetを子にorしていく
これで各頂点について、到達されうる頂点を全列挙できるので、これを使ってクエリに答える
