Problem:


Score : 500 points

Problem Statement

Given is a connected undirected graph with N vertices and M edges. The vertices are numbered 1 to N, and the edges are described by a grid of characters S.
If S_{i,j} is 1, there is an edge connecting Vertex i and j; otherwise, there is no such edge.

Determine whether it is possible to divide the vertices into non-empty sets V_1, \dots, V_k such that the following condition is satisfied. If the answer is yes, find the maximum possible number of sets, k, in such a division.

Every edge connects two vertices belonging to two "adjacent" sets. More formally, for every edge (i,j), there exists 1\leq t\leq k-1 such that i\in V_t,j\in V_{t+1} or i\in V_{t+1},j\in V_t holds.

Constraints

2 \leq N \leq 200

S_{i,j} is 0 or 1.

S_{i,i} is 0.

S_{i,j}=S_{j,i}

The given graph is connected.

N is an integer.

Input

Input is given from Standard Input in the following format:

N
S_{1,1}...S_{1,N}
:
S_{N,1}...S_{N,N}

Output

If it is impossible to divide the vertices into sets so that the condition is satisfied, print -1.
Otherwise, print the maximum possible number of sets, k, in a division that satisfies the condition.

Sample Input 1

2
01
10

Sample Output 1

2

We can put Vertex 1 in V_1 and Vertex 2 in V_2.

Sample Input 2

3
011
101
110

Sample Output 2

-1

Sample Input 3

6
010110
101001
010100
101000
100000
010000

Sample Output 3

4



Sample input:
2
01
10


Sample output:
2

Submission status: Accepted

Solution code:
from collections import deque

def bfs(n,e,fordfs):
    W = [-1]*n
    W[e] = 0
    que = deque()
    que.append(e)
    len = [0]*n
    while que:
        now = que.popleft()
        nowv = W[now]
        nowlen = len[now]
        for ne in fordfs[now]:
            if nowv == W[ne]:
                return -1
#                print(-1)
#                exit()
            elif W[ne] == -1:
                W[ne] = (nowv+1) % 2
                len[ne] = nowlen+1
                que.append(ne)
    return max(len)

N = int(input())
data = [list(map(int, list(input()))) for i in range(N)]
v = [[] for i in range(N)]
maxlen = [0]*N

for i in range(N):
    for j in range(N):
        if data[i][j] == 1:
            v[i].append(j)
for i in range(N):
    maxlen[i] = bfs(N,i,v)


ans = max(maxlen)+1
if ans==0:
    ans = -1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from collections import deque
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)



def main():

    n = int(input())


    data = [list(map(int, list(input()))) for i in range(n)]
    fordfs = [[] for i in range(n)]
    for i in range(n):
        for j in range(n):
            if data[i][j] == 1:
                fordfs[i].append(j)


    def bfs():
        V = [-1]*n
        V[0] = 0
        que = deque()
        que.append(0)
        while que:
            now = que.popleft()
            nowv = V[now]
            for ne in fordfs[now]:
                if nowv == V[ne]:
                    print(-1)
                    exit()
                elif V[ne] == -1:
                    V[ne] = (nowv+1) % 2
                    que.append(ne)


    bfs()
    # print(data)
    G = csgraph_from_dense(data)
    d = floyd_warshall(G)
    d.tolist()
    M = 0
    for i in d:
        M = max(M, max(i))
    M = int(M)
    print(M+1)
    return
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from collections import deque
import sys


def input(): return sys.stdin.readline()[:-1]

n = int(input())
data = [list(map(int, list(input()))) for i in range(n)]
fordfs = [[] for i in range(n)]
for i in range(n):
    for j in range(n):
        if data[i][j] == 1:
            fordfs[i].append(j)

def bfs():
    V = [-1]*n
    V[0] = 0
    que = deque()
    que.append(0)
    while que:
        now = que.popleft()
        nowv = V[now]
        for ne in fordfs[now]:
            if nowv == V[ne]:
                print(-1)
                exit()
            elif V[ne] == -1:
                V[ne] = (nowv+1) % 2
                que.append(ne)

bfs()
# print(data)
G = csgraph_from_dense(data)
d = floyd_warshall(G)
d.tolist()
M = 0
for i in d:
    M = max(M, max(i))
