I was able to solve this using greedy…
From each node i tried to find minimum size cycle and remove it and continue that thing…
It feels to be right (but it’s greedy) can there be any counter case for my code
https://www.codechef.com/viewsolution/32751065
Thanks
You can try making a code that creates random testcases and compare your solution with setter’s solution. That’s how i found the testcase in the comments above
I also started enlarging the cycle by free swaps. Then I used dp with bitmask to split the cycles and check which of them gave me the minimum number of non-free swaps. It also got AC, but then I created some random testcases and compared my solution with the setter’s solution and it seems that this approach is wrong (or maybe I didn’t implemented it well). It appears that the solution also depends on how you enlarge the cycle. If you just enlarge it with the first free swaps you find, then I think there could be created a counterexample.
If we notice, in whatever order we merge cycles (enlarging), the final cycle is always the same. and one more thing, if any value can be swapped to correct position with free swaps, I do it before enlarging, so the enlarged cycle doesn’t have any free swaps between consecutive elements.
The split order can determine the outcome, so I am checking all the possible ways I can split the cycle using all the swaps with-in cycle. and then recursively calling it. Can you share your solution link, so I can go through it.
Thanks
Ashok
Here’s the case for you:
1
18 7
14 15 16 13 2 17 5 10 8 7 6 12 4 18 1 11 9 3
1 4
9 16
1 11
18 5
12 6
3 16
5 14
This case was generated by a friend. This will fail for a lot of greedy approaches.
Correct answer is 11 
.
I had the same approach earlier, removing cycles at each node greedily, but then I randomized it. So it mostly outputs correct now.
Can anyone let me know the probability of my submission failing? 
I guess, you were lucky. Because your algorithm doesn’t guarantee the identification of maximum number of cycles. 
Consider the above graph of families all with equal weights 1. Your algorithm would wrongly choose cycle 012 first which leads to a total count of 2. But in reality the maximum number of cycles is 3.
Counter example -
1
9 3
5 4 6 7 9 8 2 3 1
1 7
2 8
3 9
Can you add more comments in your code please. Like why you made a structure , what is the function dfs doing, is it an abbreviation for Depth First Search. I am a beginner and it’s still hard for me to comprehend the editorial and their solution.
Thank You 
Can you please elaborate your approach.
Thankx in advance
I have commented for almost everything upto my knowledge except the DSU part.
You can read about DSU (Disjoint Set Union ) in
https://cp-algorithms.com/data_structures/disjoint_set_union.html
Sure , here is my submission : CodeChef: Practical coding for everyone
Just to save you some time, first i call the function “addpairs” to add “new free swaps” from the connected component.
Then I call the function “transform” , to enlarge the cycle (I used DSU) using only free swaps. And then for each cycle I used dp to calculate the answer.
Also, I think that the same elements will be in the enlarged cycle no matter how you enlarge it, but the order of this elements can be different and that could change your possibilities for the splitting process. At least in the way I implemented, I think this can return a wrong answer.
My code will fail in this case :
1
17 9
1 15 14 3 4 13 5 17 8 9 12 2 11 6 16 7 10
8 14
10 11
3 6
4 6
10 13
2 14
11 17
7 9
1 16
The correct answer is 9. And my code outputs 10 . Although, if I randomized the process of enlarging the cycle, it could get the correct answer (9) . That’s why I think that the order matters.
I think the way you have implemented addPairs, the function is not adding all the pairs, which are possible. you can use dfs or bfs to find all the connected nodes (through pairs) and then add all of them as pairs.
let’s chat over hangout and not spam this discuss thread.
my email id: ashok1113@gmail.com
can you provide your code link
CodeChef: Practical coding for everyone i need cases where my code fails.and want to know was my approach correct?
@harisisbatman Sir,sorry to disturb you but can you explain me the actions of ‘splitting the cycles’,‘finding maximum number of disjoint cycles’, that you have done? I am not able to understand also how bitmask dp is helping us…
I would be grateful if you can kindly help this beginner…
Thanks in advance
Sir, can you explain in a bit detailed manner what is all this enlarging of cycles you are talking about?
sir can explain code by some comment
@rajarshi_basu Sir,can you kindly explain why the setter’s solution is returning character in the get function()? and what is this char &ans in get function?And also why are we considering that total edges will be 18 max??Because n vertices can have nC2 edges here where every edge represents a possible swap and so maximum edges can be 18C2…
Anyone else also kindly help me if you have any knowledge of the above questions?
Thanks in advance