### Tony_Kakkar's blog

By Tony_Kakkar, history, 10 months ago,

 » 10 months 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.
•  » » 10 months 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