DFS 算法始终找到顶点少于最大值的路径

Question

我正在用 dfs 解决编程问题。 tldr 如下所示：在坐标 x,y 处有 n 头奶牛。他们可以与 "voicability" p 半径范围内的其他人交流。仅仅因为奶牛 a 可以与奶牛 b 通信，并不意味着 b 在没有足够的 p 的情况下可以进行通信。如果一条消息从任何一头奶牛开始，它最多可以到达多少头奶牛？奶牛可以将信息从一个奶牛传递到另一个奶牛。前任。如果 b 可以听到 a，而 c 听不到 a 但可以听到 b，则 b 可以将信息从 a 传递给 c，因此在这种情况下有 3 头牛听到了信息。这是一个示例输入：

第一行是N，后面几行是牛的x、y、p。这是我的代码：

#include <iostream>
#include <cmath>
using namespace std;
int n;
int best=0;
int cnt=1;
struct cow {
    int x, y, p;
    bool visited=0;
} cows[201];
bool adj[201][201];
bool access (int a, int b) {
    return pow(cows[b].x-cows[a].x, 2)+pow(cows[b].y-cows[a].y, 2)<=pow(cows[a].p, 2);
}
void dfs(int cow1) {
    for (int i=1; i<=n; i++) {
        if (cnt>best)
        best=cnt;
        if ((!cows[i].visited)&&(adj[cow1][i])) {
            cnt=cnt+1;
            cows[i].visited=1;
            dfs(i);
        }
    }
    return;
}

int main () {
    cin>>n;
    for (int i=1; i<=n; i++) {
        cin>>cows[i].x>>cows[i].y>>cows[i].p;
    }
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            if (i!=j) {
            if(access(i, j)) {
                adj[i][j]=1;
            }
            else {
                adj[i][j]=0;
            }
        }
        }
    }
    for (int i=1; i<=n; i++) {
        cows[i].visited=1;
        dfs(i);
        cnt=1;
        for (int j=1; j<=n; j++) {
            cows[j].visited=0;
        }
    }
    cout<<best;
}

我不太确定问题出在哪里，但我确定它在 dfs 函数中，而不是在邻接列表的创建中。我的代码仅适用于示例案例。我本质上是在所有 n 个启动奶牛的情况下为消息做 dfs。

Answer 1

错误很简单。您测量最长的路径长度（实际上是奶牛数）。但问题是不同的，它是如何可以到达奶牛的。考虑三头牛的情况，其中一头可以被所有人听到，而其他的则没有声音。你的程序将回答 2（除非我错过了另一个错误），因为这是最长的链，但正确答案是 3（它是奶牛的数量 visited）。

DFS 算法始终找到顶点少于最大值的路径

DFS Algorithm consistently finds path with less vertices than maximum

c++

recursion

graph

directed-graph

depth-first-search