単純有向グラフの非循環性のテスト

Question

単純な有向グラフの非循環性をテストするために、私はデプスファーストサーチアルゴリズムを使用しました。いくつかのテストケースでは、私のコードは正常に動作しますが、誤った動作をすることもあります。オンラインジャッジサーバーは私に "ある場合には、あなたは間違った答えを持っています。"しかし、どの場合に失敗するか分かりません。テストケースは表示されません。私のコードは以下の通りです（Python3で書かれています）。

def get_graph(): 
    graph = {} 
    numofn, numofe = map(int, input().split()) 
    for i in range(1, numofn+1): 
     graph[i] = [] 
    for i in range(numofe): 
     s, e = map(int, input().split()) 
     graph[s].append(e) 
    return graph 

def dfs(v, visited, graph): 
    """ 
    input: current vertex v and list of visited node and graph 
    output: if acyclic 0 else 1 
    """ 
    if v in visited: 
     return 1 
    visited.append(v) 
    for next in graph[v]: 
     return dfs(next, visited, graph) 
    return 0 


def test_acyclicity(graph): 
    """ 
    input: graph 
    output: 1 if acyclic else -1 
    """ 
    for s in graph.keys(): 
     if dfs(s, [], graph) == 1: 
      return -1 
    return 1 

if __name__ == "__main__": 
    N = int(input()) 
    for i in range(N): 
     input() 
     graph = get_graph() 
     if i == N-1: 
      print(test_acyclicity(graph)) 
     else: 
      print(str(test_acyclicity(graph)) + " ", end='') 

ここに入力があります。

3 

2 1 
1 2 

4 4 
4 1 
1 2 
2 3 
3 1 

4 3 
4 3 
3 2 
2 1 

3つのテストケース（最初の3つは「3つのテストケースがある」という意味です）があり、このフォーマットに従います。

|V| |E| 
(list of non-weighted directed edges) 
... 

入力は次のように仮定されています：頂点は[1,2,3、..、|]です。

出力：

1 -1 1 

は、したがって、この場合には、私のプログラムがうまく動作します。しかし、裁判官のサーバーはそれが失敗すると私に伝えます。

私の質問は「どの場合にプログラムが失敗するのですか？」です。

---

ポストスクリプト

は述べSryheniのアドバイスによると、私は私のDFSの検索で自分のバグを修正。

def dfs(v, visited, graph): 
    """ 
    input: current vertex v and list of visited node and graph 
    output: if acyclic 0 else 1 
    """ 
    if v in visited: 
     return 1 
    visited.append(v) 
    for next in graph[v]: 
     ret = dfs(next, visited, graph) 
     if ret == 1: 
      return 1 
    return 0 

これはいくつかの小さなテストケースで機能しますが、グラフには1000個のノードと1000個のエッジがあるなど、大きなテストケースでは常に返されます。

Answer 1

私はこのラインでは、パイソンの専門家でないんだけど、あなたのDFS機能で：

for next in graph[v]: 
    return dfs(next, visited, graph) 

はこれが唯一の最初の子の値を返すと思いませんか？あなたのコードは、数1でノードからDFSを開始2に行き、そのノード番号2はこれ以上子供を持っていない参照してDFS 0を返します。この場合、

1 
3 3 
1 2 
1 3 
3 1 

：私は、次のテストケースを想像意味しますノード1の関数は、ノード3から始まるDFSを実行し、サイクルを見つけるのを完了するのではなく、値0を返します。

UPDATE：あなたのコードを印刷-1ながら、

1 

3 3 
1 2 
1 3 
2 3 

正しい出力が1です： このテストケースは、あなたの更新されたコードに失敗します。このテストケースをデバッグして、コード内の問題を見つけてください。上記の方法では

Answer 2

def dfs(v, visited, graph): 
    """ 
    input: current vertex v and list of visited node and graph 
    output: if acyclic 0 else 1 
    """ 
    if v in visited: 
     return 1 
    visited.append(v) 
    for next in graph[v]: 
     return dfs(next, visited, graph) 
    return 0 

、間違いはここにある：

if v in visited: 

たび、あなたはノードがすでに訪れているかどうかを確認するために、リスト全体を横断しています。dfsという単一の再帰呼び出しごとに、ほとんどはO(n)です。代わりにboolean visited arrayを維持して、ノードがすでにO(1)の時間に訪れているかどうかを知ることができます。これはすべての入力を処理する必要があります。

P.S：自分の問題を解決する場合は、正しい答えを記入してください。