参考文献
- 秋葉拓哉,岩田陽一,北川宜稔,『プログラミングコンテストチャレンジブック』,株式会社 マイナビ出版(2012)
- AtCoder Beginner Contest 223 Problem D
- Nyann様の 提出 #26618152
1. 初めに
AtCoder ABC 223 D問題 にてトポロジカルソートに関する問題が出たそうです。
解説を読む以前に,
『トポロジカルソートってなんだっけ...?』と思った私はそれに関してまとめてみることにします。
2. トポロジカル順序とは
有向非巡回グラフ(Directed Acyclic Graph)において,
$i,j\in[N],v_i,v_j\in V$に対して$v_i\rightarrow v_j$ならば $i<j$である時,トポロジカル順序といいます
つまり, 以下のようなグラフのことをいいます。
そして,このような順序となるようなグラフを求めることをトポロジカルソートと呼びます。
また,上記において自分に入ってくるノードの数を入次数と定義すると,入次数はそれぞれ {0,1,1,1,1,2}となります.
3. 今回の問題への対応付け
今回のD問題 はこのトポロジカルの応用例であると考えられます。
実際の問題文(一部改変)は以下の通りです。
問題
ある数列
T=\{ A_i,B_i\}^{M}_{i=1}
が与えられた時に,$(1,2,...,N)$を並び替えて得られる数列 $P$ であって以下の条件を満たすもののうち、辞書順で最小のものを求めよ。
\begin{align}
\forall i &\in [M]{\rm において,} A_i,B_i\in T \cap P {\rm ならば} \\
\exists k,l &\in [|P|](k<l)\ {\rm s.t.}\ P_k=A_i, P_l=B_i
\end{align}
ただし,そのような$P$が存在しない場合は-1を返せ.
考察
$A_i,B_i\in T$であれば$A_i \rightarrow^{+} B_i$であるようなものを調べていくため,トポロジカル順序にいて
-
$v_i\rightarrow v_j$を$A_i,B_i\in T$
-
$i<j$を$A_i \rightarrow^{+} B_i$
とすることで,トポロジカルソートと似たように考えることができそうだと考えます(通常のトポロジカルソートと対応関係が逆であることに注意する必要があります)。
それではここからは実際にどのように解けば良いかを考えましょう。
4. 実装とそのアルゴリズム
今回は,最も提出が早かった(というか開催前に提出済みであった)
Nyann様の解答を参考にさせていただきました。
方針としては,
- 1に $A_i \rightarrow^{+} B_i$は確定なのでそれを埋めていきます.
- 2に 巡回グラフでないかどうかを確認します. means 入次数が0のものがあるかを確認します.
- 3に 入次数が0の集合のうち,最も小さいものから順に追加していきます. mean use heqpq.
- 4に 今追加したところの入次数を減らしていきます.
- 5に 追加される配列の長さが$N$になるまで繰り返します.
だと思います.
Nyann様の解答は以下の通りです(一部改変, Nyann様の 提出 #26618152 )。
# 問題設定
N, M = map(int, input().split())
# グラフを表すmatrix g :
# 任意の頂点aに対してg[a]はaから矢印が向いている頂点を指す
g = [list()for _ in range(N)]
d = [0] * N
for _ in range(M):
a, b = map(int, input().split())
a -= 1
b -= 1
g[a].append(b)
d[b] += 1
import heapq
Q = []
# 入次数が0のものを候補として入れる
for i in range(N):
if d[i] == 0:
heapq.heappush(Q, i)
ans = []
while len(ans) < N:
# 非巡回グラフであることを確認する
if len(Q) == 0:
print(-1)
exit()
# 最も小さい値を取ってくる
x = heapq.heappop(Q)
ans.append(x + 1)
# 現在追加したもので x=A_i -> + B_i の関係を見る
for y in g[x]:
d[y] -= 1
if d[y] == 0:
heapq.heappush(Q, y)
print(*ans)
5 あとがき
いかがでしたでしょうか。
このように,$\rightarrow^{+}$ヒープ構造を使ったり,うまく行列を定義したりすることで,今回の問題が解けることを確認できました。
また,グラフのアルゴリズムの勉強が自分は少し苦手であることがわかったので練習問題を解いて復習したいと思いました。