[SWEA] 4871. [Python S/Wトラブルシューティング基本]4日目-グラフィックパス[D 2]

📚 質問する
V個またはV個のノードをE本の幹線に接続する方向性図に関する情報を提供する場合は、2つの特定のノードにパスがあるかどうかを判断するプログラムを作成します.
2つのノードの場合、パスがある場合は1を出力し、ない場合は0を出力します.
例えば、下図に1から6までの経路が見つかった場合、経路が存在するため、1が出力される.

ノード番号は1番から存在し、V個のノードでも幹線に接続されていない可能性があります.
[入力]
第1行は、試験用例数Tを与える.1≤T≤50
次の行から、テストボックスの最初の行はVおよびEを与える.5≤V≤50, 4≤E≤1000
テストケースの2行目からE行を経て,出発到着ノードとして幹線情報を提供する.
E行の後、経路の存在を確認する開始ノードSおよび到達ノードGが与えられる.
[出力]
各行に「#T」(Tはテストケース番号)を出力し、答えを出力します.
これはStackを使用したDFSの問題です.
幹線で接続された頂点間の関係を配列内のsetで表現します.
1つの頂点に接続されているものを配列の要素としてSet演算子で表します.
アクセスされていない頂点は、アクセスを確認することによって確認されます.
DFSブラウズとは異なり、必要な到着点に到達した時点で終了し、重複文を出力するように設定します.
📒 コード#コード#

T = int(input())
for tc in range(1, T + 1):
    V, E = map(int, input().split())
    arr = [set() for _ in range(V+1)]       # 인접리스트를 set로 표현
    for i in range(E):
        s, e = map(int, input().split())    # 정점 -> 정점을 arr에 넣는다
        arr[s].add(e)
    visited = [0 for _ in range(V+1)]       # 나왔는지 확인
    s, e = map(int, input().split())        # 확인할 경로의 출발점과 도착점
    stack = [s]     # stack에 출발점을 넣는다.

    while stack and visited[e] == 0:        # stack이 없거나 원하는 도착점까지 도달했는지 확인
        v = stack.pop()
        if not visited[v]:                  # 방문하지 않는 정점만 확인
            visited[v] = 1                  # 방문했음을 표시
            for v2 in arr[v]:               # 정점에서 연결된 정점들을 순회
                if not visited[v2]:         # 방문하지 않은 정점을 방문
                    stack.append(v2)        # stack에 담는다.

    if visited[e]:                          # 원하는 정점에 방문했는지 체크
        print(f'#{tc} 1')
    else:
        print(f'#{tc} 0')

🔍 結果:Pass