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: Time Limit Exceeded

Solution code:

N = int(input())
S = [input() for _ in range(N)]

import sys
import queue

def getVlist(x):
    reslist = []
    for i in range(N):
        if int(S[x][i]): reslist.append(i)
    return reslist

ans = 0
adj_list = [[]for _ in range(N)]
for i in range(N):
    for j in range(i+1,N):
        if int(S[i][j]):
            adj_list[i].append(j)
            adj_list[j].append(i)


for kk in range(N):
    q = queue.Queue()
    visited = [False] * N
    cnt = 1
    visited[kk] = True
    q.put(kk)
    VC = 1
    while VC < N:
        nextv = []
        while not(q.empty()):
            nextv.append(q.get())
        nextv = list(set(nextv))
        #子の要素同士の連結チェック
        L = len(nextv)
        for i in range(L):
            if not(visited[nextv[i]]):
                visited[nextv[i]] = True
                VC += 1
            for j in range(i+1,L):
                if (int(S[nextv[i]][nextv[j]])):
                    print(-1)
                    sys.exit()
        
        for nv in nextv:
            for v in adj_list[nv]:
                if not(visited[v]):
                    q.put(v)
    
        cnt += 1
    
    ans = max(ans,cnt-1)
        
#
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

def f1(l1):
    ret = []
    for i in l1:
      for n,j in enumerate(li[i]):
        if j == 1:
            if n in used or n in l1:
                return False
            elif n in tree[nest-1]:
            	pass
            else:
                ret.append(n)
    return list(set(ret))


N = int(input())
li = []
for _ in range(N):
    li.append(list(map(int,list(input()))))
    
max_nest = 0
for i in range(N):
    tree = [[]]
    used = []
    tree.append([i])
    nest = 1
    while True:
        ret = f1(tree[nest])
        nest += 1
        if ret == False:
            break
        elif ret != []:
            tree.append(ret)
            used.extend(tree[nest-2])
        else:
            if max_nest < nest:
                max_nest = nest
            break
        
print(max_nest-1)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

graph=[]
for i in range(N):
  graph.append([])

for i in range(N):
  S=list(map(int,input()))
  for j in range(N):
    if S[j]==1:
      graph[i].append(j)
      
#print(graph)
max_set=-1
for i in range(N):
  node_list=[-1]*N
  #bfs
  d=1
  queue=[i]
  illegal=False
  while(True):
    new_queue=[]
    for q in queue:
      node_list[q]=d
      for qq in graph[q]:
        if node_list[qq]==-1:
          new_queue.append(qq)
        elif node_list[qq]!=d-1:
          illegal=True
          break
      
    if illegal:
      break
    elif len(new_queue)==0:
      #print(node_list,d)
      max_set=max(max_set,d)
      break
    else:
      #print(node_list,new_queue)
      queue=new_queue
      d+=1
      
print(max_set)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
#ts=time.time()
#sys.setrecursionlimit(10**6)
#input=sys.stdin.readline
show_flg=False
#=True

inf=float('inf')
n=I()
s=[[inf]*n for _ in range(n)]
g=[[] for i in range(n)]
for r in range(n):
    ri=list(input())
    for c in range(n):
        if ri[c]=='1':
            s[r][c]=1
            g[r].append(c)  

