AtCoderをしていた時、解法でオイラーツアーという単語が出てきた。
初めて聞いた単語だったため、以下のサイトを参考に実装して思考過程を整理してみた。
深さ優先探索（DFS）を行い、訪れた頂点の順番と時刻を記録するアルゴリズム。
オイラーツアーを使うことで、グラフの問題を配列の問題へと置き換えられるようになる。
Pythonは再帰を使うと遅いため、AtCoderでTLEにならないよう今回はスタックを使って実装してみた。
完成したコード
def EulerTour(n, graph, root):
"""
(n: int, graph: List[List[int]], root: int) -> Tuple[List[int], List[int], List[int]]:
:param n: the number of vertex points
:param graph: 2D matrix of N vertices given by the edges
:param root: start node index
:return tour: order of visited vertex
:return in_time: first visiting time of each vertex
:return out_time: last visiting time of each vertex
example:
graph = [[] for _ in range(n)]
for _ in range(n):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
tour, in_time, out_time = EulerTour(n, graph, 0)
"""
parent = [-1] * n
stack = [~root, root] # postorder, preorder
curr_time = -1
tour = []
in_time = [-1] * n
out_time = [-1] * n
while stack:
curr_node = stack.pop()
curr_time += 1
if curr_node >= 0: # preorder
tour.append(curr_node)
if in_time[curr_node] == -1:
in_time[curr_node] = curr_time
for next_node in graph[curr_node]:
if next_node != parent[curr_node]:
parent[next_node] = curr_node
stack.append(~next_node)
stack.append(next_node)
elif curr_node < 0: # postorder
out_time[~curr_node] = curr_time
if parent[~curr_node] != -1:
tour.append(parent[~curr_node])
return tour, in_time, out_time
実装までの思考
グラフはどの頂点とどの頂点が繋がっているのかという辺の情報で与えられることとする。例えば、
input
0 3
1 0
1 4
2 1
graph = [[3, 1],
[0, 4, 2],
[1],
[0],
[1]]まずは普通のDFSを理解し、スタックに置き換えることを考える。
行きがけ（preorder）、帰りがけ（postorder）、通りがけ（inorder）の練習には、LeetCodeの以下の問題がそのまんまで練習しやすかった。
オイラーツアーでは行けるところまで探索し（行きがけ）、最後のノードに着いたら元に戻る（帰りがけ）という処置を行う。
これを先入れ後出しのスタックで実現しようとすると、帰りがけ→行きがけの順で頂点スタックに入れればいい。
stack = [postorder, preorder]ここで、行きがけなのか帰りがけなのかを識別するフラグも一緒に入れたくなる。
しかし、フラグを設定すると実装がタプルになって面倒になり、フラグの分のメモリ使用量が増えてしまう。
そこで、正負によって行きがけなのか帰りがけなのかを判定するようにした。
スタートする頂点をrootとすると、以下のようなスタックから開始出来る。
開始地点の帰りがけは必要ないように見えるが、時刻を記録するために必要となる。
stack = [-root, root] # postorder, preorderしかし、頂点0から開始する場合、0も-0も同じ値のため、正しくifで分岐されない。
そのため、notを使った符号の反転を考える。
これにより not 0 = -1 となり、ifで分岐されるようになる。
notはチルダ（~）で表現できるため、スタックは以下のように開始するよう変更する。
stack = [~root, root] # postorder, preorderスタックが空になるまで処理を繰り返すので、処理の骨子は以下のようになる。
グラフの頂点の数をnとして、オイラーツアーの結果を保存する配列と変数も設定する。
最初の頂点を時刻0としたいので、現在時刻current timeは-1で初期化する。
elifのところはelseでも良いのだが、理解しやすいよう条件を明示している。
stack = [~root, root] # postorder, preorder
curr_time = -1
tour = []
in_time = [-1] * n
out_time = [-1] * n
while stack:
curr_node = stack.pop()
curr_time += 1
if curr_node >= 0: # preorder
...
elif curr_node < 0: # postorder
...行きがけ
訪れた頂点を保存する。
オイラーツアーでは「初めてその頂点を訪れた時刻」を保存するため、初めて訪れたかどうか判定してから時刻を更新する。
if curr_node >= 0: # preorder
tour.append(curr_node)
if in_time[curr_node] == -1:
in_time[curr_node] = curr_time
その後、次の頂点に潜っていく。
スタックは先入れ後出しなので、帰りがけ→行きがけで積み込んでいく。
for next_node in graph[curr_node]:
stack.append(~next_node)
stack.append(next_node)しかし、このままではcurr_nodeとnext_nodeで無限ループが起きてしまう。
同じ頂点を行き来しないようにifが必要となるが、どこから来たのかという「親の頂点」の情報が欲しくなる。
親の頂点を保存するための配列を新たに用意し、次のノードが自分の親じゃないなら探索を続けていく。
合わせて親の情報も更新する。
これで行きがけの完成。
parent = [-1] * n
stack = [~root, root] # postorder, preorder
curr_time = -1
tour = []
in_time = [-1] * n
out_time = [-1] * n
while stack:
curr_node = stack.pop()
curr_time += 1
if curr_node >= 0: # preorder
tour.append(curr_node)
if in_time[curr_node] == -1:
in_time[curr_node] = curr_time
for next_node in graph[curr_node]:
if next_node != parent[curr_node]:
parent[next_node] = curr_node
stack.append(~next_node)
stack.append(next_node)帰りがけ
帰りがけでは親頂点に戻るだけなので、行きがけで保存した親情報を参照する。
行きがけで現在の頂点を保存しているため、重複しないよう帰りがけでは頂点を保存しないようにする。
また、オイラーツアーでは「最後に頂点を出た時刻」を保存するため、行きがけと違って時刻の更新に条件判定は必要なく、常に最新の一番遅い時刻を記録し続ければ良い。
elif curr_node < 0: # postorder
# tour.append(curr_node) は不要
out_time[~curr_node] = curr_time
tour.append(parent[~curr_node])最後に、オイラーツアーが終わってスタート地点に帰ってきた時の帰りがけを考える。
最後に訪れた時刻を更新するためにスタックを[~root, root]で初期化したが、この時にtour.append(parent[~curr_node])によりダミーの親 -1 が保存されてしまう。
スタート地点の親は当然存在しないため、ifを追加する。
elif curr_node < 0: # postorder
out_time[~curr_node] = curr_time
if parent[~curr_node] != -1:
tour.append(parent[~curr_node])ifを追加せず、whileを抜けた後に -1 を除去しても良い。
この時、スライスを使うと遅いので注意する。
tour.pop() # 0(1)
tour = tour[:-1] # O(N)whileの度にifするよりも、最後に一度だけpopする方が直感的に早そうだが、後で自分で見返した時に混乱しそうなので分かりやすいifを採用した。
以上で完成。AtCoderで使い回せるよう関数にしておく。
型ヒントをコメント内に書いたのは、コピペした時にAtCoderで import typing する手間を減らすため。
重み付きグラフなどが与えられた場合でも、重み用の配列を用意すれば別途対応可能。
def EulerTour(n, graph, root):
"""
(n: int, graph: List[List[int]], root: int) -> Tuple[List[int], List[int], List[int]]:
:param n: the number of vertex points
:param graph: 2D matrix of N vertices given by the edges
:param root: start node index
:return tour: order of visited vertex
:return in_time: first visiting time of each vertex
:return out_time: last visiting time of each vertex
example:
graph = [[] for _ in range(n)]
for _ in range(n):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
tour, in_time, out_time = EulerTour(n, graph, 0)
"""
parent = [-1] * n
stack = [~root, root] # postorder, preorder
curr_time = -1
tour = []
in_time = [-1] * n
out_time = [-1] * n
while stack:
curr_node = stack.pop()
curr_time += 1
if curr_node >= 0: # preorder
tour.append(curr_node)
if in_time[curr_node] == -1:
in_time[curr_node] = curr_time
for next_node in graph[curr_node]:
if next_node != parent[curr_node]:
parent[next_node] = curr_node
stack.append(~next_node)
stack.append(next_node)
elif curr_node < 0: # postorder
out_time[~curr_node] = curr_time
if parent[~curr_node] != -1:
tour.append(parent[~curr_node])
return tour, in_time, out_time試しに以下の問題を解いてみる。
この問題では頂点が小さい順に訪れるという制約があるため、入力するグラフはソートしておく。
スタックは先入れ後出しのため、頂点の番号が小さい順に訪れるために、頂点の大きい番号からスタックに積み込めるようfor next_node in graph[curr_node][::-1]と反転させておく。
def EulerTour(n, graph, root):
"""
(n: int, graph: List[List[int]], root: int) -> Tuple[List[int], List[int], List[int]]:
:param n: the number of vertex points
:param graph: 2D matrix of N vertices given by the edges
:param root: start node index
:return tour: order of visited vertex
:return in_time: first visiting time of each vertex
:return out_time: last visiting time of each vertex
example:
graph = [[] for _ in range(n)]
for _ in range(n):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
tour, in_time, out_time = EulerTour(n, graph, 0)
"""
parent = [-1] * n
stack = [~root, root] # postorder, preorder
curr_time = -1
tour = []
in_time = [-1] * n
out_time = [-1] * n
while stack:
curr_node = stack.pop()
curr_time += 1
if curr_node >= 0: # preorder
tour.append(curr_node)
if in_time[curr_node] == -1:
in_time[curr_node] = curr_time
for next_node in graph[curr_node][::-1]:
if next_node != parent[curr_node]:
parent[next_node] = curr_node
stack.append(~next_node)
stack.append(next_node)
elif curr_node < 0: # postorder
out_time[~curr_node] = curr_time
if parent[~curr_node] != -1:
tour.append(parent[~curr_node])
return tour, in_time, out_time
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n - 1):
a, b = map(int, input().split())
a -= 1
b -= 1
graph[a].append(b)
graph[b].append(a)
for i in range(n):
graph[i] = sorted(graph[i])
tour, in_time, out_time = EulerTour(n, graph, 0)
tour = [i + 1 for i in tour]
print(*tour)ほとんどコピペでAC。
whileのスタックを使ったことでpypyで高速化され、実行時間は0.6秒だった。
以下の再帰を使った例では1.5秒かかったため、約2倍早くなったことになる。
実務ではどうなのか分からないが、AtCoder的には有利。
ABC239のE – Subtree K-th Maxでは、オイラーツアーでグラフを配列の問題に落とし込み、セグメントツリーを使うことで解けた。
以下はAC例。
この時のセグメントツリーは以下から拝借させて頂いた。
コメント