agc 039 B - Graph Partition (python)

1,...,n のうちの頂点 i から bfs をはじめて最短何回で全頂点辿れるかを計測しつつ、i から１回で通れる頂点, 最短２回で通れる頂点,,, をリストに入れておく。
答えが -1 にならない条件は i から同じ回数で辿りつける任意の２頂点が辺を持たないことである。
この時答えは全頂点回るのにかかった回数となる。
あとはこの動作を 1,..., n まで試して答えの最大値を求めたらよい。

n = int(input())

g = [[] * n for i in range(n)]

for i in range(n):
  s = input()
  for j,si in enumerate(s):
    if si == '1':
      g[i].append(j)
      
from collections import deque

def bfs(s):
  que = deque()
  que.append((s,1))
  a[0].append(s)
  chk = [False]*n
  chk[s] =True
  cnt = 1
  while que:
      now,p = que.popleft()
      if cnt == n:
        break
      for i in g[now]:
          if not chk[i]:
            a[p].append(i)
            chk[i] = True
            cnt += 1
            que.append((i,p+1))
          
ans = -1
for i in range(n):
  a = [[] for i in range(n+1)] # 同じ回数でつける頂点を入れておく
  bfs(i)
  cc = 0
  b = False
  for j in a:
    if j == []: # 途中で -1 になることなく頂点を全て見終わったら、
      ans = max(ans,cc) # 答えの候補になりうる。
      break
    cc += 1
    for k in j:
      if set(g[k]) & set(j) != set():
# g[k] が 頂点k から行くことができる頂点、
# j が bfs 時に同じ回数でたどり着く頂点を表す。
# この2つの両方に属する頂点があったらアウト。
        b = True
        break
    if b:
      break
  
print(ans)