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:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product

def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

g=[[]*n for i in range(n)]
for i in range(n):
    for j in range(n):
        if s[i][j]=="1":
            g[i].append(j)

# print(g)
ans=-float('inf')
for i in range(n):
    itta=[0]*n
    d=deque([i])
    cnt=0
    while d:
        # print(d)
        cnt+=1
        for i in range(len(d)):
            tmp=d.popleft()
            if itta[tmp]==0:
                itta[tmp]=cnt
                for j in range(len(g[tmp])):
                    if itta[g[tmp][j]]==0:
                        d.append(g[tmp][j])
            elif itta[tmp]==cnt:
                continue
            else:
                cnt=-float('inf')
    ans=max(ans,cnt)
if ans==-float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

# 奇数長のループがあるかどうかをチェック
color = [-1] * N
def dfs(node, par):
  global color
  res = True
  for i, s in enumerate(S[node]):
    if s and i != par:
      if color[i] == -1:
        color[i] = (color[node] + 1) % 2
        res *= dfs(i, node)
      else:
        res *= (color[i] == (color[node] + 1) % 2)
  return res

color[0] = 0
if dfs(0, -1):
  from scipy.sparse.csgraph import floyd_warshall
  import numpy as np
  dist = floyd_warshall(S).astype(int)
  print(dist.max() + 1)
else:
  print(-1)

Submission status: Accepted

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

# 奇数長のループがあるかどうかをチェック
node_to_idx = {}
visited = [False] * N
def dfs(node, par, n):
  global node_to_idx
  res = True
  for i, s in enumerate(S[node]):
    if s and i != par:
      if i in node_to_idx:
        idx = node_to_idx[i]
        if (n - idx) % 2:
          res *= False
        else:
          res *= True
      else:
        if visited[i]:
          continue
        visited[i] = True
        node_to_idx[i] = n
        res *= dfs(i, node, n+1)
  return res

node_to_idx[0] = 0
visited[0] = True
res = dfs(0, -1, 1)
if res:
  from scipy.sparse.csgraph import floyd_warshall
  import numpy as np
  dist = floyd_warshall(S).astype(int)
  print(dist.max() + 1)
else:
  print(-1)

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heappop, heappush

INF = float("inf")

# ２部グラフの判定
def bfs():
  stack = deque()
  stack.append((0, 1)) #頂点:0, 色:1
  colors[0] = 1
  while stack:
    v, c = stack.popleft()
    for i in edges[v]:
      if colors[i] == c:
        return False
      if colors[i] == 0:
        stack.append((i, -c))
        colors[i] = -c
  return True

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    hq = [(0, s)] # (距離, 頂点)
    while hq:
        d, v = heappop(hq)
        if dist[v] < d:
            continue
        for child in G[v]:
            if dist[child] > dist[v] + 1:
                dist[child] = dist[v] + 1
                heappush(hq, (dist[child], child))
    return dist

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

edges = [[] for _ in range(n)]

for i in range(n):
  for j in range(n):
    if S[i][j] == "1":
      edges[i].append(j)
  
# 0: 未踏, 1 or -1: 踏破
colors = [0] * n

if bfs() == True:
  import numpy as np
  from scipy.sparse.csgraph import shortest_path
  from scipy.sparse.csgraph import floyd_warshall
  from scipy.sparse.csgraph import csgraph_from_dense

  li = [list(map(int, s)) for s in S]
  nli = np.array(li)
  nnli = np.where(nli == 0, 10**12, nli)

  G = csgraph_from_dense(nnli, null_value=10**12)
  d = floyd_warshall(G)
  
  ans = 0
  for i in range(n):
    for j in range(n):
      if ans < d[i][j]:
        ans = d[i][j]
      
  print(int(ans) + 1)
else:
  print(-1)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    S = [[int(x) for x in sys.stdin.readline().rstrip()] for _ in range(N)]

    max_k = 0

    for i in range(N):
        node = [-1] * N
        q = collections.deque()
        q.append((i,1))
        node[i] = 1
        f = True
        while q:
            v,d = q.popleft()
            for j in range(N):
                if S[v][j] == 0: continue
                if node[j] == d+1 or node[j] == d-1: continue
                if node[j] < 0:
                    node[j] = d+1
                    q.append((j,d+1))
                else:
                    f = False
                    break
            else:
                continue
            break
        if f: max_k = max(max_k,max(node))
    if max_k == 0:
        print(-1)
    else:
        print(max_k)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# キュー