def wf(d):
    n=len(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

d=wf(s)
diam=-1
bg=0
ed=n-1
for r in range(n):
    for i,dist in enumerate(d[r]):
        if i==r:
            continue
        if diam<dist:
            diam=dist
            bg=r
            ed=i

v=[-1]*(n)
def bfs(x):
    p=deque()
    p.append((x,0))
    while p:
        c,depth=p.popleft()
        v[c]=depth
        for i in g[c]:
            if v[i]==-1:
                p.append((i,depth+1))
    return

bfs(bg)

for i in range(n):
    for nb in g[i]:
        if abs(v[nb]-v[i])!=1:
            print(-1)
            exit()
            show(i,nb,v[i],v[nb])

print(diam+1)
exit()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
#ts=time.time()
#sys.setrecursionlimit(10**6)
#input=sys.stdin.readline
show_flg=False
#=True

inf=float('inf')
n=I()
s=[[inf]*n for _ in range(n)]
g=[[] for i in range(n)]
for r in range(n):
    ri=list(input())
    for c in range(n):
        if ri[c]=='1':
            s[r][c]=1
            g[r].append(c)  

def wf(d):
    n=len(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

d=wf(s)
diam=-1
bg=0
ed=n-1
for r in range(n):
    for i,dist in enumerate(d[r]):
        if i==r:
            continue
        if diam<dist:
            diam=dist
            bg=r
            ed=i

v=[-1]*(n)
def bfs(x):
    p=deque()
    p.append((x,0))
    while p:
        c,depth=p.popleft()
        v[c]=depth
        for i in g[c]:
            if v[i]==-1:
                p.append((i,depth+1))
    return

bfs(bg)

for i in range(n):
    for nb in g[i]:
        if abs(v[nb]-v[i])!=1:
            print(-1)
            show(i,nb,v[i],v[nb])
            exit()

print(diam+1)

show(s)
show(wf(s))
show(diam,bg,ed)
show(v)

Submission status: Time Limit Exceeded

Solution code:

N = int(input())
S = [input() for _ in range(N)]

import sys
import queue

def getVlist(x):
    reslist = []
    for i in range(N):
        if int(S[x][i]): reslist.append(i)
    return reslist

ans = 0

for kk in range(N):
    q = queue.Queue()
    visited = [False] * N
    
        
    cnt = 1
    visited[kk] = True
    q.put(kk)
    
    while sum(visited) < N:
        nextv = []
        while not(q.empty()):
            nextv.append(q.get())
        nextv = list(set(nextv))
        #子の要素同士の連結チェック
        L = len(nextv)
        for i in range(L):
            visited[nextv[i]] = True
            for j in range(i+1,L):
                if (int(S[nextv[i]][nextv[j]])):
                    print(-1)
                    sys.exit()
        
        for nv in nextv:
            for v in getVlist(nv):
                if not(visited[v]):
                    q.put(v)
    
        cnt += 1
    
    ans = max(ans,cnt-1)
        
#
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

graph=[]
for i in range(N):
  graph.append([])

for i in range(N):
  S=list(map(int,input()))
  for j in range(N):
    if S[j]==1:
      graph[i].append(j)
      
#print(graph)
max_set=-1
for i in range(N):
  node_list=[-1]*N
  #bfs
  d=1
  queue=[i]
  illegal=False
  while(True):
    new_queue=[]
    for q in queue:
      node_list[q]=d
      for qq in graph[q]:
        if node_list[qq]==-1:
          new_queue.append(qq)
        elif node_list[qq]!=d-1:
          illegal=True
          break
      
    if illegal:
      break
    elif len(new_queue)==0:
      #print(node_list,d)
      max_set=max(max_set,d)
      break
    else:
      #print(node_list,new_queue)
      queue=new_queue
      d+=1
      
print(max_set)

Submission status: Time Limit Exceeded

Solution code:
import copy
def main():
    n = int(input())
    s = [list(map(int,list((input())))) for i in range(n)]
    k = []
    f = True
    for start in range(n):
        s_ = copy.deepcopy(s)
        group = [0]*n
        group[start] = 1
        v = [start]
        searched = set([start])
        mx_k = 2
        f = True
        while True:
            v_ = []
            for i in v:
                edge = s_[i]
                for j in range(n):
                    if edge[j] == 1:
                        if group[j] == 0:
                            v_.append(j)
                            group[j] = mx_k
                        elif not abs(group[j]-group[i])==1:
                            f = False
                            break
                searched = searched | set(v)
                if not f:
                    break
            if not f:
                break
            if len(searched) == n:
                k.append(mx_k-1)
                break
            v = copy.deepcopy(v_)
            mx_k += 1
    if k:
        print(max(k))
    else:
        print(-1)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = [[int(c) for c in input().strip()] for _ in range(n)]

def bfs(s, start):
    lengths = {start: 0}
    plan = [(i, 1) for i, c in enumerate(s[start]) if c == 1]
    while len(plan) > 0:
        vertex, length = plan.pop(0)
        if vertex in lengths:
            if (lengths[vertex] - length) % 2 != 0:
                return -1
        else:
            lengths[vertex] = length
            plan.extend([(i, length + 1) for i, c in enumerate(s[vertex]) if c == 1 and i not in lengths])
    return max(lengths.values())

bfs_result = 0
for start in range(n):
    res = bfs(s, start)
    if res < 0:
        bfs_result = -2
        break
    elif res > bfs_result:
        bfs_result = res
print(bfs_result + 1)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
edge=[[]for i in range(n+1)]
for i in range(1,n+1):
    s=list(input())
    for j in range(i,n+1):
        if s[j-1]=="1":
            edge[i].append(j)
            edge[j].append(i)



ans=0
for i in range(1,n+1):
    bubun=[[] for iii in range(n+1)]
    bubun[0].append(i)
    check=0
    for j in range(n):
        for k in bubun[j]:
            for y in edge[k]:
                if y in bubun[j-1]:
                    continue
                elif y in bubun[j]:
                    break
                else:
                    bubun[j+1].append(y)
            else:
                continue
            break
        else:
            continue
        break
    else:
        for ii in bubun:
            if ii:
                check+=1
        ans=max(ans,check)
if ans==0:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
ab = []
edge = [[] for _ in range(n)]
mat = [[1000] * n for _ in range(n)]
for i in range(n):
    s = input().rstrip()
    for j, ch in enumerate(s):
        if ch == "1":
            mat[i][j] = 1
            if j > i:
                edge[i].append(j)
                edge[j].append(i)
                ab.append((i, j))
for i in range(n):
    mat[i][i] = 0
for k in range(n):
    for i in range(n):
        for j in range(n):
            mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j])

