Can anyone offer suggestions on how to tackle this problem?

PS: This came in an online assessment of Uber (India)

# | User | Rating |
---|---|---|

1 | tourist | 3947 |

2 | ecnerwala | 3654 |

3 | jiangly | 3627 |

4 | jqdai0815 | 3620 |

5 | orzdevinwang | 3612 |

6 | Benq | 3586 |

7 | Radewoosh | 3582 |

8 | Geothermal | 3569 |

8 | cnnfls_csy | 3569 |

10 | ksun48 | 3474 |

# | User | Contrib. |
---|---|---|

1 | awoo | 163 |

2 | maomao90 | 160 |

3 | adamant | 156 |

4 | atcoder_official | 155 |

5 | maroonrk | 153 |

6 | -is-this-fft- | 148 |

6 | SecondThread | 148 |

8 | Petr | 147 |

9 | nor | 145 |

10 | cry | 144 |

Can anyone offer suggestions on how to tackle this problem?

PS: This came in an online assessment of Uber (India)

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/06/2024 01:29:05 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Observe that any two nodes connected by an edge must belong to group with different parity (odd or even). So, if the graph has odd cycles, the answer doesn't exist.

Secondly, observe that if a node $$$i$$$ belongs to group $$$1$$$, all its neighbours must belong to group $$$2$$$. I can safely replace the group of node $$$i$$$ with group $$$3$$$. It won't make a difference. So, WLOG I can say that there is exactly $$$1$$$ node which belongs to group $$$1$$$.

Next, fix a node $$$j$$$ belonging to group $$$1$$$. Then, imagine assigning groups to nodes in increasing order. This seems similar as BFS! So, start a BFS with node $$$j$$$, and whenever you reach an unvisited node, just assign it the appropriate group number, more formally, if you reach unvisited node $$$u$$$ via node $$$v$$$, then assign the group of node $$$u$$$ as $$$g[v] + 1$$$, where $$$g[i]$$$ denotes group of node $$$i$$$, finally take the maximum group number among all the possible starting node $$$j$$$.

Complexity: $$$O(N*(N+M))$$$ where, $$$N$$$ is the no. of nodes and $$$M$$$ is the number of edges.