from collections import deque

n = int(input())
links = [[] for _ in range(n+1)]
for i in range(1,n+1):
    ss = input()
    for j,s in enumerate(ss,1):
        if(s=='1'):
            links[i].append(j)

ans = -1
for i in range(1,n+1):
    ng_flag = False

    depth = [-1] * (n+1)
    depth[i] = 1
    max_depth = 1
    d = deque()
    d.append(i)
    while(d):
        now = d.popleft()
        for j in links[now]:
            if(depth[j] == -1):
                depth[j] = depth[now] + 1
                d.append(j)
                max_depth = max(max_depth, depth[j])
            else:
                if(abs(depth[j] - depth[now]) != 1):
                    ng_flag = True
                    break
        if(ng_flag):
            break
    if(not ng_flag):
        ans = max(ans, max_depth)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
mat=[[10**18 for i in range(n+1)] for j in range(n+1)]
ab = [[] for i in range(n)]

for i in range(n):
    si = input()
    for j in range(n):
        if int(si[j]) == 1:
            #print(i,j)
            mat[i+1][j+1] = 1
            ab[i].append(j)

colors = [0 for i in range(n)] 

#頂点vをcolor(1 or -1)で塗り、再帰的に矛盾がないか調べる。矛盾があればFalse
def dfs(v,color):
    #今いる点を着色
    colors[v] = color
    #今の頂点から行けるところをチェック
    for to in ab[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 not is_bipartite():
    print(-1)
    exit()

#N,M=map(int,input().split())

for i in range(n+1):
	mat[i][i]=0

for i in range(1,n+1):
	for x in range(1,n+1):
		for y in range(1,n+1):
			mat[x][y] = min(mat[x][y], mat[x][i] + mat[i][y])

ans = 0

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

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

N = int(readline())
S = [list(map(int, readline().strip())) for _ in range(N)]

ans = -1
for st in range(N):
    level = [None]*N
    level[st] = 0
    used = set([st])
    stack = [st]
    flag = True
    while len(used) < N:
        stack2 = []
        for vn in stack:
            used.add(vn)
            for vf in range(N):
                if S[vn][vf]:
                    if level[vf] is None:
                        level[vf] = level[vn]+1
                        stack2.append(vf)
                    elif level[vf] == level[vn]-1 or level[vf] == level[vn]+1:
                        continue
                    else:
                        flag = False
        stack = stack2[:]
    if flag:
        ans = max(ans, max(level)+1)
print(ans)

Submission status: Accepted

Solution code:

from collections import deque


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

for i in range(N):
    for j in range(i+1,N):
        if S[i][j] == "1":
            es[i].append(j)
            es[j].append(i)


INF = float("inf")

def bfs(node):
    dist = [INF] * N
    dist[node] = 0
    union = [[] for _ in range(N+1)]
    union[0].append(node)
    q = deque()
    q.append(node)
    while q:
        curr = q.popleft()
        for nxt in es[curr]:
            if dist[curr] + 1 < dist[nxt]:
                dist[nxt] = dist[curr] + 1
                union[dist[nxt]].append(nxt)
                q.append(nxt)

    d = max(dist)
    max_idx = dist.index(d)
    return max_idx, dist, union

s, dist, union = bfs(0)

for u in union:
    if len(u) >= 2:
        for i in u:
            for j in u:
                # 同じ集合なのに辺があると矛盾するのでNG
                if S[i][j] == "1":
 
                    print(-1)
                    exit()
ans = 0
for i in range(N):
    _, dist, _ = bfs(i)
    ans = max(ans, max(dist)+1)

print(ans)

Submission status: Accepted

Solution code:
"""
問題の理解が困難
ノードi,jを結ぶ辺があるとき、ノードiは集合aに、ノードjは集合k+1（あるいは逆）に含まれるようにノードを集合に分ける。
その条件を満たす最大の集合の数を求める

1->2
2->3
2->4
みたいなのがあるときに、
・1と2は別の集合（1を集合１、２を集合とする）
・２と３は別の集合（２が集合２なので、３は集合１か３。できるだけ集合の数を多くとりたいので、３とする）
・２と４は別の集合（２が集合２なので、４は集合１か３。上に同じく３とする）
みたいな感じか。
なので、
あるノードから等距離にあるノードを同じ集合にする
という戦略をとれば、集合の数を最大化できる。
で、同じ集合に属するやつらの間に辺がある場合、辺を挟んだノードは別の集合にならなければならないので矛盾するからNG

↑から、木の直径＋１が最大の集合数になるので、double sweepだったか？何かでもとめればよいか？
"""



import heapq
from collections import deque



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

for i in range(N):
    for j in range(i+1,N):
        if S[i][j] == "1":
            es[i].append(j)
            es[j].append(i)


INF = float("inf")
dist = [INF] * N
dist[0] = 0
union = [[] for _ in range(N+1)]
union[0].append(0)
q = []
heapq.heappush(q, (0, 0))

while q:
    cost, curr = heapq.heappop(q)
    for nxt in es[curr]:
        if dist[nxt] <= cost + 1:
            continue
        dist[nxt] = cost + 1

        union[cost+1].append(nxt)
        heapq.heappush(q, (dist[nxt], nxt))


for u in union:
    if len(u) >= 2:
        for i in u:
            for j in u:
                # 同じ集合なのに辺があると矛盾するのでNG
                if S[i][j] == "1":

                    print(-1)
                    exit()

ans = 0
for i in range(N):
    q = deque()
    q.append(i)
    dist = [0] * N
    # 距離＋１が答えなので、起点を１としておく
    dist[i] = 1
    while q:
        curr = q.popleft()
        for nxt in es[curr]:
            if dist[nxt] == 0:
                dist[nxt] = dist[curr] + 1
                q.append(nxt)
 
    ans = max(ans, max(dist))

print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = lambda : sys.stdin.readline().rstrip()
    sys.setrecursionlimit(max(1000, 10**9))


    from collections import defaultdict
    from queue import deque

    n = int(input())
    ns = defaultdict(set)
    for u in range(n):
        for v,b in enumerate(map(int, input())):
            if b:
                ns[u].add(v)
                ns[v].add(u)

    best = -1
    for start in range(n):
        q = deque([])
        seen = [False] * n
        vals = [-1] * n
        seen[start] = True
        vals[start] = 0
        v = 0
        q.appendleft((start, v))
        while q:
            u, val = q.pop()
            for v in ns[u]:
                if not seen[v]:
                    q.appendleft((v, val+1))
                    seen[v] = True
                    vals[v] = val + 1
                elif vals[v]==val:
                    print(-1)
                    return
        best = max(best, val+1)
    print(best)
main()

Submission status: Accepted

Solution code:
# 隣り合う頂点が、同じグループにいなければ良い
# 点を順番に0,1で塗っていき、既に0で塗られている場所に1を塗ろうとしたら（あるいはその逆）NG。

N = int(input())
E = [[] for i in range(N)]
G = [None] * N
INF = 10 ** 9
for i in range(N):
  edges = input()
  G[i] = list(map(int,list(edges)))
  G[i] = list(map(lambda x:INF if x == 0 else x,G[i]))
  for j in range(len(edges)):
    if edges[j] == "1":
      E[i].append(j)

color = [-1 for i in range(N)]
from collections import deque
q = deque([])
# 頂点、次に塗る色
q.append([0,0])

while q:
  v,bit = q.popleft()
  if color[v] != -1:
    # 既に色が塗られている
    if color[v] == bit: # 塗ろうとしている色と同じなら探索済み
      continue
    else: # 違う色ならNG
      print(-1)
      exit(0)
  # 塗る
  color[v] = bit
  children = E[v]
  for child in children:
    q.append([child,bit^1])

# ここまで来たら、最も長い頂点間の距離を求め+1が答え
# ワーシャルフロイドして最大値

import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse.csgraph import csgraph_from_dense

G = csgraph_from_dense(G, null_value=10**9)
d = floyd_warshall(G)

ans = 0
for i in range(N):
  for j in range(N):
    if ans < d[i][j]:
      ans = d[i][j]
      
print(int(ans) + 1)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

def main():
    N = int(input())
    G = [[] for _ in range(N)]
    dist = []
    for i in range(N):
        route = [int(i) for i in input()]
        for j in range(N):
            if route[j]:
                G[i].append(j)
            elif i != j:
                route[j] = INF
        dist.append(route)
    
    color = [-1]*N
    color[0] = 0
    stack = [0]
    possible = True
    while stack:
        p = stack.pop()
        for e in G[p]:
            if color[e] >= 0:
                if color[e] == color[p]:
                    possible = False
            else:
                color[e] = color[p]^1
                stack.append(e)
        if not possible:
            break
    
    if possible:
        csr = csr_matrix(dist)
        minimum_route = floyd_warshall(csr).astype(int)
        ans = minimum_route.max()
        print(ans + 1)
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class WarshallFloyd:
    def __init__(self,n):
        self.v = n
        self.d = [[1e100]*n for _ in range(n)]
        for i in range(n):
            self.d[i][i] = 0

    def path(self,x,y,c):
        if x == y:
            return False
        self.d[x][y] = c
        self.d[y][x] = c
        return True

    def build(self):
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
        return self.d

class UnionFind:
    def __init__(self, n):
        '木の初期化をする'
        self.p = [-1] * n
        self.rank = [1]*n
    def find(self, x):
        'x の親を返す'
        if self.p[x] == -1:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def unite(self, x, y):
        'rankの低い親を高い方のの親にする'
        if not self.same(x,y):
            x = self.find(x)
            y = self.find(y)
            if self.rank[x] > self.rank[y]:
                x,y = y,x
            elif self.rank[x] == self.rank[y]:
                self.rank[y] += 1
            self.p[x] = y
            return True
        else:
            return False

    def same(self, x, y):
        return self.find(x) == self.find(y)

n = int(input())
wf = WarshallFloyd(n*2)
uf = UnionFind(n*2)
for i in range(n):
    s = input()
    for j in range(i):
        if s[j] == '1':
            wf.path(i,j,1)
            uf.unite(i,j+n)
            uf.unite(i+n,j)
for i in range(n):
    if uf.same(i,i+n):
        print(-1)
        exit(0)
d = wf.build()
ans = 0
for i in range(n):
    for dist in d[i][:i]:
        ans = max(ans,dist)
print(ans+1)

Submission status: Accepted

Solution code:
def warshall_floyd(v_count: int, matrix: list) -> list:
    """ ワーシャルフロイド
    v_count: 頂点数
    matrix: 隣接行列(到達不能はfloat("inf"))
    """
    for i in range(v_count):
        for j, c2 in enumerate(row[i] for row in matrix):
            for k, (c1, c3) in enumerate(zip(matrix[j], matrix[i])):
                if c1 > c2+c3:
                    matrix[j][k] = c2+c3
    return matrix


n = int(input())
g = [[] for _ in range(n)]
m = [list(map(int, input())) for _ in range(n)]
for i, row in enumerate(m):
    for j, c in enumerate(row):
        if c == 1:
            g[i].append(j)
        elif i != j:
            m[i][j] = 10000000000
d = [-1] * n
d[0] = 0
s = [0]
while s:
    p = s.pop()
    for node in g[p]:
        if d[node] == -1:
            s.append(node)
            d[node] = d[p] ^ 1
        elif d[node] == d[p]:
            print(-1)
            exit(0)
ans = 0
warshall_floyd(n, m)
for row in m:
    ans = max(ans, max(row))
print(ans + 1)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self._size = [1 for _ in range(n)]
        self._edges = 0

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self._size[y] += self._size[x]
            self._edges += 1
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self._size[x] += self._size[y]
            self._edges += 1
    
    def size(self, x):
        x = self.find(x)
        return self._size[x]
    
    def trees(self):
        return self.n - self._edges

    def same(self, x, y):
        return self.find(x) == self.find(y)

n = ni()
s = nsn(n)

def floyd_warshall(n, dist):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k])

