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).
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.
@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
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 be glad you got AC Cheers !!
@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
Interesting problem (though a ready-made algorithm was available).
Good that the problem statement did not mention any unwanted stuff like (no ODD cycles and all), else it would have been simple bi-partate matching.
Tutte Matrix was a really interesting method.
Issues:
I was on this problem for many days, trying to implement blossomâs algo flawlessly (Couldnât succeed though). And eventually many brute-force and normal BP-Matching solutions passed, definitely due to lack of proper cases not because their algo is apt.
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.
Cheers !!