Need help to prove my solution of last contest's D question

Revision en1, by insider_pants, 2020-06-15 18:43:38

The last contest's D question, I came up to a solution which got accepted by I do not have the proof the solution. What I did was, First I did a DFS to give colours to the node(here colours means the parity like in bipartite graphs) and maintain two sets for even parity and odd parity. Now, if i came up to any adjacent nodes which have same colour assigned, I just removed any node from the set, given that both nodes are in the set. Now for the answer, I checked whether the bigger set have atleast K / 2 elements or not. If yes, the print the answer and exit and if not, I did another dfs to find cycles, and print it if its length is atmax k.

Solution

Anyone with some proof or willing to discuss or even hack it will sure help me. Thanks.

Tags 1364d, graph, #bipartite, cycle

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English insider_pants 2020-06-15 18:43:38 918 Initial revision (published)