Tony_Kakkar's blog

By Tony_Kakkar, history, 19 months ago, In English

problem link

Can anyone offer suggestions on how to tackle this problem?

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

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

| Write comment?
»
19 months ago, # |
Rev. 4   Vote: I like it +1 Vote: I do not like it

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.