DFS Algorithm consistently finds path with less vertices than maximum

aceadams (59)
I'm solving a programming problem with dfs. The tldr is as follows: There are n cows at coordinates x, y. They can communicate to others within their radius of "voicability" p. Just because cow a can communicate to cow b, doesn't mean b can communicate back if it doesn't have sufficient p. If a message starts at any cow, what is the greatest number of cows it will be able to reach? Cows can relay messages from one to another. Ex. If b can hear a, and c cannot hear a but can hear b, b can relay info from a to c, so 3 cows hear the info in this case. Here is a sample input:
4
1 3 5
5 4 3
7 2 1
6 1 1
First row is N, following rows are a cow's x, y, and p. Here is my code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
#include <iostream>
#include <cmath>
using namespace std;
int n;
int best=0;
bool adj[201][201];
struct cow {
    int x, y, p;
    bool visited=0;
} cows[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, int cnt) {
    cows[cow1].visited=1;
    for (int i=1; i<=n; i++) {
        if (cnt>best)
        best=cnt;
        if ((!cows[i].visited)&&(adj[cow1][i])) {
            dfs(i, cnt+1);
        }
    }
    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++) {
        dfs(i, 1);
        for (int j=1; j<=n; j++) {
            cows[j].visited=0;
        }
    }
    cout<<best;
}


I'm not quite sure where the issue is, but I am sure it is within the dfs function, and not within the creation of the adjacency list. My code works only for the sample case. I'm essentially doing dfs on all n cases of starting cows for the message.
Last edited on
helios (17574)
You're not counting how many cows a given cow's message can reach, you're counting the maximum recursion depth, which is equivalent to the maximum cow hops a given cow's message will do starting from the initial cow.
Imagine this cow graph:
A -> B
A -> C -> E
A -> D
Your code will give 3 as a result, because that's the length of this linked list: A -> C -> E. In reality, it should return 4, because four cows can be reached from A: B, C, D, and E.
aceadams (59)
@helios, my code gives 3 for the sample case above, and that is the right answer. However, if I have the case where 2 cows are essentially mute and the other cow left is heard by everyone, it gives 2, and not the correct answer of 3. I'm not quite sure why.
Topic archived. No new replies allowed.