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

Правка en1, от 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.

Теги 1364d, graph, #bipartite, cycle

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский insider_pants 2020-06-15 18:43:38 918 Initial revision (published)