ans = 0
for i in range(n):
    dq = deque()
    dist = [-1] * n
    dq.append((i, 0))
    ok = True
    while dq:
        v, d = dq.popleft()
        if dist[v] == -1:
            dist[v] = d
        elif dist[v] != d:
            ok = False
            break
        for item in edge[v]:
            if dist[item] == -1:
                dq.append((item, d+1))
    if ok:
        ans = max(ans, max(dist))

if ans > 0:
    print(ans + 1)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = [list(map(int, list(input()))) for _ in range(N)]

graph = [[] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if S[i][j] == 1: graph[i].append(j)

from collections import deque

ans_tmp = 0
possible = True
for home in range(N):
    iswhite = [None] * N
    q = deque([(home, False, 0)])
    while len(q) > 0:
        src, white, depth = q.popleft()
        # print("##", src, white, depth)
        iswhite[src] = white
        ans_tmp = max(ans_tmp, depth)
        for dst in graph[src]:
            # print("###", dst, iswhite[dst])
            if iswhite[dst] == None:
                q.append((dst, (white != True), depth + 1))
            elif white == iswhite[dst]:
                possible = False
                break
            else:
                continue
        #
        if possible == False:
            break
    
if possible:
    print(ans_tmp + 1)
else:
    # print("#", iswhite)
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
S = [list(map(int, input().strip())) for _ in range(N)]
G = [[] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if S[i][j] == 1:
            G[i].append(j)

#Bipartie Graph
def is_bibarate(G):
    vst = [False] * N
    que = deque([0])
    color = [0] * N
    color[0] = 1
    while len(que):
        p = que.popleft()
        for q in list(G[p]):
            if color[q] == 0:
                color[q] = - color[p]
                que.append(q)
            elif color[q] == color[p]:
                return False
            
    return True
                

        
#Warshal Floyd        
d = [[float('inf')] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j:
            d[i][j] = 0
        elif S[i][j] == 1:
            d[i][j] = 1
            
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])

wf_ans = max([max(r) for r in d]) + 1

if is_bibarate(G):
    print(wf_ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = [[int(c) for c in input().strip()] for _ in range(n)]

def bfs(s, start):
    visited = set([start])
    lengths = {start: 0}
    plan = [(i, 1) for i, c in enumerate(s[start]) if c == 1]
    while len(plan) > 0:
        vertex, length = plan.pop(0)
        vf = False
        if vertex in visited:
            if (lengths[vertex] - length) % 2 != 0:
                return -1
        else:
            visited.add(vertex)
            lengths[vertex] = length
            plan.extend([(i, length + 1) for i, c in enumerate(s[vertex]) if c == 1])
    return max(lengths.values())

bfs_result = 0
for start in range(n):
    res = bfs(s, start)
    if res < 0:
        bfs_result = -2
        break
    elif res > bfs_result:
        bfs_result = res
print(bfs_result + 1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
S = []
for i in range(N):
    s = list(input().strip())
    s_list = [int(k) for k in s]
    S.append(s_list)

count_max = 0
for i in range(N):
    flag = [-1]*N
    q = deque([i])
    flag[i] = 0
    count = 0
    while(q):
        count += 1
        for k in range(len(q)):
            v = q.popleft()
            for j in range(len(S[v])):
                if S[v][j] == 1 and flag[j] == -1:
                    flag[j] = count
                    q.append(j)
                elif S[v][j] == 1:
                    if flag[j]%2 != count%2:
                        print(-1)
                        sys.exit()
    count_max = max(count, count_max)
print(count_max)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = [[int(c) for c in input().strip()] for _ in range(n)]

def bfs(s, start):
    visited = [(start, 0)]
    plan = [(i, 1) for i, c in enumerate(s[start]) if c == 1]
    while len(plan) > 0:
        vertex, length = plan.pop(0)
        vf = False
        for v, l in visited:
            if v == vertex:
                if (l - length) % 2 != 0:
                    return -2
                else:
                    vf = True
                    break
        if not vf:
            visited.append((vertex, length))
            plan.extend([(i, length + 1) for i, c in enumerate(s[vertex]) if c == 1])
    return visited[-1][1]

print(max([bfs(s, start) for start in range(n)]) + 1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = []
for i in range(n):
    line = list(map(int, list(input())))
    s.append(line)

ans = -1

# @GDaigo さんのコメントより関数の追加 2017/03/18
def get_target_min_index(min_index, distance, unsearched_nodes):
    start = 0
    while True:
        index = distance.index(min_index, start)
        found = index in unsearched_nodes
        if found:
            return index
        else:
            start = index + 1

for k in range(n):
    unsearched_nodes = list(range(n)) # 未探索ノード
    distance = [300] * n # ノードごとの距離のリスト
    previous_nodes = [-1] * n # 最短経路でそのノードのひとつ前に到達するノードのリスト
    distance[k] = 0 # 初期のノードの距離は0とする

    while(len(unsearched_nodes) != 0): #未探索ノードがなくなるまで繰り返す
        # まず未探索ノードのうちdistanceが最小のものを選択する
        posible_min_distance = 300 # 最小のdistanceを見つけるための一時的なdistance。初期値は inf に設定。
        for node_index in unsearched_nodes: # 未探索のノードのループ
            if posible_min_distance > distance[node_index]: 
                posible_min_distance = distance[node_index] # より小さい値が見つかれば更新
        target_min_index = get_target_min_index(posible_min_distance, distance, unsearched_nodes) # 未探索ノードのうちで最小のindex番号を取得
        unsearched_nodes.remove(target_min_index) # ここで探索するので未探索リストから除去

        target_edge = s[target_min_index] # ターゲットになるノードからのびるエッジのリスト
        for index, route_dis in enumerate(target_edge):
            if route_dis != 0:
                if distance[index] > (distance[ target_min_index] + route_dis):
                    distance[index] = distance[ target_min_index] + route_dis # 過去に設定されたdistanceよりも小さい場合はdistanceを更新
                    previous_nodes[index] =  target_min_index #　ひとつ前に到達するノードのリストも更新

    marubatu = 1
    for i in range(n-1):
        if marubatu == 0:
            break
        for j in range(i+1, n):
            if distance[i] == distance[j] and s[i][j] == 1:
                marubatu = 0
                break
    if marubatu == 1:
        ans = max(ans, len(list(set(distance))))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)


def dfs(s):
    for t in g[s]:
        if dist[t] > -1:
            if (dist[s] + 1 - dist[t]) % 2 == 1:
                print(-1)
                exit()
            continue
        dist[t] = dist[s] + 1
        dfs(t)


n = int(input())
s = [list(input()) for _ in range(n)]
g = [[] for _ in range(n)]
mat = [[10**9] * n for _ in range(n)]
for i in range(n):
    mat[i][i] = 0
    for j in range(i + 1, n):
        if s[i][j] == '1':
            g[i].append(j)
            g[j].append(i)
            mat[i][j] = mat[j][i] = 1
dist = [-1] * n
dist[0] = 0
dfs(0)

for k in range(n):
    for i in range(n):
        for j in range(n):
            mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j])
ans = 0
for i in range(n):
    for j in range(n):
        ans = max(ans, mat[i][j])
print(ans + 1)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
table=[[float("inf")]*n for i in range(n)]
for i in range(n):
  s=input()
  for j in range(n):
    if s[j]=="1":
      table[i][j]=1
    
def warshall_floyd(d):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if d[i][k]+d[k][j]<d[i][j]:
          d[i][j]=d[i][k]+d[k][j]
        if d[i][j]<float("inf") and d[i][k]+d[k][j]<float("inf") and d[i][j]%2!=(d[i][k]+d[k][j])%2:
          return False
  return d

d=warshall_floyd(table)

if not d:
  print(-1)
else:
  ans=0
  for i in range(n):
    for j in range(i+1,n):
      ans=max(ans,d[i][j]+1)
  
  print(ans)

Submission status: Time Limit Exceeded

Solution code:

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

M = [[] for i in range(n)]
for i in range(n):
    for j in range(n):
        if S[i][j] == "1":
            M[i].append(j)
ans = -1
owa = 0
for i in range(n):
    a0 = -1
    Q = [[i, 0]]
    st = 0
    D = [-1] * n
    while st < len(Q):
        a = Q[st][0]
        d = Q[st][1]
        D[a] = d
        for x in M[a]:
            if D[x] == -1:
                Q.append([x, d+1])
            elif D[x] == d-1 or D[x] == d+1:
                continue
            else:
                owa = 1
                break
        if owa == 1:
            break
        st += 1
    if owa == 0:
        a0 = max(D)+1
    ans = max(ans, a0)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import queue

INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, a, b):
        self.graph[a].append(b)

    def get_nodes(self):
        return self.graph.keys()

