何の話かと言うと
この問題をネタに、「(閉路を含む)有向グラフの深さ優先探索」の実装方法に関する話をします。
問題の解法については公式解説に譲りますが、解法の中で「強連結成分分解」が使われており、これを実装する際に、「(閉路を含む)有向グラフの深さ優先探索」が必要になります。
木構造の深さ優先探索
次のような単純な木を考えます。再帰呼び出しではなく、キュー(スタック)を使って深さ優先探索します。
1 | -- -- | | 2 3
行きがけ順と帰りがけ順で処理するなら、それぞれ、こんな感じ。
import sys from collections import defaultdict, deque def main(f): N, M = list(map(int, f.readline().split())) link = [[] for _ in range(N+1)] for _ in range(M): a, b = list(map(int, f.readline().split())) link[a].append(b) link[b].append(a) q = deque() print('行きがけ順') flag = [False] * (N+1) q.append(1) flag[1] = True while q: i = q.pop() #### # i について処理する print(i) #### for j in link[i]: if flag[j]: continue q.append(j) flag[j] = True print('帰りがけ順') flag = [False] * (N+1) q.append(1) flag[1] = True while q: i = q.pop() if i < 0: #### # -i について処理する print(-i) #### continue q.append(-i) # 帰りチェック用 for j in link[i]: if flag[j]: continue q.append(j) flag[j] = True main(sys.stdin)
# input 3 2 1 2 1 3 # output 行きがけ順 1 3 2 帰りがけ順 3 2 1
帰りがけ順については、行きがけ順をリストに入れて reverse() しても構いませんが、ここでは、帰りチェック用の番兵を仕込むというテクニックを使っています。
(閉路を含む)有向グラフの深さ優先探索
次の有向グラフを考えます。これを深さ優先探索して、帰りがけ順にノードを並べるとどうなるでしょう?
1---->2 | ^ v | 3---->4
最初に右に行くか下に行くかで結果が変わる可能性がありますが、たとえば、先に下に行ったなら 1 -> 3 -> 4 -> 2 で突き当たるので、帰りがけ順は、2 -> 4 -> 3 -> 1 になります。
一方、先に右に言った場合がちょっとトリッキーです。まず、1 -> 2 で突き当たりますが、次に下に行くと、1 -> 3 -> 4 ->2 で突き当たります。最後の 2 はすでに訪問済みですが、「深さ優先」なので(ループしない限りは)行けるところまで進みきる必要があります。結果、帰りがけ順は、先ほどの結果と一致して、2 -> 4 -> 3 -> 1 になります。
これを先ほどの番兵のテクニックで実装したいのですが、次は失敗例になります。
import sys, math from collections import defaultdict, deque def main(f): N, M = list(map(int, f.readline().split())) link_to = [[] for _ in range(N+1)] link_from = [[] for _ in range(N+1)] for _ in range(M): a, b = list(map(int, f.readline().split())) link_from[a].append(b) link_to[b].append(a) q = deque() print('帰りがけ順') flag = [False] * (N+1) q.append(1) flag[1] = True while q: i = q.pop() if i < 0: #### # -i について処理する print(-i) #### continue q.append(-i) # 帰りチェック用 for j in link_from[i]: if flag[j]: continue q.append(j) flag[j] = True main(sys.stdin)
# input 4 4 1 2 1 3 3 4 4 2 # output 帰りがけ順 4 3 2 1
この例では、先に右に行って、2 に訪問フラグを立ててしまっているので、上述の「深さ優先」が実現できていません。
じゃあどうするのかと言うと。。。
次のように、子ノードをキューに入れてもフラグは立てずにおきます。これにより、別経路での上書き訪問(?)が可能になります。その後、キューから取り出した後に(上書き訪問時の二重処理を防ぐために)フラグを立てればOKです。
import sys, math from collections import defaultdict, deque def main(f): N, M = list(map(int, f.readline().split())) link_to = [[] for _ in range(N+1)] link_from = [[] for _ in range(N+1)] for _ in range(M): a, b = list(map(int, f.readline().split())) link_from[a].append(b) link_to[b].append(a) q = deque() print('帰りがけ順') flag = [False] * (N+1) q.append(1) while q: i = q.pop() if i < 0: print(-i) continue if flag[i]: # 2 回目の処理はスキップする continue flag[i] = True # ここで初めてフラグを立てる q.append(-i) # 帰りチェック用 for j in link_from[i]: if flag[j]: continue # flag[j] = True # 別経路で来る可能性があるので、ここでフラグを立ててはいけない q.append(j) main(sys.stdin)
# input 4 4 1 2 1 3 3 4 4 2 # output 帰りがけ順 2 4 3 1
解答例
ここまでは、連結成分のみを探索する前提でしたが、実際には非連結成分(強連結でない部分)も探索する必要があります。詳細は解答例を参照してください。
(最初、フラグを立てるタイミングの問題に気づいてなくて、半日ほど悩んじゃいました。。。)