R2__D2's blog

Need Help On bipartite Graph

By R2__D2, history, 8 years ago, In English

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.

  • Vote: I like it
  • +6
  • Vote: I do not like it

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

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply