提出 #7864926

---

ソースコード 拡げる

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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

"""
・二部グラフが必要
・最長の最短距離 + 1 で上からbound
・2部グラフならbfs木が満たすのでよい
"""

N = int(readline())
S = np.frombuffer(read(),'S1').reshape(N,-1)[:,:N].astype(np.int64)

graph = csgraph_from_dense(S)

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

max_d = 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()

answer = max_d + 1 if bl else -1
print(answer)

提出情報

ジャッジ結果