非再帰 Euler Tour を書く
Euler Tour に限らなくてもいいんですが、 DFS を非再帰で書くと若干大変ですよね。それの私なりの書き方です。先に方針を書くとこんな感じです。
- Python で非再帰 DFS で Euler Tour を書く
- DFS はスタックで管理する
- 追加するときは、行きがけ用と帰りがけ用の2つずつ追加する
ABC 163-F についても少しだけ書きます。
入力部分
$N$ 頂点の木が辺で与えられるとします。 1-indexed の場合は途中で $1$ 引いてください。
N = int(input())
X = [[] for i in range(N)]
for i in range(N-1):
x, y = map(int, input().split())
# x, y = x-1, y-1
X[x].append(y)
X[y].append(x)
再帰
まずは再帰で書いてみます。 ET は Euler Tour の頭文字です。各頂点を処理する際は
- リストに追加 → 子たちを処理 → リストに追加
をすれば良いですね。
done = [0] * N
ET = []
def dfs(i):
done[i] = 1
ET.append(i) # 開始時にリストに追加
for j in X[i]:
if done[j]: continue
dfs(j)
ET.append(i) # 終了時にもリストに追加
dfs(0)
print("ET =", ET)
コードは簡潔なんだけど、再帰はなるべく避けたいところです。
ここから下では、上のコードに相当するものを非再帰で書きます。ポイントは 開始時（行きがけ） の処理と 終了時（帰りがけ） の処理です。
非再帰
非再帰 DFS はスタックで管理するのが良いですね。
ただし、行きがけ・帰りがけの両方で処理が必要なので、スタックに入れる際は2つずつ入れます。具体的には、i番目の頂点を入れるときは、 i と ~i を入れます（ ~i は -i-1 と同じです）。 "~" が分かりにくければタプルで (1, i) と (2, i) にするとか、 i * 2 と i * 2 + 1 でもよいです。とにかくはじめか終わりかの情報と i が復元できるように追加すればよいです。 あるいは 1, i, 2, i のように分けて追加する方法もあります。
i を行きがけの処理用、 ~i を帰りがけの処理用とすると、スタックへは ~i → i の順に追加します。「再帰」部分は行きがけの部分に書きます。
例えば、 i の処理中に j が追加される場合は、スタックは次のように変化します。
[~i, i] → [~i] → [~i, ~j, j] → [~i, ~j] → [~i] → []
右から順に見て行って、非負の場合は行きがけの処理、負の場合は帰りがけの処理をする感じですね。
コードで書くとこんな感じ。
def EulerTour(n, X, i0):
done = [0] * n
Q = [~i0, i0] # 根をスタックに追加
ET = []
while Q:
i = Q.pop()
if i >= 0: # 行きがけの処理
done[i] = 1
ET.append(i)
for a in X[i][::-1]:
if done[a]: continue
Q.append(~a) # 帰りがけの処理をスタックに追加
Q.append(a) # 行きがけの処理をスタックに追加
else: # 帰りがけの処理
ET.append(~i)
return ET
print(EulerTour(N, X, 0))
あとは他にも処理があれば適当に行きがけ・帰りがけにする処理を追加すれば良いです。
帰りがけを入れない方式
ところで、 Euler Tour では行きがけと帰りがけにリストに追加すると言いましたが、 帰りがけの方はいらない場合が多い と思いませんか？私は思います。
そんなときは無理に両方入れる必要はないですね。帰りの追加をやめれば良いです。コードもすっきり、デバッグもしやすい、処理も高速化される、ということでおすすめです。
def EulerTour(n, X, i0):
done = [0] * n
Q = [~i0, i0] # 根をスタックに追加
ET = []
while Q:
i = Q.pop()
if i >= 0: # 行きがけの処理
done[i] = 1
ET.append(i)
for a in X[i][::-1]:
if done[a]: continue
Q.append(~a) # 帰りがけの処理をスタックに追加
Q.append(a) # 行きがけの処理をスタックに追加
else: # 帰りがけの処理
pass # ET.append(~i) # ←これは使わないなら外してOK
return ET
print(EulerTour(N, X, 0))
コード全体
各頂点について、開始時番号と終了時番号が欲しいですよね。他にももろもろ入れています。
コメントも含めて私のライブラリそのままです。
N = int(input())
X = [[] for i in range(N)]
for i in range(N-1):
x, y = map(int, input().split())
X[x].append(y)
X[y].append(x)
def EulerTour(n, X, i0):
# Xは破壊してXとPができる
P = [-1] * n
Q = [~i0, i0]
ct = -1
ET = []
ET1 = [0] * n
ET2 = [0] * n
DE = [0] * n
de = -1
while Q:
i = Q.pop()
if i < 0:
# ↓ 戻りも数字を足す場合はこれを使う
# ct += 1
# ↓ 戻りもETに入れる場合はこれを使う
# ET.append(P[~i])
ET2[~i] = ct
de -= 1
continue
if i >= 0:
ET.append(i)
ct += 1
if ET1[i] == 0: ET1[i] = ct
de += 1
DE[i] = de
for a in X[i][::-1]:
if a != P[i]:
P[a] = i
for k in range(len(X[a])):
if X[a][k] == i:
del X[a][k]
break
Q.append(~a)
Q.append(a)
return (ET, ET1, ET2)
ET, ET1, ET2 = EulerTour(N, X, 0)
print("ET =", ET) # Pathのi番目の頂点番号
print("ET1 =", ET1) # Start
print("ET2 =", ET2) # End
ET1 と ET2 に、それぞれ各頂点の開始時番号と終了時番号が格納されます。
DE は depth 、深さです。これもいらなければ消して OK です。
ABC 163-F
問題は こちら
色 i について見るときは、 i で塗られていない頂点たちを連結成分に分けて、各成分の個数を $x$ とすると $x(x+1)/2$ の和みたいなのを求めればよいです。
Euler Tour 順に見て、各頂点ではそれより下でその頂点より下ですでに使ったやつの個数を引いておけば良いです（日本語が下手い）。詳細はコードを参照してください。
（きれいなコードでもないので）細かいところを見る必要はないですが、「行きがけ」と「帰りがけ」に処理を入れられるということが分かって頂ければ十分です。
2020年4月21日：投稿
2020年4月21日（同日）：「帰りがけを入れない方式」と 「ABC 163-F」 について追記