🤖

[AtCoder ABC213 D Takahashi Tour] Euler Tour with Stack(DFS)

2021/08/12に公開

Python

(問題ページ) AtCoder ABC213 D Takahashi Tour

ここでは、Euler TourをStackで行ってみた例を書いてます。再帰でやる方法が知りたい方は、公式解説などのほかのサイトを参照ください。

なお、実行時間(Python)を比較してみると
　Stackを使用: 732 ms
　再帰を使用: 1028 ms
となりました。
再帰のほうが、計算コストが増えるのかもしれません。

1.考え方

通常のDFSでは、Stackに探索する頂点を追加していくだけですが、今回の場合「戻り」の経路も追加する必要があります。

例えば頂点数2個で、現在、頂点Vにいる場合、

Stackには、stack = [ V(逆順), nv(正順) ] という感じで、次の頂点の情報を入れていくことになります。

探索先が複数ある場合(nv1→nv2→nv3の順で探索)は、

stack = [ V(逆順), nv3(正順), V(逆順), nv2(正順), V(逆順), nv1(正順) ]
という感じ。(Stackにはnv3→nv2→nv1の順で入れる)

2.頂点の情報

頂点に「正順」「逆順」を表す情報を付与する必要があります。
素直(?)に考えると、Stackに入れる際、パラメータを増やす方法が考えられます。例えばTrue、Falseで正順・逆順を表すことにして、
stack = [ (V, False), (nv3, True), (V, False), (nv2, True), (V, False), (nv1, True) ]
みたいな感じ。

ですが、今回は「ビット反転(~V)した値を「逆順」として扱う。」ことにします。
stack = [ ~V, nv3, ~V, nv2, ~V, nv1 ]
みたいな感じ。

これについては、以下のサイトを参考にしました。(というか、全体の考え方含めて、参考にしてます)
非再帰 Euler Tour を Python でやる

3.code

# -*- coding: utf-8 -*-
import sys


def main():
    N = int( sys.stdin.readline() )
    AB_list = [ list(map(int, sys.stdin.readline().split())) for _ in range(N-1) ]


    edge = [ [] for _ in range(N+1) ]
    # the number of vertex is 1-indexed

    for A,B in AB_list:
        edge[A].append(B)
        edge[B].append(A)

    for i in range(len(edge)):
        edge[i].sort()


    # dfs --------------------
    visited = [0]*(N+1)
    order = []

    visited[1] = 1
    stack = [1]  # [int]
                 # [vertex(1-indexed)]

    while stack:
        V = stack.pop()

        if V >= 0:
            order.append(V)
        else:
            order.append(~V)
            continue

        for nv in edge[V][::-1]:
            if visited[nv] == 0:
                visited[nv] = 1
                stack.append( ~V )
                stack.append( nv )
    # --------------------


    print( *order )


if __name__ == "__main__":
    main()

1.考え方

2.頂点の情報

3.code

Discussion