M = int(M)
print(M+1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
N = int(input())
S = [list(map(int, input())) for i in range(N)]
G = [[float('inf')] * N for i in range(N)]

for i in range(N):
    for j in range(N):
        if S[i][j]:
            G[i][j] = 1


colors = [None] * N
stack = [(0, 1)]
while stack:
    n, color = stack.pop()
    colors[n] = color
    for i, cost in enumerate(G[n]):
        if cost == float('inf'):
            continue

        if colors[i] == colors[n]:
            print(-1)
            exit()
        else:
            if colors[i] is None:
                stack.append((i, color ^ 1))

for i in range(N):
    G[i][i] = float('inf')

for k in range(N):
    for i in range(N):
        for j in range(N):
            G[i][j] = min(G[i][j], G[i][k] + G[k][j])

for i in range(N):
    G[i][i] = 0

ans = max([max(g) for g in G])
print(ans + 1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from collections import deque
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
def solve():
    n=int(input())
    data=[list(map(int,list(input()))) for i in range(n)]
    fordfs=[[] for i in range(n)]
    for i in range(n):
        for j in range(n):
            if data[i][j]==1:
                fordfs[i].append(j)

    def dfs():
        V=[-1]*n
        V[0]=0
        que=deque()
        que.append(0)
        while que:
            now=que.popleft()
            nowv=V[now]
            for ne in fordfs[now]:
                if nowv==V[ne]:
                    print(-1)
                    exit()
                elif V[ne]==-1:
                    V[ne]=(nowv+1)%2
                    que.append(ne)
    
    dfs()
    # print(data)
    G=csgraph_from_dense(data)
    d = floyd_warshall(G)
    d.tolist()
    M=0
    for i in d:
        M=max(M,max(i))
    M=int(M)
    print(M+1)
    return



def main():

    solve()
    return
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
 
n=int(input())
l=[list(input()) for i in range(n)]
connection=[[] for i in range(n)]
for i in range(n):
  for j in range(n):
    if l[i][j]=='1':
      connection[i].append(j)
 
colors = [0]*n
def dfs(v,color):
    colors[v] = color
    for to in connection[v]:
        if colors[to] == color:
            return False
        if colors[to] == 0 and not dfs(to, -color):
            return False
    return True
 
def is_bipartite():
    return dfs(0,1)
if is_bipartite()==0:
  print(-1)
  sys.exit()

def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 and visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

ans=[]
for i in range(n):
  ans.append(max(bfs(i)))
print(max(ans)+1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
 
n=int(input())
l=[list(input()) for i in range(n)]
connection=[[] for i in range(n)]
for i in range(n):
  for j in range(n):
    if l[i][j]=='1':
      connection[i].append(j)
 
colors = [0]*n
def dfs(v,color):
    colors[v] = color
    for to in connection[v]:
        if colors[to] == color:
            return False
        if colors[to] == 0 and not dfs(to, -color):
            return False
    return True
 
def is_bipartite():
    return dfs(0,1)
if is_bipartite()==0:
  print(-1)
  sys.exit()
 
 
def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 or visitct!=n:
    ct+=1
    for i in range(len(next)):
      distance[next[i]]=ct
      visited[next[i]]=1
      visitct+=1
      for j in range(len(connection[next[i]])):
        if visited[connection[next[i]][j]]==-1:
          next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

ans=[]
for i in range(n):
  ans.append(max(bfs(i)))
print(max(ans)+1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
 
n=int(input())
l=[list(input()) for i in range(n)]
connection=[[] for i in range(n)]
for i in range(n):
  for j in range(n):
    if l[i][j]=='1':
      connection[i].append(j)
 
colors = [0]*n
def dfs(v,color):
    colors[v] = color
    for to in connection[v]:
        if colors[to] == color:
            return False
        if colors[to] == 0 and not dfs(to, -color):
            return False
    return True
 
def is_bipartite():
    return dfs(0,1)
if is_bipartite()==0:
  print(-1)
  sys.exit()
 

def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while visitct!=n:
    ct+=1
    for i in range(len(next)):
      distance[next[i]]=ct
      visited[next[i]]=1
      visitct+=1
      for j in range(len(connection[next[i]])):
        if visited[connection[next[i]][j]]==-1:
          next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
    
  return distance

ans=[]
for i in range(n):
  ans.append(max(bfs(i)))
print(max(ans)+1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
 
n=int(input())
l=[list(input()) for i in range(n)]
connection=[[] for i in range(n)]
for i in range(n):
  for j in range(n):
    if l[i][j]=='1':
      connection[i].append(j)
 
colors = [0]*n
def dfs(v,color):
    colors[v] = color
    for to in connection[v]:
        if colors[to] == color:
            return False
        if colors[to] == 0 and not dfs(to, -color):
            return False
    return True
 
def is_bipartite():
    return dfs(0,1)
if is_bipartite()==0:
  print(-1)
  sys.exit()
 
def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=[]
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.append(connection[next[i]][j])
    next=next2
    next2=[]
    
  return distance
 
ans=[]
for i in range(n):
  ans.append(max(bfs(i)))
print(max(ans)+1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

n=int(input())
l=[list(input()) for i in range(n)]
connection=[[] for i in range(n)]
for i in range(n):
  for j in range(n):
    if l[i][j]=='1':
      connection[i].append(j)

colors = [0]*n
def dfs(v,color):
    colors[v] = color
    for to in connection[v]:
        if colors[to] == color:
            return False
        if colors[to] == 0 and not dfs(to, -color):
            return False
    return True

def is_bipartite():
    return dfs(0,1)
if is_bipartite()==0:
  print(-1)
  sys.exit()

def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=[]
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 and visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.append(connection[next[i]][j])
    next=next2
    next2=[]
    
  return distance

ans=[]
for i in range(n):
  ans.append(max(bfs(i)))
print(max(ans)+1)

Submission status: Accepted

Solution code:
import scipy.sparse.csgraph as c,numpy
_,*s=open(0)
s=numpy.int8([list(t[:-1])for t in s])
m=c.floyd_warshall(s)
i=m[0]%2<1
j=i^True
print((s[i][:,i].any()|s[j][:,j].any()or~int(m.max()))*-1)

Submission status: Accepted

Solution code:
import scipy.sparse.csgraph as c,numpy
_,*s=open(0)
s=numpy.int32([list(t[:-1])for t in s])
m=c.floyd_warshall(s)
i=m[0]%2<1
j=i^True
print((s[i][:,i].any()|s[j][:,j].any()or~int(m.max()))*-1)

Submission status: Accepted

Solution code:
import scipy.sparse.csgraph as c,numpy
_,*s=open(0)
s=numpy.int32([list(t[:-1])for t in s])
m=c.floyd_warshall(s)
i=m[0]%2<1
j=i^True
print(s[i][:,i].any()|s[j][:,j].any()and-1or-~int(m.max()))

Submission status: Accepted

Solution code:
import scipy.sparse.csgraph as c,numpy
_,*s=open(0)
s=numpy.int32([list(t[:-1])for t in s])
m=c.floyd_warshall(s)
i=m[0]%2<1
j=i^True
print(s[i][:,i].any()|s[j][:,j].any()and-1or int(m.max()+1))

Submission status: Accepted

Solution code:
import scipy.sparse.csgraph as c,numpy
_,*s=open(0)
s=numpy.array([list(map(int,t[:-1]))for t in s])
m=c.floyd_warshall(s)
i=m[0]%2<1
j=i^True
print((s[i][:,i].any()|s[j][:,j].any())*-1or int(m.max()+1))

Submission status: Accepted

Solution code:
import scipy.sparse.csgraph as c,numpy
_,*s=open(0)
s=numpy.array([list(map(int,t[:-1]))for t in s])
m=c.floyd_warshall(s)
i=m[0]%2<1
j=i^True
print((s[i][:,i]<1).all()*(s[j][:,j]<1).all()*int(m.max()+1)or-1)

Submission status: Accepted

Solution code:
from numpy import*
from scipy.sparse import*
_,*s=open(0)
s=array([list(map(int,t[:-1]))for t in s])
m=csgraph.floyd_warshall(csr_matrix(s))
i=m[0]%2<1
j=i^True
print(all(s[i][:,i]<1)*all(s[j][:,j]<1)*int(m.max()+1)or-1)

Submission status: Accepted

Solution code:
from numpy import*
from scipy.sparse import*
_,*s=open(0)
s=array([list(map(int,t[:-1]))for t in s])
m=csgraph.floyd_warshall(csr_matrix(s))
i=m[0]%2<1
j=i^True
print(all(s[i][:,i]==0)*all(s[j][:,j]==0)*int(m.max()+1)or-1)

Submission status: Accepted

Solution code:
from numpy import*
from scipy.sparse import*
_,*s=open(0)
s=array([list(map(int,t[:-1]))for t in s])
g=csr_matrix(s)
m=csgraph.floyd_warshall(g)
i=m[0]%2<1
j=i^True
print(all(s[i][:,i]==0)*all(s[j][:,j]==0)*int(m.max()+1)or-1)

Submission status: Accepted

Solution code:
from subprocess import*
call(('python3','-c',"""
from numpy import*
from scipy.sparse import*
_,*s=open(0)
s=array([list(map(int,t[:-1]))for t in s])
g=csr_matrix(s)
m=csgraph.floyd_warshall(g)
d=m.max()
i=m[0]%2<1
j=i^True
print(all(s[i][:,i]==0)*all(s[j][:,j]==0)*int(d+1)or-1)
"""))

Submission status: Accepted

Solution code:
from numpy import*
from scipy.sparse import*
_,*s=open(0)
s=array([list(map(int,t[:-1]))for t in s])
g=csr_matrix(s)
m=csgraph.floyd_warshall(g)
d=m.max()
i=m[0]%2<1
j=i^True
print(all(s[i][:,i]==0)*all(s[j][:,j]==0)*int(d+1)or-1)

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
edge = [[] for i in range(n)]

for i in range(n):
    S = input()
    for j in range(n):
        if S[j] == '1':
            edge[i].append(j)


def is_bipartite(num_of_node, edge):
    colors = [-1]*num_of_node
    start = 0
    todo = deque([[start, 0]])

    while todo:
        node, color = todo.popleft()
        new_color = 1 - color

        for new_node in edge[node]:
            if colors[new_node] == -1:
                colors[new_node] = new_color
                todo.append([new_node, new_color])

            elif colors[new_node] == color:
                return False

            else:
                continue
    return True


def get_max_distance(start, num_of_node, edge):
    distances = [-1] * num_of_node
    distances[start] = 1
    todo = deque([[start, 1]])

    while todo:
        node, dis = todo.popleft()

        for new_node in edge[node]:
            if distances[new_node] == -1:
                distances[new_node] = dis + 1
                todo.append([new_node, dis+1])
            else:
                continue

    return max(distances)


if is_bipartite(n, edge):
    print(max([get_max_distance(x, n, edge) for x in range(n)]))
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

n = int(input())
l=[list(input()) for _ in range(n)]
es = [[] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if l[i][j]=="1":
            es[i].append(j)
colors = [0 for _ in range(n)]

def dfs(v,color):
    colors[v] = color
    for to in es[v]:
        if colors[to] == color:
            return False
        if colors[to] == 0 and not dfs(to, -color):
            return False
    return True

def is_nibu():
    return dfs(0,1)

if not is_nibu():
    print(-1)
    exit()



d = [[float("inf") for i in range(n)] for i in range(n)]

for i in range(n):
    for j in range(n):
        if l[i][j]=="1":
            d[i][j]=1

for i in range(n):
    d[i][i] = 0

def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

ans=0
dd=warshall_floyd(d)
for i in range(n):
    ans=max(ans,max(dd[i]))

print(ans+1)

Submission status: Accepted

Solution code:
import sys
from collections import deque
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
s = [[_ for _ in S()] for _ in range(N)]

root = [[] for _ in range(N+1)]
for i in range(N):
  for j in range(N):
    if s[i][j] == "1":
      root[i + 1].append(j + 1)
#print(root)

ans = -1
for i in range(1, N+1):
  Vnum = [-1 for _ in range(N+1)]
  Vnum[i] = 1

  queue = deque([i])
  while queue:
    #print(queue)
    x = queue.popleft()
    for j in root[x]:
      if Vnum[j] == -1:
        Vnum[j] = Vnum[x] +1
        queue.append(j)
      else:
        if Vnum[j] == Vnum[x] or abs(Vnum[j] - Vnum[x]) > 1:
          break
    else:
      continue
    break
  else:
    ans = max(ans, max(Vnum))

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
s = [[_ for _ in S()] for _ in range(N)]

root = [[] for _ in range(N+1)]
for i in range(N):
  for j in range(N):
    if s[i][j] == "1":
      root[i + 1].append(j + 1)
      root[j + 1].append(i + 1)
      s[j][i] = "0"
#print(root)

ans = -1
for i in range(1, N+1):
  Vnum = [-1 for _ in range(N+1)]
  Vnum[i] = 1

  queue = deque([i])
  while queue:
    #print(queue)
    x = queue.popleft()
    for j in root[x]:
      if Vnum[j] == -1:
        Vnum[j] = Vnum[x] +1
        queue.append(j)
      else:
        if Vnum[j] == Vnum[x] or abs(Vnum[j] - Vnum[x]) > 1:
          break
    else:
      continue
    break
  else:
    ans = max(ans, max(Vnum))

print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import *

sys.setrecursionlimit(10 ** 6)

def main():
    def judge(u=0,b=False):
        bt[u]=b
        res=False
        for ku in range(n):
            if not to[u][ku]:continue
            if bt[ku]==b:
                return True
            if bt[ku]==None:
                res|=judge(ku,not b)
        return res

    def bfs(u):
        hp=[]
        heappush(hp,(0,u))
        while hp:
            d,u=heappop(hp)
            for v in range(n):
                if not to[u][v]:continue
                if dis[v]!=-1:continue
                dis[v]=d+1
                heappush(hp,(d+1,v))

    n = int(input())
    to = [[c == "1" for c in input()] for _ in range(n)]
    bt=[None]*n
    if judge():
        print(-1)
        exit()
    ans=0
    for u in range(n):
        dis=[-1]*n
        dis[u]=0
        bfs(u)
        ans=max(ans,max(dis)+1)
    print(ans)
main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000)
inf = float('inf')

N = int(input())
ad = [[int(e) for e in list(input())] for _ in range(N)]

# 二部グラフ判定

# -1:未訪問, 0:黒, 1:白
visited = [-1] * N
flag = True

# 0を黒塗りでスタート
def dfs(v=0, color=0):
    visited[v] = color
    for nv, bit in enumerate(ad[v]):
        if not bit:
            continue
        ncolor = (color + 1) % 2
        if visited[nv] == -1:
            dfs(nv, ncolor)
        elif visited[nv] != ncolor:
            global flag
            flag = False

dfs()
if not flag:
    print(-1)
    exit()
    
def warshall_floyd(ad):
    N = len(ad)
    dist = [[inf] * N for _ in range(N)]
    for i, line in enumerate(ad):
        for j, p in enumerate(line):
            if p:
                dist[i][j] = 1
            if i == j:
                dist[i][j] = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

dist = warshall_floyd(ad)

ans = 0
for i, line in enumerate(dist):
    for j, d in enumerate(line):
        if d != inf and d > ans:
            ans = d
ans += 1
print(ans)

Submission status: Accepted

Solution code:
'''
二部グラフ判定
'''
INFTY = 10**13
def floyd():
    for k in range(N):
        for i in range(N):
            if d[i][k] == INFTY:
                continue
            for j in range(N):
                if d[k][j] == INFTY:
                    continue
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

def dfs(v, c):
    color[v] = c
    for i in G[v]:
        if color[i] == c:
            return False
        if color[i] == 0 and not dfs(i, -c):
            return False
    # ds[v] += d
    return True
def solve():
    for i in range(N):
        if color[i] == 0:
            if not dfs(i, 1):
                return False
    return True
N = int(input())
G = [[]for i in range(N)]
color = [0 for i in range(N)]
# ds = [1 for i in range(N)]
d = [[0 if i == j else INFTY for j in range(N)]for i in range(N)]
for i in range(N):
    S = input()
    for j, s in enumerate(S):
        if s == '1':
            G[i].append(j)
            d[i][j] = 1

ans = solve()
if ans:
    floyd()
    print(max([max(di)for di in d])+1)
    # print(max(ds))
else:
    print(-1)

Submission status: Accepted

Solution code:
def where(cond, A):
    return [ i for i in range(len(A)) if cond(A[i])]

N = int(input())
S = [ input() for _ in range(N) ]
uv = [ where(int, s) for s in S ]

ans = -1
for i in range(N):
    used = [False]*N
    used[i] = True
    cur = {i}
    nxt = set(uv[i])
    k = 1
    while nxt:
        k += 1
        prev = cur
        cur = nxt
        for c in cur:
            used[c] = True
        nxt = set()
        for u in cur:
            for v in uv[u]:
                if v in prev:
                    continue
                elif used[v]:
                    k = -1
                    break
                else:
                    nxt.add(v)
            else:
                continue
            break
        else:
            continue
        break
    else:
        if k > ans:
            ans = k

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**3)

n = int(input())
s = [list(map(int, list(input()))) for _ in range(n)]

c = [-1 for _ in range(n)]
e = [[] for _ in range(n)]
for i in range(n-1):
    for j in range(i+1, n):
        if s[i][j] == 1:
            e[i].append(j)
            e[j].append(i)

def dfs(x, p, b):
    c[x] = b
    for f in e[x]:
        if f != p:
            if c[f] >= 0:
                if c[f] == c[x]:
                    print(-1)
                    exit()
            else:
                dfs(f, x, (b+1)%2)


dfs(0, 0, 0)

inf = float('inf')

for i in range(n-1):
    for j in range(i+1, n):
        if s[i][j] == 0:
            s[i][j] = inf
            s[j][i] = inf

def warshall_floyd(d):
    for k in range(n):
        for i in range(n-1):
            for j in range(i+1, n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
                    d[j][i] = d[i][j]
    return d

s = warshall_floyd(s)

ans = 0
for x in s:
    ans = max(max(x), ans)

print(ans+1)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra
from collections import deque
import sys
input = sys.stdin.readline
def isbipart(n,graph):  
  colors = [0 for i in range(n)]
  stack = deque([(0,1)])
  while stack:
    v,color = stack.pop()
    colors[v] = color
    for to in graph[v]:
      if colors[to] == color:
        return False
      if colors[to] == 0:
        stack.append((to,-color))
  return True

def solve():
  n = int(input())
  graph = []
  for i in range(n):
    tmp = []
    s = input()
    for j in range(n):
      tmp.append(int(s[j]))
    graph.append(tmp)
  d = dijkstra(graph)
  #csgraphを変換
  newgraph = [[] for _ in range(n)]
  for i in range(n):
    for j in range(n):
      if graph[i][j] == 1:
        newgraph[i].append(j)
  ans = -1 * float("Inf")
  for i in range(n):
    for j in range(n):
      ans = max(ans,d[i][j])
  if isbipart(n,newgraph):
    print(int(ans)+1)
  else:
    print(-1)
solve()

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall
from collections import deque
import sys
input = sys.stdin.readline
def isbipart(n,graph):  
  colors = [0 for i in range(n)]
  stack = deque([(0,1)])
  while stack:
    v,color = stack.pop()
    colors[v] = color
    for to in graph[v]:
      if colors[to] == color:
        return False
      if colors[to] == 0:
        stack.append((to,-color))
  return True

def solve():
  n = int(input())
  graph = []
  for i in range(n):
    tmp = []
    s = input()
    for j in range(n):
      tmp.append(int(s[j]))
    graph.append(tmp)
  d = floyd_warshall(graph)
  #csgraphを変換
  newgraph = [[] for _ in range(n)]
  for i in range(n):
    for j in range(n):
      if graph[i][j] == 1:
        newgraph[i].append(j)
  ans = -1 * float("Inf")
  for i in range(n):
    for j in range(n):
      ans = max(ans,d[i][j])
  if isbipart(n,newgraph):
    print(int(ans)+1)
  else:
    print(-1)
solve()

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall


def main():
    n = int(input())
    s = [list(map(int, input())) for _ in range(n)]

    s = np.array(s)

    g = csgraph_from_dense(s)

    dist_mat = floyd_warshall(g).astype(np.int32)

    dist_max = dist_mat.max()

    a = np.where(dist_mat[0] % 2 == 0)
    b = np.where(dist_mat[0] % 2 == 1)
    bl = (s[a][:,a] == 0).all() and (s[b][:,b] == 0).all()

    ans = dist_max + 1 if bl else -1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
S = [None] * N

for i in range(0, N):
    S[i] = [int(s) for s in list(input())]


def local_max_level(S, N, n): # n is the starting vertex
    levels = [None] * N
    levels[n] = 0

    for l in range(0, N): # for each level l
        for i in range(0, N): # look at every vertex i
            if levels[i] == l: # which is at level l
                # scan column S[i]
                for j in range(0, N): # scan all vertices and look for adjacent vertex to i
                    if S[i][j] == 1: # vertex j is adjacent to i
                        if levels[j] == None:
                            levels[j] = l + 1

                        elif levels[j] == l - 1: continue
                        elif levels[j] == l + 1: continue
                        else:
                            return -1
    return max(levels)

def n_partite(S, N):

    M = 0
    for n in range(0, N):  # try starting with every vertex
        m = local_max_level(S, N, n)
        if m == -1: # not n-partite
            return -1
        else:
            M = max(M, m)
    return M + 1

print(n_partite(S, N))

Submission status: Accepted

Solution code:
import queue
import sys
from collections import defaultdict

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N = int(input())
        # S = [list(map(int, list(input().rstrip())))for _ in range(N)]

        edges = defaultdict(set)
        for i in range(N):
            for j, flag in enumerate(list(input().rstrip())):
                if int(flag):
                    edges[i + 1].add(j + 1)

        ans = -1
        for i in range(N):
            q = queue.Queue()
            colors = defaultdict(int)
            q.put((i + 1, 0))
            colors[i+1] = -1
            is_bipartite_graph = True
            distance = 0
            while not q.empty():
                node = q.get()

                edge = edges[node[0]]

                # 2部グラフ判定
                for to in edge:
                    if colors[to] == 0:
                        colors[to] = -1 * colors[node[0]]
                        q.put((to, node[1] + 1))
                        distance = max(distance, node[1] + 1)
                    elif colors[to] == colors[node[0]]:
                        is_bipartite_graph = False
                        break
                if not is_bipartite_graph:
                    break

            if is_bipartite_graph:
                ans = max(ans, distance + 1)

        print(ans)


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Accepted

Solution code:
N = int(input())
G = [[int(x) for x in input()] for k in range(N)]
es = [[] for k in range(N)]

for k in range(N):
    for l in range(N):
        if G[k][l] == 1:
            es[k].append(l)

#
# 二部グラフ判定by prdさん
#

#n個の頂点の色を初期化。0:未着色、1:黒、-1:白
colors = [0 for i in range(N)]

#頂点vをcolor(1 or -1)で塗り、再帰的に矛盾がないか調べる。矛盾があればFalse
def dfs(v,color):
    #今いる点を着色
    colors[v] = color
    #今の頂点から行けるところをチェック
    for to in es[v]:
        #同じ色が隣接してしまったらFalse
        if colors[to] == color:
            return False
        #未着色の頂点があったら反転した色を指定し、再帰的に調べる
        if colors[to] == 0 and not dfs(to, -color):
            return False
    #調べ終わったら矛盾がないのでTrue
    return True

#2部グラフならTrue, そうでなければFalse
def is_bipartite():
    return dfs(0,1) # 頂点0を黒(1)で塗ってDFS開始

if is_bipartite() == False:
    print(-1)
    exit(0)

# ワーシャルフロイドで距離を求める
D = [[float("inf") for k in range(N)] for l in range(N)]
for k in range(N):
    for l in range(N):
        if k == l:
            D[k][l] = 0
        elif G[k][l] == 1:
            D[k][l] = 1

for p in range(N):
    for q in range(N):
        for r in range(N):
            D[q][r] = min(D[q][r],D[q][p]+D[p][r])
ans = 0
for k in range(N):
    for l in range(N):
        ans = max(ans, D[k][l]+1)

print(ans)