kushb30's blog

Check wether the graph is bipartite after adding each edge
By kushb30, history, 4 years ago, In English

Given multiple inputs of the edges in a graph such as(first line being number of connections):

4 1 2 2 3 5 6 1 5

I have to check that after each input whether the graph remains bipartite or not, we will just break if graph is non-bipartite. I think this is some graph coloring problem but I am unable to implement it, please help me by providing some algorithm to do so.

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Gears is a similar problem I think. It is most probably a more complicated version but includes this as a sub-problem. In this problem, gears get blocked when the graph is not bipartite. You can find the editorial here

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    swapnil159 Can you explain a bit,because i am unable to get there approach

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Suppose the edge to be added is between u and v.
      let p1=parent(u) and p2=parent(v)
      Here, by parent I mean the root of the subtree in which the node lies

      Now if u == p1 and v == p2 then you can simply add the edge and color them.
      else if u == p1 then you can simply add the edge and colour u accordingly
      else if v == p2 then you can simply add the edge and colour v accordingly
      else this follows-

      This is an interesting case,
      if p1 == p2 then you can check if u and v have the same colour or not
      else if u and v have opposite colours then simply add the edge
      else now you will have to change the colour of one of the trees, either of p1 or of p2. So always choose the subtree which is smaller in size and run a dfs to change all the colours and then add the edge.

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

Look for: Checking bipartiteness online, here

→ Reply