Why greedy fails in CHEFTRIP?

help
,
1

in CodeChef: Practical coding for everyone
I sorted vertices in descending order of their heights, and now I ran DFS on all unvisited vertices, if height of neighbors is less than parent, I made them in one set, using DSU. Now we have m independent components (Disjoint sets), with leader as the one with highest Height among the elements in the set.
Now for each query, if ‘x’ and ‘y’ lies in same set, return 1, else if both have unequal heights and are adjacent pairs return 1, else return 0.

here is my submission.
I am getting WA on this.
What’s wrong with this approach?

2

Here a case for which your output is wrong.

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

Also refer the editorial for the solution:

1 Like