Salesman Motu-Counter Testcase

general
1

The following example does not work on most of accepted submissions:
5 6 5
1 2
2 3
3 4
4 1
1 5
5 3
1
1
Is the following example valid?
Also please suggest a solution.

2 Likes
2

of course any input graph is valid but there is something wrong with the intended solution I think.

I submitted a code that ignores the constraint about not visiting any city twice and got AC
my code was just find the SCC’s, and if the size of the SCC that contains node u is greater or equal to K then the answer is “Yes”
else the answer is “No”
and I have a very big question mark on this, also you can check my comment under the problem statement

also I wonder what is the correct solution!

3

The example is clearly valid as per the question and I feel like I just got hacked.
No idea how to deal with it now?

4

@nitika_789 Please share the solution.

5

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

maximium solution fail on this TC.

6

here you go: solution
you can see that I’m just using the “dfs” function, all other stuff are useless
my solution is equivalent to this code

1 Like