def ok(n, dist):
    uf = UnionFind(2 * n)
    for i in range(n):
        for j in range(n):
            if s[i][j] == '1':
                uf.unite(i, j + n)
                uf.unite(i + n, j)
    for i in range(n):
        if uf.same(i, i + n):
            return False
    return True

dist = [[inf] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if s[i][j] == '1':
            dist[i][j] = 1
    dist[i][i] = 0

floyd_warshall(n, dist)

if ok(n, dist):
    ans = 0
    for i in range(n):
        for j in range(n):
            if dist[i][j] != inf:
                ans = max(dist[i][j], ans)
    print(ans + 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
N = int(input())
E = [[] for _ in range(N)]
for j in range(N):
	t = input()
	for i in range(N):
		if t[i] == '1':
			E[j].append(i)

ANS = -1
for start in range(N):		
	cnt = [0] * N
	cnt[start] = 1
	q = [start]
	cond = 0
	while q:
		cp = q.pop(0)
		if cp < 0:
			continue
		cnt[cp] *= -1

		for nep in E[cp]:
			if cnt[nep] < 0:
				continue
			elif cnt[nep] > 0:
				if cnt[nep] == cnt[cp] * (-1) + 1:
					continue
				else:
					cond = 1
					break
			else:
				cnt[nep] = cnt[cp] * (-1) + 1
				q.append(nep)
	
	if cond:
		continue

	ans = min(cnt) * (-1)
	ANS = max(ANS, ans)

print(ANS)

Submission status: Accepted

Solution code:
n = int(input())
T = []
graph = [[] for i in range(n)]
for i in range(n):
    s = input()
    for j in range(n):
        if s[j] == '1':
            graph[j].append(i)
color = [-1]*n
color[0] = 0
stack = [0]
flag = True
while len(stack) != 0:
    t = stack.pop()
    for i in range(len(graph[t])):
        cur = graph[t][i]
        if color[cur] == -1:
            if color[t] == 1:
                color[cur] = 0
            else:
                color[cur] = 1
            stack.append(cur)
        else:
            if color[t] != color[cur]:
                None
            else:
                flag = False
                break
    if not flag:
        break
ans = 0
if not flag:
    print(-1)
else:
    dist = [[10**5]*n for i in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for i in range(n):
        for j in range(len(graph[i])):
            dist[i][graph[i][j]] = 1
            dist[graph[i][j]][i] = 1
    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])
    for i in range(n):
        for j in range(n):
            ans = max(ans, dist[i][j]+1)
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque


def grouping(n, N, d):
    group = [-1]*(N+1)
    group[n] = 1

    q = deque([n])
    while q:
        s = q.popleft()
        for t in d[s]:
            if group[t]!=-1:continue
            group[t] = group[s] + 1
            q.append(t)

    for k, v in d.items():
        for j in v:
            if not abs(group[j]-group[k])==1:
                return False
    
    return group


def solve():
    N = int(input())
    d = defaultdict(list)
    for i in range(1, N+1):
        for j, s in enumerate(input(), start=1):
            if s=="1":
                d[i].append(j)
    

    ans = -1
    for i in range(1, N+1):
        res = grouping(i, N, d)
        if res != False:
            ans = max(ans, max(res))
    
    print(ans)

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N=int(input())
S=[input() for i in range(N)]
l=[None]*N
ni=1
b=[0]
l[0]=False
while b:
    a=[]
    for i in b:
        for j in range(N):
            if S[i][j]=="1":
                if l[j]==None:
                    l[j]=not l[i]
                    a.append(j)
                else:
                    if l[j]==l[i]:
                        ni=0
    b=a
s=[[1000]*N for i in range(N)]
for i in range(N):
    s[i][i]=0
for i in range(N):
    for j in range(N):
        if S[i][j]=="1":
            s[i][j]=1
for i in range(N):
    for j in range(N):
        for k in range(N):
            s[j][k] = min(s[j][k],s[j][i] + s[i][k])
M=0
for i in s:
    M=max(M,max(i))
print(M+1 if ni else -1)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
S = [list(map(int, list(input()))) for _ in range(N)]
graph = csr_matrix(S)
dist_matrix = floyd_warshall(graph, directed=False)
ans = np.array(dist_matrix, dtype=np.int64).max()+1

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

color = [0]*N
def f(v, c):
    color[v] = c
    for node in g[v]:
        if color[node] == c:
            return False
        elif color[node] == 0 and not f(node, -c):
            return False
    return True

k = 1
for i in range(N):
	if color[i] == 0 and not f(i, 1):
		k = -1
		break

if k == 1:
	print(ans)
else:
	print(-1)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
s = [list(map(int, list(input()))) for _ in range(n)]
bord = [[] for _ in range(n)]
for i in range(n-1):
    for j in range(i+1, n):
        if s[i][j]==1:
            bord[i].append(j)
            bord[j].append(i)

result = []
for i in range(n):
    ch = True
    visit = [-1 for _ in range(n)]
    visit[i] = 1
    q = deque([i])
    while q:
        x = q.popleft()
        for y in bord[x]:
            if visit[y]<0:
                visit[y] = visit[x]+1
                q.append(y)
            elif (visit[y] == visit[x]+1) or (visit[y]==visit[x]-1):
                continue
            else:
                ch = False
                break
    if ch:
        result.append(max(visit))
    else:
        result = [-1]
        break
print(max(result))

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
s = [list(map(int, list(input()))) for _ in range(n)]
bord = [[] for _ in range(n)]
for i in range(n-1):
    for j in range(i+1, n):
        if s[i][j]==1:
            bord[i].append(j)
            bord[j].append(i)

result = []
for i in range(n):
    ch = True
    visit = [-1 for _ in range(n)]
    visit[i] = 1
    q = deque([i])
    while q:
        x = q.popleft()
        for y in bord[x]:
            if visit[y]<0:
                visit[y] = visit[x]+1
                q.append(y)
            elif (visit[y] == visit[x]+1) or (visit[y]==visit[x]-1):
                continue
            else:
                ch = False
                break
    if ch:
        result.append(max(visit))
    else:
        result = [-1]
        break
print(max(result))

Submission status: Accepted

Solution code:
N=int(input())
d=[[float("inf") for i in range(0,N)] for i in range(0,N)]
for i in range(0,N):
    S=input()
    for j in range(0,N):
        if S[j]=="1":
            d[i][j]=1

for k in range(0,N):
    for i in range(0,N):
        for j in range(0,N):
            if d[i][j]>d[i][k]+d[k][j]:
                d[i][j]=d[i][k]+d[k][j]

ans=0
for i in range(0,N-1):
    for j in range(i+1,N):
        ans=max(ans,d[i][j])
for i in range(1,N-1):
    for j in range(i+1,N):
        if d[i][j]==1 and d[0][i]==d[0][j]:
            ans=-2

print(ans+1)

Submission status: Accepted

Solution code:
n = int(input())
S = []
for i in range(n):
    S.append(input())
color = [-1]*n #0:黒, 1:白
color[0] = 0
stack = [0]
colored = [0]*n
colored[0] = 1
while len(stack) != 0:
    temp = stack.pop()
    col = color[temp]
    cur = S[temp]
    for j in range(n):
        if cur[j] == '1':
            if colored[j] != 0:
                if color[j] == col:
                    print(-1)
                    exit()
            else:
                if col == 1:
                    color[j] = 0
                else:
                    color[j] = 1
                colored[j] = 1
                stack.append(j)
maxdist = 0
dist = []
for i in range(n):
    d = [10**10]*n
    d[i] = 0
    dist.append(d)
for i in range(n):
    for j in range(n):
        if S[i][j] == '1':
            dist[i][j] = 1
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])
for i in range(n):
    for j in range(n):
        maxdist = max(maxdist, dist[i][j])
