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

Check wether the graph is bipartite after adding each edge
Автор kushb30, история, 4 года назад, По-английски

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.

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

      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.

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

Look for: Checking bipartiteness online, here

→ Ответить