Блог пользователя R2__D2

Need Help On bipartite Graph

Автор R2__D2, история, 8 лет назад, По-английски

Given N nodes and M edges. I have to color(only 2 colors) the nodes in such a way that at least one of the connected nodes of each nodes belong to different color. What will be the maximum number of nodes of same colored ? I am not sure about the range of N,M. I was working on bipartite graph. Suddenly I noticed it but failed to manage any idea to solve it.

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
8 лет назад, # |
← Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

You can run dfs at each component, then select the type of color with larger amount of node covered and add it to the answer. (If there exists a component which is not bipartite, return error.)

Edit: Oh.. I misinterpreted the constraints, hold on. Gotta rethink it a bit more.

Edit2: I am raising my white flag, I don't know and would like to know a decent solution for this problem. The corner cases just kills the greedy approach and the graph nature and the situation makes dp and point compression much more complicated.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    But How do I fix the color whenever I have a option to keep it same color as it's parent node?

    → Ответить