DFS算法始终如一地寻找顶点少于最大值的路径

Question

我正在用dfs解决一个编程问题。tldr是这样的:在坐标x，y上有n头牛。它们可以在它们的“可发声”半径p内与其他牛交流。仅仅因为牛a可以与牛b交流，并不意味着b可以在没有足够的p的情况下进行交流。如果一条消息从任何一头牛开始，那么它能够到达的最大牛数量是多少？牛可以将信息从一头牛传递到另一头牛。例如。如果b能听到a，c不能听到a，但能听到b，那么b可以将信息从a传递到c，所以在这种情况下，3头牛听到了信息。以下是一个输入示例：

4
1 3 5
5 4 3
7 2 1
6 1 1

第一行是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)。