### Acclerated_Coder's blog

By Acclerated_Coder, history, 7 weeks ago, 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 impossible

Constraints 2 <= N <= 250

Input Format

First 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 0

Sample Input 1

4 0111 1011 1101 1110

Sample Output 1

-1

Explanation It is not possible to divide the cities into different groups by following the given constraints

Sample Input 2

2 01 10

Sample Output 2

2

Explanation City 1 can be in 1st group and city 2 can be in 2nd group, hence, max value of x is 2

Sample Input 3

3 011 100 100

Sample output 3

3

Explanation 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 mat

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 0

[output] integer Comments (1)
 » #include using namespace std; int G; bool checkOddCycle(int src, int V){ // checking bipartiteness 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