めもめも

このブログに記載の内容は個人の見解であり、必ずしも所属組織の立場、戦略、意見を代表するものではありません。

021 - Come Back in One Piece(★5)の解説

何の話かと言うと

atcoder.jp

この問題をネタに、「(閉路を含む)有向グラフの深さ優先探索」の実装方法に関する話をします。

問題の解法については公式解説に譲りますが、解法の中で「強連結成分分解」が使われており、これを実装する際に、「(閉路を含む)有向グラフの深さ優先探索」が必要になります。

木構造の深さ優先探索

次のような単純な木を考えます。再帰呼び出しではなく、キュー(スタック)を使って深さ優先探索します。

   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

解答例

ここまでは、連結成分のみを探索する前提でしたが、実際には非連結成分(強連結でない部分)も探索する必要があります。詳細は解答例を参照してください。

atcoder.jp

(最初、フラグを立てるタイミングの問題に気づいてなくて、半日ほど悩んじゃいました。。。)