BFSやDFSで使えるtipsを集める

ABCにおけるD問題ではグラフに関する問題がしばしば出題されます。
このグラフに対してBFSやDFSを用いる時に合わせて使われるテクニックを、見つかり次第書き加えていこうと思います。
あくまでリストアップに留めるつもりですので、詳しい解説を読みたい方は各自で調べてみてください。
問題と解法はなるべく載せておきますので、良ければ参考にしてください。

<br>
<br>

目次
・[非再帰DFS](https://qiita.com/demi-human/items/508316ce1f880c92d1b2#%E9%9D%9E%E5%86%8D%E5%B8%B0dfs)
・[多始点BFS](https://qiita.com/demi-human/items/508316ce1f880c92d1b2#%E5%A4%9A%E5%A7%8B%E7%82%B9bfs)
・[頂点倍化](https://qiita.com/demi-human/items/508316ce1f880c92d1b2#%E9%A0%82%E7%82%B9%E5%80%8D%E5%8C%96)
# 非再帰DFS
その名の通り、再帰関数を用いずにDFSを行います。
再帰は時間のかかる処理ですから、再帰を使わない事で高速化を図ります。結構速くなる上に簡単なので、習得しておくことをお勧めします。
実はBFSにおけるキューをスタックに変えれば実現できます。

https://atcoder.jp/contests/abc138/tasks/abc138_d

<details> <summary>解答(クリックで展開)</summary>

```python:
N,Q = map(int,input().split())

graph = [[]for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    
Query = [0 for i in range(N)]
for i in range(Q):
    p,x = map(int,input().split())
    Query[p-1] += x


# 非再帰DFS
def dfs(graph,Query):
    result = [0 for i in range(N)]
    visited = [False for i in range(N)]
    stack = [(0,0)]
    while len(stack) != 0:
        v,counter = stack.pop()
        visited[v] = True
        counter += Query[v]
        result[v] = counter
        for nb in graph[v]:
            if not visited[nb]:
                stack.append((nb,counter))
    return result

result = dfs(graph,Query)
print(" ".join([str(result[i]) for i in range(N)]))
```

</details>


# 多始点BFS
その名の通り始点が複数あるBFSです。
実装は拍子抜けするほど簡単です。
複数ある始点を全てキュー及び訪問済みリストに入れておくだけで実現できます。

https://atcoder.jp/contests/abc405/tasks/abc405_d

<details> <summary>解答(クリックで展開)</summary>

BFSの始点となる"E"がたくさんあります。
全部キューと訪問済みリストに入れましょう。
```python:
from queue import Queue

H,W = map(int,input().split())
Grid = [list(input()) for i in range(H)]
esc = []
for i in range(H):
    for j in range(W):
        if Grid[i][j] == "E":
            esc.append((j,i))

def bfs(Grid,esc):
    result = Grid.copy()
    que = Queue()
    visited = set()
    # queとvisitedに"E"の座標をすべてセット
    for e in esc:
        que.put(e)
        visited.add(e)
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    arrow = {(0,1):"^", (0,-1):"v", (1,0):"<", (-1,0):">"}
    while not que.empty():
        v = que.get()
        for i in range(4):
            nx, ny = v[0]+dx[i], v[1]+dy[i]
            if not (0 <= nx < W and 0 <= ny < H):
                continue
            elif Grid[ny][nx] == "#":
                continue
            elif (nx,ny) in visited:
                continue
            else:
                result[ny][nx] = arrow[(dx[i],dy[i])]
                que.put((nx,ny))
                visited.add((nx,ny))
    return result

result = bfs(Grid,esc)
for i in range(len(result)):
    print("".join(result[i]))
```

</details>



# 頂点倍化
1つの頂点の状態が複数考えられる場合に利用します。
各頂点に対して、考えられる状態の数だけ頂点の複製を行います。

https://atcoder.jp/contests/abc410/tasks/abc410_d

<details> <summary>解答(クリックで展開)</summary>

こちらの解答では頂点の複製は行っていないため頂点倍化とは言い難いです。とはいえ要点は同じです。
こちらの解法では状態ごとに頂点を複製する代わりに各頂点の過去の状態を記録しています。集合型を使っていますが、過去の状態を記録できるなら何でもかまいません。
```python
N,M = map(int,input().split())
G = [[] for i in range(N)]

for i in range(M):
    A,B,W = map(int,input().split())
    A -= 1
    B -= 1
    G[A].append((B,W))

def dfs(G):
    # 各頂点の状態を集合で記録
    condition = [set() for i in range(len(G))]
    condition[0].add(0)
    stack = [(0,0)]
    while stack:
        v,count = stack.pop()
        for nv,nw in G[v]:
            n_count = count^nw
            # conditionを用いて、計算済みかどうかの判断を行う
            if n_count in condition[nv]:
                continue
            else:
                # 状態を記録
                condition[nv].add(n_count)
                stack.append((nv,n_count))
    # 頂点Nの取りうる状態の内、最も良いものを選ぶ
    if condition[len(G)-1]:
        return min(condition[len(G)-1])
    else:
        return -1

print(dfs(G))
```

</details>