class BFS(object):
	def __init__(self, graph, s, N):
		self.judge = "Yes"
		self.g = graph.graph
		self.Q = queue.Queue()
		self.dist = [INF] * N
		self.visit = ["No"] * N
		self.visit[s] = "Yes"
		self.dist[s] = 0
		self.Q.put(s)
		while not self.Q.empty():
			v = self.Q.get()
			for i in self.g[v]:
				if self.visit[i] == "No":
					self.dist[i] = self.dist[v] + 1
					self.Q.put(i)
					self.visit[i] = "Yes"
				else:
					if (self.dist[i] - self.dist[v]) % 2 == 0:
						self.judge = "No"

	def ans(self):
		return max(self.dist)

#処理内容
def main():
	#初期化
	N = int(input())
	L = []
	for i in range(N):
		S = list(input())
		L.append(S)
	G = Graph()
	for i in range(N):
		for j in range(i + 1, N):
			if L[i][j] == "1":
				G.add_edge(i, j)
				G.add_edge(j, i)
	#BFS
	jud = "Yes"
	A = - INF
	for i in range(N):
		bfs = BFS(G, i, N)
		A = max(bfs.ans(), A)
		if bfs.judge == "No":
			jud = "No"
	if jud == "No":
		print(-1)
	else:
		print(A + 1)

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
table=[[0]*n for i in range(n)]
for i in range(n):
  s=input()
  for j in range(n):
    if s[j]=="1":
      table[i][j]=1
    else:
      table[i][j]=float("inf")
