Without any removed edges there would be n! permutations.
Now when you remove m edges, the number of permutations reduce, by how much? We can find this by inclusion exclusion. Let f(mi) be number of permutations containing the edge mi. So for all edges, the total number of permutations we have is given by
f(m1) + f(m2) + f(m3) + … - f(m1 & m2) - f(m1 & m3) - … + f(m1 & m2 & m3) and so on.
Now to find, f(mi1 & mi2 & mi3 & …) we can observe 2 things :
If these edges form a cycle they do not appear in any permutation
If a node in any of these edges has degree more than 2, it cannot appear in any permutation
After checking these two condition it’s simple. We only have to count the number of components obtained by combining edges. Answer for f will be :
@rishabh.jain9196 Because you are using stl function next_permutation which is taking too much time.You may implement your own permutation generator to pass first subtask.
@rishabjain9196, here is a link to my solution for 25 points which exactly uses for ides for graph using adjacency matrix. CodeChef: Practical coding for everyone
The name was a giveaway in my case. No mention of a Salesman in the problem led me to work on a dp solution similar to the Travelling Salesman Problem.
I solved by the combination of bitmask , dfs , inclusion-exclusion principle ;
Subtask1 got accepted , while as for the remaining , it is giving wrong answer .
below is the link of the solution ; could some point out the bug in the code ?
next_permutation(v,v+n) will run n! times. so your code complexity is n*n! which is too high to pass in 1 sec for n>10. Your code could have passed the first subtask if you had not included the statement f=f%1000000007 which also takes a lot of time to execute. Also this line is not necessary for the first subtask as your ans will never exceed 1000000007 in the first subtask