V_2's blog

[Solved]Need help in coloring a planar graph [Toph -Chor Tintin Tikri]
By V_2, 8 years ago, In English

Problem Link: Chor Tintin Tikri

Statement
My approach

Note: Actually the problem contain wrong statement .Here 0<=Edge<=5000 .

Input: 
4 6
1 2
1 3
1 4
2 3
2 4
3 4
           __1__
         _/  |  \_
       _/    |    \_
     _/   ___3__    \_
   _/   _/      \_    \
  2 ___/___________\___4

In this graph , every vertices is a part of some triangles. And Adjacent of nodes(1,2 4) make a cycle of odd length and thus the output will be 4.

And got many wrong answer using this approach. Can anyone suggest any hint please or solution ? Thanks in Advance.

My implementation
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Your solution is right. This problem contains wrong statement about the constraints . Here the number of edges can be 0. Consider this constraint.

→ Reply