AtCoder Beginner’s Contest 138 復習2

知り合いのコードがキューを使っててどっかで見た感じのコードだなと
思ったらグラフ関連のところで出てきたような書き方なんだな
無向グラフとして扱うわけだからそれも自然か

ちょっと思い出しがてら書いてみる

深さ優先から
スタックを使うからこれは普通のリストで

from sys import stdin, setrecursionlimit

def main():

    ...

    stack = []
    visited = [False] * (n + 1)

    stack.append((0, 1))

    while len(stack) > 0:
        parent, current = stack.pop()
        visited[current] = True
        count[current] += count[parent]
        for child in tree[current]:
            if not visited[child]:
                stack.append((current, child))

    print(*count[1:])

幅優先探索にするにはスタックをキューにするだけ（たぶん
こんどはdequeを使う

from collections import deque

...
    
    queue.append((0, 1))

    while len(queue) > 0:
        parent, current = queue.popleft()
        ...
                queue.append((current, child))

stackっていう名前にしてたのでqueueにしたのを除けば
pop()をpopleft()にしただけ

ということはこのままpopleft()をpop()にするとdeque版DFSになる
・・・速くなった？(1063ms→950ms)
標準のリストよりdequeのほうが速いの？
たまたま？

なんどか試してみたら、ばらつきはあるけどdequeのほうが速そう
メモリはさすがにdequeのほうが少し多く使うけどそれほどでもなかった
（極端にスタックが長くなるケースがなかっただけかもしれない）
スタック・キューはdequeほぼ一択でいいかな