@xellos0:I don’t understand… I simply calculated the determinant of the Tutte Matrix using Gaussian Elemination with random pivot technique.
How many times do I have to calculate the determinant??? Are you trying to say that I have to generate the Tutte matrix and calculate the determinant of each connected component seperately???
I’m not talking about connected components. Do you know what a randomized algorithm is? It’s something that can fail. The more test cases there are, the higher the chances of failing. The more times you try the same thing with different random values, the smaller the chance of failing. Maybe you just happened to choose the variables for which the determinant is 0, or maybe you just make a mistake somewhere 
what i could derive from other contestants solution that they were selecting vertex having minimum size and then marking it,can somebody expain this concept to me as editorial does not clarifies the concept clearly(atleast to me)?
Most of the accepted code used maximum matching for bipartite graph algorithm… But there may be general graph in test case so how they were passed…
Can someone point me to a better explanation about the Blossom algorithm or to give an explanation of it applied to this problem? I really want to code it now 
@sayan_paul My algorithm was to first eliminate all the leaf nodes using the steps mentioned by m_a_y_a above. Then You can use Dirac’s Theorem as you said above to detect Hamiltonian path
Well, after googling and reading a bit, I got AC at last
Maybe I write a tutorial about this when I have time 
3 Likes
But in case of a cycle or many cycles if we take the vertex with the minimum degree(say A) and then find from the vertexes connected with it(A) the one with the minimum degree and make a pair with those two.
Is this approach correct, because the solution is getting accepted using this approach.
I too did a lot of Google searching for this problem but couldn’t clearly follow the blossom algorithm so tried brute forcing and much to my surprise it got accepted. Initially check if the number of vertices are even. If true, then check if any vertex has degree less than one. If all vertices have degree greater than zero, then sort the vertices based on their degrees and then try to find a solution by removing edges. Try this for every possible combination until a certain set of edge removals satisfy.
1 Like
Wasn’t brute-force intended? My simple brute force solution got AC.
http://www.codechef.com/viewsolution/3179852
I had an analysis as to why it should get AC, but I fear its too vague
and not specific.
Very interesting paper :
http://web.eecs.umich.edu/~pettie/matching/Lovasz-determinants-matching-1979.pdf
On page 3 :
In fact, results of Zippel [17] imply that the probability of error is less than m / N.
Thus choosing random values for the matrix between 1 and 1000 * M gives you a probabilistic answer >= 99.999%.
4 Likes
I always thought that setter/tester is watching submitted solutions (not all of course) and adds some tests, when he sees, that there are solution not intended to be accepted…
I used exactly the same approach as @ddhruvkr and got AC. And this algo is giving correct answer on both the test cases mentioned above…
Can anyone think of a test case where this algorithm fails??
It is hard to monitor the submissions all the time. And also there are a lot of creative but wrong algorithms. Your understanding will be appreciated.
@shangjingbo can you tell me how to construct the Tutte matrix for a given graph. If you say it is random then for the same two graphs matrix can be same. how do you resolve that ??. Thanks.
I used a similar approach.
I made a recursive function which took a source node and then if an edge existed with next node , then marked both vertices as visited. Then if(new source is available, i.e some unmarked vertex is present) recur with that node as source.
else if(no vertex is found that is unvisited) return true, i.e graph can be reduced
If one complete traversal results to no solution than backtrack(unmark the visited node and continue with the next one).
It may not be the best way but it worked!!
http://www.codechef.com/viewsolution/3191837