print(maxdist+1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque

def solve(N: int, S: "List[str]"):
    matrix = [[] for _ in range(N)]
    d = [[10**5]*N for _ in range(N)]

    for i in range(N):
        d[i][i] = 0
        for j in range(N):
            if S[i][j] == "1":
                matrix[i].append(j)
                d[i][j] = 1
                d[j][i] = 1
    
    # ２部グラフ 判定
    stack = [(0,1)]
    color = [-1]*N

    while stack:
        node,c = stack.pop()
        color[node] = c

        for next in matrix[node]:
            if color[next] == -1:
                stack.append((next,~c))
            else:
                if c^color[next] == 0:
                    print(-1)
                    return


    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])

    answer = 0
    for i in range(N):
        answer = max(answer,max(d[i]))
    print(answer+1)
    return

def main():
    N = int(input())
    S = [input() for _ in range(N)]
    solve(N, S)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
#input = sys.stdin.buffer.readline
from collections import deque
 
def main():
    N = int(input())
    edge = [list(str(input())) for _ in range(N)]

    dist = [-1 for _ in range(N)]
    col = [0 for _ in range(N)]
    dist[0],col[0] = 0,1
    q = deque([(0,1)])
    D = 0
    while q:
        now,nc = q.popleft()
        for i in range(N):
            if edge[now][i] == "1":
                fol = i
                if col[fol] == 0:
                    col[fol] = -1*nc
                    q.append((fol,-1*nc))
                elif col[fol] == nc:
                    print(-1)
                    exit()

    def getmax(x):
        dist = [-1 for _ in range(N)]
        dist[x] = 1
        q = deque([x])
        while q:
            now = q.popleft()
            for i in range(N):
                if edge[now][i] == "1":
                    fol = i
                    if dist[fol] == -1:
                        dist[fol] = dist[now]+1
                        q.append(fol)
        return max(dist)
    
    print(max(getmax(i) for i in range(N)))
    
if __name__ == "__main__":
    main()