### Tony_Kakkar's blog

By Tony_Kakkar, history, 6 weeks ago,

Can anyone offer suggestions on how to tackle this problem?

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

• +3

 » 6 weeks ago, # | ← Rev. 4 →   +1 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.
•  » » 6 weeks ago, # ^ | ← Rev. 3 →   0 #include using namespace std; int G[1001][1001]; bool checkOddCycle(int src, int V){ int colorArr[V]; for(int i=0;i q; q.push(src); while(!q.empty()){ int u=q.front(); q.pop(); if(G[u][u]==1){ return true; } for(int v=0;v group(n,0); vector vis(n,false); queue q; q.push(i); group[i]=1; vis[i]=true; while(!q.empty()){ int size=q.size(); while(size--){ int node=q.front(); q.pop(); for(int nei=0;nei
 » 6 weeks ago, # |   0 Its too blurry, the condition part. Please can you clear that
•  » » 6 weeks ago, # ^ |   0 We are given N cities and M bridges, each bridge connects two cities where it is possible to travel from any one city to any other city using a sequence of bridges.We want to divide these N cities into X disjoint groups G1, G2....Gx such that any one of the following conditions meet for any bridge that connects two cities A and B:if A belongs to Gi then B belongs to Gi+1 (1 <= i <= x-1) if A belongs to Gi then B belongs to Gi-1 (2 <= i <= x) Find the maximum value of X, or print -1 if such division is impossibleConstraints 2 <= N <= 250Input FormatFirst line contains N, an integer N line follows, one for each city, ith line contains N characters , where the jth character is 1 if there is a bridge between city i and j, else the character is 0Sample Input 14 0111 1011 1101 1110Sample Output 1-1Explanation It is not possible to divide the cities into different groups by following the given constraintsSample Input 22 01 10Sample Output 22Explanation City 1 can be in 1st group and city 2 can be in 2nd group, hence, max value of x is 2Sample Input 33 011 100 100Sample output 33Explanation City 2 can be in 1st group, city 1 can be in 2nd group and city 3 can be in 3nd group, hence, max value of x is 3[execution time limit] 3 seconds (java)[input] integer n[input] array.array.char matN line follows, one for each city, ith line contains N characters , where the jth character is 1 if there is a bridge between city i and j, else the character is 0[output] integer
•  » » » 6 weeks ago, # ^ |   0 Thanks bro