かしのブログ

競技プログラミングとか

第一回日本最強プログラマー学生選手権決勝 B - Reachability

AtCoder

問題

$3N$ 頂点の有効グラフの頂点 $x_0, \cdots, x_{N-1}, y_0, \cdots, y_{N-1}, z_0, \cdots, z_{N-1}$ の

$x_i$ から $y_j$ へ向かう辺が存在するか
$x_i$ から $z_k$ へのパスが存在するか

がわかっている。この条件を満たす $y_j$ から $z_k$ へ向かう辺の集合があれば求める。

考察

これらの条件を満たさないのは、

$x_i$ から $z_k$ へのパスがないが、 $x_i$ から $y_j$ への辺があり、 $y_j$ から $z_k$ への辺があるような $j$ がある
$x_i$ から $z_k$ へのパスがあるが、 $x_i$ から $y_j$ への辺があり、 $y_j$ から $z_k$ への辺があるような $j$ がない

のいずれかである。また、前者は全ての $y_j$ から $z_k$ の辺が存在しない、後者は全ての $y_j$ から全ての $z_k$ への辺を追加すれば解決する。よって、一方を最低限満たすような辺の集合を作ったときに、他方が満たされるかを判定すればいい。

はじめ、全ての $y_j$ から全ての $z_k$ への辺を用意する。これから、前者の条件を満たすように最低限の辺を削除する。このとき、後者の条件が満たされているかを判定する。

実装