Help in DFS vs DFS

1

this discussion is related to problem Chipped Tree

As we know this problem is simply based on DFS traversing. During the contest i used following code for finding the depth of each node.
here

arr[MAX] // depth of nodes


int DFS(int u){
    arr[u] = 1;
    for(auto x : v[u])
        arr[u] = max(arr[u], DFS(x)+1);
    return arr[u];
}

and
edges inserted as following manner

int x, y; cin>>x>>y;
 v[x].push_back(y).

but this code is givind WA. I do not know why?

VS CODE
and on the other most of the programmer use following code for finding Depth.

int DFS(int u, int par = 0){
    arr[u] = 1;
    for(auto x : v[u])
       if(x != par)
        arr[u] = max(arr[u], DFS(x, u)+1);
    return arr[u];
}

and edges inserted in following way

int x, y; cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);

why?

2

looking for your ideas.

3

Please format the code because it is hurting my eyes and will definitely hurt the compiler. Thanks. :slight_smile:

3 Likes
4

It’s better if you post the link to your solution

3 Likes
5

ok changed code little bit

1 Like
6

i simply want to discuss DFS vs DFS and my code is working if i simply replace code for finding depth. so now it’s good time to discuss it.

7

Let us define * as the “is connected to” relation on the vertices of the tree.

(u, v) \in E(G) \implies (u, v), (v, u) \in *

This is the reason why we must do this

int x, y; cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);

Now, as we have included the parent of each node in the corresponding list,

arr[MAX] // depth of nodes


int DFS(int u){
    arr[u] = 1;
    for(auto x : v[u])
        arr[u] = max(arr[u], DFS(x)+1);
    return arr[u];
}

^ does not work as we are calling DFS on the parent node again.

:slightly_smiling_face:

8

but it is already given that it is an tree and more it is given that edges are N-1 so it cannot be disconnected and can you give an example for which my DFS is going false.

9

but i am not going to call parent again because i have taken edges as

int x, y; cin>>x>>y;
v[x].push_back(y);

os there is no back way from child to parent.

10

You might want to go through this. Adjacency list representation is what you are looking for. :slightly_smiling_face:

11

you just try it for different tree and you will feel that it is going to work correctly.
i already have understanding of graph theory.

12

Does it work on a chain, where the edges are given as input like this:
Number of nodes, N = 5

5 4
4 3
3 2
2 1
1 Like
13

it is not. but it is fault of codechef problem maker. why these guys not make proper statement like codeforces. in this statement there should be Graph instead of Tree. and that’s why i like codeforces.

14

Not really, the problem statement has absolutely no false information. After all, a chain is a tree.

Also, it was an external contest, if you take a look at the contest details.

You might want to go through this. I’ve explained every part of the code. :slightly_smiling_face:

1 Like
15

In the question it is no where written that u is the parent of v while taking input. It’s written that there is an edge between u and v in the tree. So it’s your mistake for assuming such condition.

3 Likes
16

it is true. problem at codeforces is really simple to understand but tricky to implement and codechef
has vice-versa game. same as previous year ACM-ICPC qualification round. they do not know difficulty distribution. you can also look for current Long chellange(top 6 problem are too easy and than difficulty of 7 and 8 problem is too high as compared to previous 6 problem).

17

You don’t know why or you don’t want to know? @raisinten gave a clear idea of where the bug lies, you’re just misinterpreting it. It is mentioned in the problem statement that u and v has an edge between them, you assumed that that edge is directed: that u has to be the parent of v. It is simply connectedness that is given, which means that any of the two can be the parent of the other. Don’t you think if your assumption were true, the level of each node is kind of embedded in the given graph (or well, the tree)? The entire structure of the tree would have been provided to you then, and very little work remains to be done if any. So, per that claim, your adjacency list is the real culprit here because you have cut down all the possible trees that can arise from the given input and reduced it down to what follows your assumption. Hope, it helps :slightly_smiling_face:

3 Likes
18

It physically hurts to see this idiot blaming the problemsetters for his own inability to comprehend the problem statement…

1 Like