c++ - 我误解了吗？关于 DFS 的答案似乎被扭曲了

Question

答案是错误的我误解了吗？在 DFS 中，有人可以请教我到底在哪里犯了错误吗？我检查了程序中没有错误，但答案是错误的。这是我的测试用例

6
10
4 3
3 1
3 4
5 2
5 6
6 5
1 2
1 3
2 1
2 5
1

这是我的意见。

结果是1 2 5 6 3 4。

#include <bits/stdc++.h>
using namespace std;
const int N = 10000;
vector<bool> vis(N, -1);
vector<int> adj[N]; /// keep adj list
bool visited[N];
int dis[N] = {0};

void DFS(int start){
    cout << start << " ";
    vis[start] = true;
    for(int i=0;i<adj[start].size() ; i++){
        if(vis[i] == -1){
            DFS(i);
        }
    }
}
int main() {
    int edge, node;
    cin >> node;
    cin >> edge;
    for (int i = 0; i < edge; i++){
        int first,second;
        cin >> first;
        cin >> second;
        adj[first].push_back(second);
        adj[second].push_back(first);
    }
    int start_node;
    cin >> start_node;

    DFS(start_node);

    return 0;
}

标签： c++

Answer 1

你的 for 循环不好。它应该去

for (const auto elem : adj[start])
    {
        if(!vis[elem])
        {
            DFS(elem);
        }
    }

也就是说，您需要迭代 adj ELEMENTS，而不是元素数量。

迭代元素的其他方法是将您的 if 语句更改为

if(!vis[adj[start][i]])

但这会给您留下其他可能的错误，因此请坚持上述错误。

此外，您还有许多其他错误，例如未使用节点变量并且您有重复的边，但所有这些都可以通过一些练习来修复。

快乐学习！