def warshall_floyd(d):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if d[i][j]==float("inf") or d[i][k]+d[k][j]==float("inf"):
          d[i][j]=min(d[i][j],d[i][k]+d[k][j])
        else:
          if d[i][j]%2!=(d[i][k]+d[k][j])%2:
            return False
          else:
            d[i][j]=min(d[i][j],d[i][k]+d[k][j])
  return d

d=warshall_floyd(table)

if not d:
  print(-1)
else:
  ans=0
  for i in range(n):
    for j in range(i+1,n):
      ans=max(ans,d[i][j]+1)
  
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
graph = []
for _ in range(N):
	graph.append(list(map(int, input().strip())))

def check(graph):
	queue = [0]
	dists = [None] * N
	dists[0] = 0
	while queue:
		cur = queue.pop()
		dist = dists[cur] + 1
		col = graph[cur]
		for i in range(N):
			c = col[i]
			if c == 1:
				d = dists[i]
				if d == None:
					dists[i] = dist
					queue.append(i)
				else:
					if d % 2 != dist %2:
						return False
					elif d > dist:
						dists[i] = dist
						queue.append(i)
	return True

def search(graph, start):
	queue = [start]
	dists = [None] * N
	dists[start] = 0
	while queue:
		cur = queue.pop()
		dist = dists[cur] + 1
		col = graph[cur]
		for i in range(N):
			c = col[i]
			if c == 1:
				d = dists[i]
				if d == None or d > dist:
					dists[i] = dist
					queue.append(i)
	return max(dists)

