ABC284E - Count Simple Paths

考え方

DFSでできる．

頂点に入ったときにフラグを立て，頂点を抜けるときにフラグを消す．

回答例（スタックでDFS）

頂点に入ったときと抜けるときは，行きがけと帰りがけに対応する．

スタックを使って行きがけと帰りがけを処理する方法は以下がある：
ABC220F - Distance Sums 2 - 競プロはじめました
非再帰 Euler Tour を Python でやる - Qiita

スタックから頂点vを取り出したときが行きがけ，頂点~vを取り出したときが帰りがけである．

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
    u, v = map(lambda x:int(x) - 1, input().split())
    G[u].append(v)
    G[v].append(u)

K = 0
stack = [~0, 0]
seen = [False] * N
while stack:
    cur = stack.pop()
    if cur >= 0:
        K += 1
        if K == 10 ** 6:break
        seen[cur] = True
        for chi in G[cur]:
            if seen[chi]:continue
            stack.append(~chi)
            stack.append(chi)
    else:
        if ~cur == 0:break
        seen[~cur] = False

print(K)

回答例（再帰でDFS）

実装は再帰関数のほうがわかりやすい．
Pythonではあまりやりたくない処理．
（間に合う処理が書けていない．．．）