Module: 徹底的に検索します。 DFS

Problem

2/12

深さ優先検索 (DFS) は、グラフに関する主要なアルゴリズムの 1 つです。アルゴリズムは O(N + M) で実行されます。

まず、トップから始めて、このトップの子を考えます。まだ入力していない場合は、それらから DFS を開始します。

開始頂点 S から無向グラフの深さをトラバースし、頂点 < code>S を 1 行にスペースで区切ります。

最初の行には 3 つの数値 N - グラフの頂点の数、M - エッジの数、S - 開始バーテックス。次の M 行で、2 つの変数 U_i と V_i が提供されます 、グラフエッジの説明。入力内のすべての数字が 1000 を超えないこと。

DFS による走査の順序ですべての頂点を出力します。

上記のプログラムでは、 V[i][j] は、頂点 i と j の間にエッジがあることを意味し、配列 Visited このピークを訪れたかどうかをマークします。

インデントを示すには、4 つのスペースを使用します。

Python

Write the program below
def dfs(start):

n, m, s = map(int, input().split()) Visited = [False]*(n+1) V = [set() for i in range(n+1)] for i in range(m): u, v = map(int, input().split()) V[u].add(v) V[v].add(u) dfs(s)