ナビゲーションパス(グラフィックDFS)

完全なナビゲーション(遡及、ステータスツリー、エッジの切断)-深度優先ナビゲーションベース

に質問

ナビゲーションパス(グラフィックDFS)

方向図がある場合は、作成プログラムは1番からN番までのすべてのパスの整数を出力します.次の図では、1番から5番までの分岐数を示します.

1 2 3 4 5
1 2 5
1 3 4 2 5
1 3 4 5
1 4 2 5
1 4 5
全部で6種類あります.
グラフィックでは、パスとは、アクセスしたノードが重複してアクセスしないことを意味します.
■説明の入力
1行目には、頂点数N(2<=N<=20)と、幹線数Mが与えられる.そして、M行の間に接続情報が与えられる.
■出力説明
総指数を出力します.
■入力例1
5 9
1 2
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5
■出力例1
6

コード#コード#💻

import sys
#sys.stdin=open("input.txt", "rt")     # read text

def DFS(v):                            # vertex
    global cnt                         # 전역변수
    if v == n:
        cnt += 1
        for x in path:
            print(x, end= " ")
        print()
    else:
        for i in range(1, n+1):
            if g[v][i] == 1 and ch[i] == 0:     # v -> i 노드로 갈 수 있는가, 방문하지 않은 노드인가
                ch[i] = 1
                path.append(i)
                DFS(i)                          # 방문할 노드로 이동
                path.pop()
                ch[i] = 0                       # 백트래킹시 체크 해제

if __name__ == "__main__":
    n, m = map(int, input().split())
    g = [[0] * (n+1) for _ in range(n+1)]
    ch = [0] * (n+1)
    for i in range(m):
        a, b = map(int, input().split())
        g[a][b] = 1
    cnt = 0
    path = []                                   # 경로
    path.append(1)
    ch[1] = 1
    DFS(1)
    print(cnt)

リファレンス

インフラストラクチャ:Pythonアルゴリズム回答