PROBLEM LINK:Author: Sergey Nagin DIFFICULTY:Medium PREREQUISITES:Matching, Gaussian Elimination PROBLEM:Determine whether there is any perfect matching. EXPLANATION:The problem setting is exactly same as the perfect matching. That is, find a subset of edges, there are no edges have common nodes and all nodes are covered by one edge. Since the graph is general, Blossom algorithm which can provide the maximum matching in O(VE) time is enough. Here, I would like to introduce a simpler way to solve this problem. Of course, it is not some strange greedy algorithms which may passed because we can't design cases for all wrong solutions (contestants are always creative :D). Anyway, let me introduce the simple solution  Tutte matrix. We can randomly choose the X[i][j]. Since we only need to check whether its determinant is zero, we can module all number during Gaussian Elimination (used to calculate the determinant) by a big prime, such as 10^9 + 7. Due to the randomness, we can solve this problem with a high probability. This solution is O(V^3 log MOD), where MOD is the big prime number we chosen. O(log MOD) is caused by the calculating the inverse or elimination by subtracting. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here.
This question is marked "community wiki".
asked 13 Jan '14, 15:12
showing 5 of 8
show all

I didn't use a prime modulus or anything like that. I just chose random integers as variables of the Tutte matrix, and did the GEM on doubles. Chances are small that there'd always be an undetectably nonzero (or zero) solution :D So I just try this an (insert constant here) amount of times and decide if the determinant can be nonzero. That being said, this problem would've done better in a short contest. It's hard to make worstcase test data, so wrong/slow solutions could pass, I think. Also, I solved it using Google Search algorithm, where I googled "perfect matching general graph" and got to Tutte matrix in no time. Overall, deciding if there's a perfect matching in a graph sounds like a standard problem (and therefore solvable with hardly any effort by finding the solution), so it is a bit of a waste. answered 13 Jan '14, 16:49
Wasn't bruteforce 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.
(13 Jan '14, 22:40)
Bruteforced it too.. But started with removing 1degree vertices as @m_a_y_a
(14 Jan '14, 06:19)
@mbrc Can you please explain what are you doing in your above code.
(27 Jun '14, 13:29)

Very interesting paper : http://web.eecs.umich.edu/~pettie/matching/Lovaszdeterminantsmatching1979.pdf On page 3 :
Thus choosing random values for the matrix between 1 and 1000 * M gives you a probabilistic answer >= 99.999%. :) answered 13 Jan '14, 22:54

Hi, I tried following strategy (though I never got it correct). Can anybody point out why is this algorithm incorrect? What is wrong? Before doing anything ensure that total no. of vertex is even otherwise output NO. Lets work on a single connected component of our graph. The same procedure can be applied to all the components.
Something like this pictorially : This is a very simple example. Here vertex 1 & 8 are the what I called leaf nodes. And edges {(1, 2), (7,8)} are what I called as leaf edges. Why is this strategy incorrect? answered 13 Jan '14, 16:34
1
I had initially thought of an approach exactly like yours. However i later realized that the the graph remaining is guaranteed to have atleast 1 cycle and will not always have exactly 1 cycle.There are many cases in which the remaining graph will consist of multiple cycles joined together for which your algorithm fails.
(13 Jan '14, 16:43)
understood thanks :)
(13 Jan '14, 16:47)
try this: 1 6 8 1 2 1 3 2 4 2 5 2 6 3 4 3 5 3 6 Answer is NO.
(13 Jan '14, 17:30)
1
@m_a_y_a , i used a similar approach , there is one more special case when you have no vertex of degree one (a cycle)  you just can't plainly tell that if the cycle is of even length then the current component can be matched Look at this case, graph with 10 vertices and 12 edges, [[1 2],[2 3],[1 3],[4 5],[5 6],[4 6],[7 8],[8 9],[7 9],[10 3],[10 5],[10 7]] The answer is NO even though this graph has no vertices with degree 0 or 1 and has an even length (contains cycles), you can't match this graph.
(13 Jan '14, 17:41)
In order to solve it, i used this approach, found an articulation point in the cycle and associated it with any one of its adjacent edges having odd cycle length and disconnect the graph. Then again follow the entire algorithm from the start on the remaining graph. Worked Out !
(13 Jan '14, 17:47)
@mecodesta can you please explain your solution
(13 Jan '14, 18:34)
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.
(13 Jan '14, 22:03)
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??
(14 Jan '14, 10:17)
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
(14 Jan '14, 13:53)
2
@jaggi1234 & @ddhruvkr, i'm not sure if your assumption is correct but I'm pretty sure that it'll fail in this case , Refer to the image and I'm sorry for the bad image :P Your Algo will remove the edge circled in blue , which disconnects the graph and it'll result in a 'NO', but the answer is 'YES' ! If this case was included you both should've got WA :P be glad you got AC :) Cheers !!
(15 Jan '14, 04:19)
1
@m_a_y_a, I've followed an algorithm similar to yours, except that when i encounter a cycle i do the following : > Check if the cycle has an articulation point, > If yes, then retain only the edge connecting the articulation point to ODD no of vertices and remove the other edges (if multiple edges with odd vertices are there , then select any one ) and then continue with your algorithm again, > If no, then just check how many vertices are there, if even then "YES" if odd then "NO". Thats pretty much it :)
(15 Jan '14, 04:24)
@mecodesta Indeed, my algo will fail in that test case. Thanks for pointing it out!
(15 Jan '14, 21:15)
showing 5 of 12
show all

I wanted to try Hungarian algorithm in this problem, but first had no time, and then got stucked with step 5, "Cover the zero elements with the minimum number of lines it is possible to cover them with.", but to do this I have to solve matching problem as a subproblem (recursion?)... In TopCoder tutorial, there is also:
Absolutely confused :D Any idea someone? answered 13 Jan '14, 16:11
The Hungarian algorithm is for bipartite graphs only (how do you convert a matrix to a multipartite graph, anyway?). And bipartite matching can be solved in O(N^3) using network flows, which is much simpler to code.
(13 Jan '14, 16:33)
My idea was to have 2N vertexes let say v1 and v2 for each v, and there is edge between v1[i] and v2[j] iff there is edge v[i] v[j] in original graph...
(13 Jan '14, 16:35)
Dunno. Sounds weird, it could correspond to a completely different graph.
(13 Jan '14, 17:50)

I think this problem tested google searching skills more than the programming knowledge. I know this was not intended but all one had to do to solve this problem was to figure out that it is a maximum matching problem in general graphs, search the same, find out about blossom algorithm and then search blossom algorithm code. Nevertheless it led me to many new algorithms and concepts. I read in norbert blum's paper how a O(m*root(n)) complexity algorithm can find maximum matching in a general graph. If anyone solved the problem using this, please share your code. answered 13 Jan '14, 17:33

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. answered 13 Jan '14, 22:13

Hello, Thanks for this very interesting problem and editorial... It was a joy to attempt to solve this problem during contest time and it is even better to read editorial and learn that there was a simple solution after all, which even used a standard algorithm. I'm very interested now in reading more about the Blossom Algorithm and how it works so I can try to adapt it to solve this problem. Do you happen to know of better resources to read about Blossom Algorithm besides wikipedia page? Best, Bruno answered 13 Jan '14, 15:47
http://discuss.codechef.com/questions/4138/minesreveditorial You can see it.
(13 Jan '14, 16:48)
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 :)
(13 Jan '14, 20:43)
3
Well, after googling and reading a bit, I got AC at last :D Maybe I write a tutorial about this when I have time ;)
(13 Jan '14, 21:27)

If we try to find if each of the connected components in the given graph has a Hamiltonian Path or not and also check if each of the components have even number of vertices, will this suffice to solve the problem ? Is this approach correct ? answered 13 Jan '14, 16:37
The approach will be correct however finding a Hamiltonian path in a graph is an NPcomplete problem so it would have been difficult to get it accepted within the time limits.
(13 Jan '14, 16:46)
I'm not trying to find the actual path but only checking if graph is Hamiltonian using Dirac's Theorem and that is not NPcomplete.
(13 Jan '14, 17:26)
1
@sayan_paul: No your algo won't work...If you consider the follwing testcase: 1 8 8 1 2 2 3 3 4 4 5 5 6 6 4 4 7 7 8. This test case will answer YES however it does not have any Hamiltonian Path. @xellos0: could you please look into my submission http://www.codechef.com/viewsolution/3236313. I used the Tutte Matrix concept. But it gave me wrong answer. I think somehow I am not setting the correct indeterminants of the Tutte Matrix. Please suggest what is the exact way to set the indeterminants. Thanks in advance.
(13 Jan '14, 17:38)
sambuddha: Are you only trying the determinant once? I did that at first, and got WA.
(13 Jan '14, 17:52)
@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???
(13 Jan '14, 18:00)
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 :D
(13 Jan '14, 18:44)
@sambuddha ya correct, my algo fails to take leaf nodes into consideration.
(13 Jan '14, 19:42)
@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
(13 Jan '14, 20:50)
showing 5 of 8
show all

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)? answered 13 Jan '14, 19:16

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... answered 13 Jan '14, 19:28

I got away with a recursive brute force solution. http://www.codechef.com/viewsolution/3173530 answered 14 Jan '14, 00:57

i can't understand ,,why is it giving wrong answer......(it runs fine on my compiler) ...... please help..... //www.codechef.com/JAN14/problems/SEAGRP/ include<iostream>using namespace std; include<stdio.h>define max 100int main()
{
int t,m,n,i,x,y;
scanf("%d",&t);
while(t)
{
scanf("%d%d",&n,&m);
int f[max]={0},a[max]={0};
for(i=0 ; i<m ; i++)
{
scanf("%d%d",&x,&y);
f[x]++;
f[y]++;
}
for(i=1 ; i<=n ; i++)
{
a[f[i]]++;
}
for(i=1 ; i<=n ; i++)
{
if(a[i]%2  f[i]==0)
break;
} answered 28 Jan '14, 15:27
i can't understand ,,what your code is doing......(it's unformatted) ...... please edit it so that it'd be readable.....
(28 Jan '14, 16:02)

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...
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.
Read the wiki, and Xij = rand(), Xji =  Xij. if i < j and (i, j) is an edge.
What do you mean by "Due to the randomness, we can solve this problem with a high probability" ...and also How to find determinant of matrix using gaussian elimination??Please tell.
@herman, if you perform the classic gaussian elimination, and if you put the matrix in Upper Triangular form, then, the determinant is simply the product of its diagonal.
The randomness means Xij should be chosen randomly
First Things FIRST:
1) Interesting problem (though a readymade algorithm was available).
2) Good that the problem statement did not mention any unwanted stuff like (no ODD cycles and all), else it would have been simple bipartate matching.
3) Tutte Matrix was a really interesting method.
Issues:
1) I was on this problem for many days, trying to implement blossom's algo flawlessly (Couldn't succeed though). And eventually many bruteforce and normal BPMatching solutions passed, definitely due to *lack of proper cases* not because their algo is apt.
2) Shangjingbo's comment which says they couldn't monitor all the solutions, wasn't convincing. So if you can neither design proper cases, nor monitor solutions which get accepted with flaws, why frame a problem ? That was disappointing due to improper testing.