if check(graph):
	diam = 0
	for i in range(N):
		d = search(graph, i)
		if d > diam:
			diam = d
	print(diam + 1)
else:
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
b=[[]for _ in range(n)]
d=[]
inf=float('inf')
for i in range(n):
  s=input()
  c=[]
  for j in range(n):
    if s[j]=="1":
      b[i]+=[(i,j)]
    c.append(1 if s[j]=="1" else inf)
  d.append(c)
from scipy.sparse.csgraph import bellman_ford
d=bellman_ford(d)
x=[-1]*n
x[0]=0
Q=b[0]
while Q:
  p=[]
  for i,j in Q:
    if x[j]<0:
      x[j]=x[i]^1
      p+=b[j]
    elif x[i]==x[j]:print(-1);exit()
  Q=p
print(int(max(map(max,*d)))+1)

Submission status: Accepted

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


N = int(input())
A = [[int(a) for a in input()] for _ in range(N)]
graph = np.array(A)
dist_mat = floyd_warshall(graph).astype(np.int64)
max_d = dist_mat.max()

B = np.where(dist_mat[0]%2 == 0)
C = np.where(dist_mat[0]%2 == 1)

bl = (graph[B][:, B] == 0).all() and (graph[C][:, C] == 0).all()



if bl:
    print(max_d + 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
n = int(input())
S = [list(input()) for i in range(n)]
e = [[] for i in range(n)]
count = [0]*n
for i in range(n):
    count[i] = S[i].count("1")
    for j in range(i+1,n):
        if S[i][j] == "1":
            e[i].append(j)
            e[j].append(i)

m = min(count)
ans = 0
for i in range(n):
    dis = [float("INF")]*n
    dis[i] = 0
    check = True
    l = [i]
    d = 0
    while check:
        nl = []
        for j in l:
            for nex in e[j]:
                if dis[nex] < d-1 or dis[nex] == d:
                    check = False
                    break
                if dis[nex] == float("INF"):
                    nl.append(nex)
                    dis[nex] = d+1
            if check == False:
                break
        if check == False:
            d = float("INF")
            break
        if nl:
            l = nl
            d += 1
        else:
            break
    if d != float("INF"):
        ans = max(ans,d+1)
print(ans if ans != 0 else -1)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(i):
    q = deque()
    q.append(i)
    dist = [0] * n
    dist[i] = 1
    maxdist = 1
    while q:
        p = q.popleft()
        for j in G[p]:
            if dist[j] == 0:
                dist[j] = dist[p] + 1
                maxdist = max(maxdist, dist[j])
                q.append(j)
            elif dist[p] == dist[j]:
                return
    global ans
    ans = max(ans, maxdist)
    return

n = int(input())
s = [list(input()) for _ in range(n)]
G = [[] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if s[i][j] == "1":
            G[i].append(j)
ans = -1
for i in range(n):
    bfs(i)
print(ans)

Submission status: Accepted

Solution code:
import collections

n = int(input())
g = [[] for i in range(n)]
for i in range(n):
    S =input()
    for j in range(i+1,n):
        if S[j]=="1":
            g[i].append(j)
            g[j].append(i)
def bfs(s):
    vis = [False]*n
    cnts=[0]*n
    que = collections.deque()
    cnt=1
    que.append((s,cnt))
    vis[s]=True
    cnts[s]=1
    while que:
        s,cnt = que.popleft()
        for node in g[s]:
            if not vis[node]:
                vis[node]=True
                cnts[node]=cnt+1
                que.append((node,cnt+1))
            else:
                if (cnts[node]+cnt)%2==0:
                    print(-1)
                    exit()
    return cnt
ans = 0
for node in range(n):
    ans = max(bfs(node),ans)
print(ans)

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq

n = ni()
g = [[] for i in range(n)]
for i in range(n):
    S =input()
    for j in range(i+1,n):
        if S[j]=="1":
            g[i].append(j)
            g[j].append(i)
visited=[False]*n
def bfs(s):
    que = collections.deque()
    que.append(s)
    visited[s]=True
    ls=[s]
    while que:
        s = que.popleft()
        for node in g[s]:
            if not visited[node]:
                visited[node]=True
                que.append(node)
                ls.append(node)
    return ls
def bfs2(s):
    vis = [False]*n
    cnts=[0]*n
    que = collections.deque()
    cnt=1
    que.append((s,cnt))
    vis[s]=True
    cnts[s]=1
    while que:
        s,cnt = que.popleft()
        for node in g[s]:
            if not vis[node]:
                vis[node]=True
                cnts[node]=cnt+1
                que.append((node,cnt+1))
            else:
                if (cnts[node]+cnt)%2==0:
                    print(-1)
                    exit()
    return cnt
#print(g)
ans = 0
for i in range(n):
    if not visited[i]:
        ls = bfs(i)
        #print(ans,ls)
        tmp = 0
        for node in ls:
            tmp = max(bfs2(node),tmp)
        ans+=tmp
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

N=int(input())
E=[[] for _ in range(N+1)]
P=[]

for a in range(1,N+1):
    S=input()
    for b in range(1,N+1):
        if S[b-1]=="1":
            E[a].append(b)

            if a<b:
                P.append((a,b))

M=-1
for a in range(1,N+1):
    Q=deque([a])
    T=[0 for i in range(N+1)]
    T[a]=1
    while Q:
        v=Q.popleft()
        for w in E[v]:
            if T[w]==0:
                T[w]=T[v]+1
                Q.append(w)

    F=True
    for (u,v) in P:
        F&=(abs(T[u]-T[v])==1)

    if F:
        M=max(M,max(T))

print(M)