Check wether the graph is bipartite after adding each edge

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

Автор 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.

kushb30
4 года назад
5

Комментарии (5)

Написать комментарий?

swapnil159

4 года назад, # |

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

→ Ответить

kushb30

4 года назад, # ^ |

← Rev. 2 →

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

→ Ответить

swapnil159

4 года назад, # ^ |

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.

→ Ответить