Ok, I am in dangerous waters :)
I just began looking into popular graph interview questions and came across this classical one
to find if we can divide all the incompatible persons into 2 different SETs
Instead of just cramming up the solution, I really wanted to understand/learn about graphs so began searching for similar questions theories.
And now I am confused a bit :(
There was one question about finding a seating arrangement around a round table between incompatible CEOs. There it suggests creating a graph of compatible CEOs instead, and find a Hamiltonian Cycle. I could understand that since it's a round table, the cycle would give the solution.
Then, there is another similar question about creating a maximum compatible group from kids in 2 separate classes, some of whom hate each other. There it suggests using max flow to get the max number of pairs. Similarly the 'Grand Dinner' problem explained there
Then there is the original question, where I started from :) Here, what I think they are trying to do is given a condition (1 hates 2), they actually create 2 edges 1-->2 and 2-->1 and the solution suggests checking that all the cycles are even in length using the 2 color technique
I am wondering if this is a totally separate category of question or it can be converted to max flow question ? Will Hamiltonian path also come into picture ?
Or am I getting it all wrong :( and mixing bipartite/Hamiltonian/max flow