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 defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



def warshall_floyd(G):
    dist = deepcopy(G)
    n = len(G)
    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


def bipartite_or_not(G, s=0):
    n = len(G)
    global color
    color = [0] * n
    color[s] = 1
    dq = deque([s])
    while dq:
        u = dq.popleft()
        for v, bit in enumerate(G[u]):
            if u == v or bit == '0':
                continue
            elif color[v] == 0:
                color[v] = -color[u]
                dq += [v]
            else:
                if color[u] == color[v]:
                    return False
    return True



n = I()
G = SRL(n)
if not bipartite_or_not(G):
    print(-1)
    exit()


for u in range(n):
    for v in range(n):
        if u == v:
            G[u][v] = 0
        elif G[u][v] == '1':
            G[u][v] = 1
        else:
            G[u][v] = INF


dist = warshall_floyd(G)
print(max([dist[u][v] for u in range(n) for v in range(u + 1, n)]) + 1)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall
 
N = int(input())
S = [[0 if i==j else float("inf") for i in range(N)] for j in range(N)]
for i in range(N):
    S_list = list(input())
    for j in range(N):
        if S_list[j] == "0": continue
        S[i][j] = S[j][i] = int(S_list[j])
 
# 二部グラフ判定
def is_bipartite_graph(adjacency_matrix):
    colors = [0] * len(adjacency_matrix)
    return dfs(0,1,colors,adjacency_matrix)
#頂点vをcolor(1 or -1)で塗り、再帰的に矛盾がないか調べる。
def dfs(v,color,colors,adjacency_matrix):
    #今いる点を着色
    colors[v] = color
    #今の頂点から行けるところをチェック
    for to in range(len(adjacency_matrix[v])):
        # 頂点が隣接しない場合
        if adjacency_matrix[v][to] != 1:
            continue
        #同じ色が隣接してしまったらFalse
        if colors[to] == color:
            return False
        #未着色の頂点があったら反転した色を指定し、再帰的に調べる
        if colors[to] == 0 and not dfs(to,-color,colors,adjacency_matrix):
            return False
    #調べ終わったら矛盾がないのでTrue
    return True
 
if is_bipartite_graph(S):
    d = floyd_warshall(S)
    answer = 0
    for i in range(N):
        answer = max(answer,max(d[i]))
    print(int(answer)+1)
else:
    print(-1)

Submission status: Accepted

Solution code:
n=int(input())
l=[[] for i in range(n+1)]
for i in range(1,1+n):
  l1=list(input())
  for j in range(1,1+n):
    if l1[j-1]=="1":
      l[i].append(j)
color=[0 for i in range(n+1)]
b=True
def f(v,c):
    #頂点vに隣接する頂点全てを塗るあるいは判定する
    color[v] = c
    for i in range(len(l[v])):
        if color[ l[v][i] ] == c:
            return False
        elif color[ l[v][i] ] == 0 and not f(l[v][i],-c):
            #(g[v][i]がまだ塗られていない　かつ　そこを-cで塗っても問題ない) ではないなら
            return False
    return True
b=f(1,1)
if not b:
  print(-1)
else:
  inf=10**10
  d=[[inf for i in range(n+1)] for j in range(n+1)]
  for i in range(n+1):
    for j in l[i]:
      d[i][j]=1
  for k in range(n+1):
    for j in range(1,n+1):
      for i in range(1,n+1):
        d[i][j]=min(d[i][j],d[i][k]+d[k][j])
  max=0
  for i in range(1,n+1):
    for j in range(1,n+1):
      if i==j:
        pass
      elif d[i][j]>max:
        max=d[i][j]
  print(max+1)

Submission status: Accepted

Solution code:
#B-Graph Partition
n=int(input())
uselist=[[] for i in range(n+1)]
distancelist=[[10**5 for j in range(n)] for i in range(n)]
for i in range(n):
    s=input()
    for j in range(n):
        if int(s[j])!=0:
            distancelist[i][j]=1
            distancelist[j][i]=1
            uselist[i+1].append(j+1)
#各辺がどの点とつながっているかをuselistないに保存する
for i in range(n):
    distancelist[i][i]=0
visitedlist=[-1 for i in range(n)]
pointlist=[0 for j in range(n)]
flag=True
def search(i,string):
    visitedlist[i-1]=1
    if string==0:
        pointlist[i-1]="B"
    else:
        pointlist[i-1]=string
    flags=False 
    for node in uselist[i]:
        if visitedlist[node-1]==-1:
            #訪れていない点を発見した場合
            flags=True
            visitedlist[node-1]=1
            if string=="B"or string==0:
                pointlist[node-1]="R"
            elif string=="R":
                pointlist[node-1]="B"
        else:
            pass
    if flags:
        #一度でも訪れられた点がある時
        for j in uselist[i]:
            search(j,pointlist[j-1])
    if not flags:
        # 全ての点がすでにvisitedだった時
        pass    
search(1,0)
for j in range(1,n+1):
    for some in uselist[j]:
        if pointlist[j-1]==pointlist[some-1]:
            flag=False
if flag:
    #ワーシャルフロイド法で二点間の最小距離の最大値
    for k in range(n):
        for j in range(n):
            for i in range(n):
                distancelist[i][j]=min(distancelist[i][j],distancelist[i][k]+distancelist[k][j])
    maxi=0
    for i in range(n):
        for j in range(n):
            maxi=max(maxi,distancelist[i][j])
    print(maxi+1)
else:
    print(-1)

Submission status: Accepted

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

#二部グラフ判定
flag=[-1]*(n+1)
for i in range(1,n+1):
    if flag[i]==-1:
        que=[[i]]
        flag[i]=0
        k=1
        while que[0]:
            h=que[0]
            H=[]
            for u in h:
                for v in data[u]:
                    if flag[v]==-1:
                        flag[v]=k
                        H.append(v)
                    else:
                        if flag[v]==k:
                            continue
                        else:
                            print(-1)
                            sys.exit()
            k=(k+1)%2
            que=[H]

#washall
inf=float("inf")
d=[[inf]*(n+1) for i in range(n+1)]
for i in range(1,n+1):
    d[i][i]=0
for i in range(1,n+1):
    for u in data[i]:
        d[i][u]=1
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            d[i][j]=min(d[i][j],d[i][k]+d[k][j])
ans=0
for i in range(1,n+1):
    for j in range(1,n+1):
        ans=max(ans,d[i][j])

print(ans+1)

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
mat_original = [[int(c) for c in input()[:-1]] for _ in range(N)]
mat = [[1 if v == 1 else float('inf') for v in m] for m in mat_original]
for i in range(N):
    mat[i][i] = 0


def is_nibugurahu():
    visited = [0]*N
    visited[0] = 1
    Q = [0]
    while Q:
        q = Q.pop()
        for next in range(N):
            if mat_original[q][next] == 1:
                if visited[next] == 0:
                    visited[next] = visited[q]*(-1)
                    Q.append(next)
                elif visited[next] == visited[q]:
                    return False
                else:
                    pass
    return True


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


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

print(max([max(m) for m in mat])+1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from itertools import product
    n=int(input())
    A=[list(map(int,list(input()))) for _ in range(n)]
    for i,j in product(range(n),repeat=2):
        if(i==j): continue
        if(A[i][j]==0): A[i][j]=INF
    B=[a[:] for a in A] # deep copy
    E=[[] for _ in range(n)]
    for i,j in product(range(n),repeat=2):
        if(i==j): continue
        if(A[i][j]==1): E[i].append(j)

    # bipartile check
    d=[-1]*n # -1: unvisited
    def dfs(v)->bool:
        # iterate
        res=True
        for nv in E[v]:
            if(d[nv]==-1):
                d[nv]=d[v]^1
                res=min(res,dfs(nv))
            else:
                res=min(res,d[nv]^d[v])
        return res

    for v in range(n):
        if(d[v]==-1):
            d[v]=0
            if(not dfs(v)):
                print(-1)
                return

    # Warshall-Floyd
    for k,i,j in product(range(n),repeat=3):
        B[i][j]=min(B[i][j],B[i][k]+B[k][j])

    # output
    diam=0
    for i,j in product(range(n),repeat=2):
        if(B[i][j]==INF): continue # connectedなので必要ない
        diam=max(diam,B[i][j])
    print(diam+1)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from itertools import product
    n=int(input())
    A=[list(map(int,list(input()))) for _ in range(n)]
    for i,j in product(range(n),repeat=2):
        if(i==j): continue
        if(A[i][j]==0): A[i][j]=INF
    B=[a[:] for a in A] # deep copy
    E=[[] for _ in range(n)]
    for i,j in product(range(n),repeat=2):
        if(i==j): continue
        if(A[i][j]==1): E[i].append(j)

    # bipartile check
    from collections import deque
    d=[-1]*n # -1: unvisited
    def bfs(v)->bool:
        # initialize
        if(d[v]!=-1): return True
        d[v]=0
        Q=deque([v])
        while(Q):
            v=Q.popleft()
            for nv in E[v]:
                if(d[nv]==-1):
                    d[nv]=d[v]^1
                    Q.append(nv)
                else:
                    if(d[nv]^d[v]==0):
                        return False
        return True

    for v in range(n):
        if(not bfs(v)):
            print(-1)
            return

    # Warshall-Floyd
    for k,i,j in product(range(n),repeat=3):
        B[i][j]=min(B[i][j],B[i][k]+B[k][j])

    # output
    diam=0
    for i,j in product(range(n),repeat=2):
        if(B[i][j]==INF): continue # connectedなので必要ない
        diam=max(diam,B[i][j])
    print(diam+1)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from itertools import product
    n=int(input())
    A=[list(map(int,list(input()))) for _ in range(n)]
    for i,j in product(range(n),repeat=2):
        if(i==j): continue
        if(A[i][j]==0): A[i][j]=INF
    B=[a[:] for a in A] # deep copy
    E=[[] for _ in range(n)]
    for i,j in product(range(n),repeat=2):
        if(i==j): continue
        if(A[i][j]==1): E[i].append(j)

    # bipartile check
    d=[-1]*n # -1: unvisited
    def dfs(v,p=-1)->bool:
        # initialize
        if(p==-1):
            if(d[v]!=-1): return True
            else: d[v]=0
        # iterate
        res=True
        for nv in E[v]:
            if(nv==p): continue
            if(d[nv]==-1):
                d[nv]=d[v]^1
                res=min(res,dfs(nv,v))
            else:
                res=min(res,d[nv]^d[v])
        return res

    for v in range(n):
        if(not dfs(v)):
            print(-1)
            return

    # Warshall-Floyd
    for k,i,j in product(range(n),repeat=3):
        B[i][j]=min(B[i][j],B[i][k]+B[k][j])

    # output
    diam=0
    for i,j in product(range(n),repeat=2):
        if(B[i][j]==INF): continue # connectedなので必要ない
        diam=max(diam,B[i][j])
    print(diam+1)
resolve()

Submission status: Accepted

Solution code:
from collections import deque

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

adjL = [[] for _ in range(N)]
for i, Ss in enumerate(Sss):
    for j, S in enumerate(Ss):
        if S == '1':
            adjL[i].append(j)

def IsBipartiteGraph(adjList):
    def bfs(vSt):
        colors[vSt] = 1
        Q = deque([vSt])
        while Q:
            vNow = Q.popleft()
            color = colors[vNow]
            for v2 in adjList[vNow]:
                if colors[v2] == color:
                    return False
                elif colors[v2] == 0:
                    colors[v2] = -color
                    Q.append(v2)
        return True
    numV = len(adjList)
    colors = [0] * numV
    for vSt in range(numV):
        if colors[vSt] != 0: continue
        if not bfs(vSt):
            return False
    return True

def getDiameterOfUnweightedGraph(adjList):
    numV = len(adjList)
    def bfs(vSt):
        costs = [-1] * numV
        costs[vSt] = cost = 0
        vs = [vSt]
        while vs:
            cost += 1
            v2s = []
            for v in vs:
                for v2 in adjList[v]:
                    if costs[v2] == -1:
                        costs[v2] = cost
                        v2s.append(v2)
            vs = v2s
        return cost - 1
    return max([bfs(vSt) for vSt in range(numV)])


if not IsBipartiteGraph(adjL):
    print(-1)
else:
    maxDist = getDiameterOfUnweightedGraph(adjL)
    print(maxDist+1)

Submission status: Accepted

Solution code:
from collections import deque

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

adjL = [[] for _ in range(N)]
for i, Ss in enumerate(Sss):
    for j, S in enumerate(Ss):
        if S == '1':
            adjL[i].append(j)

def IsBipartiteGraph(adjList):
    def bfs(vSt):
        colors[vSt] = 1
        Q = deque([vSt])
        while Q:
            vNow = Q.popleft()
            color = colors[vNow]
            for v2 in adjList[vNow]:
                if colors[v2] == color:
                    return False
                elif colors[v2] == 0:
                    colors[v2] = -color
                    Q.append(v2)
        return True
    numV = len(adjList)
    colors = [0] * numV
    for vSt in range(numV):
        if colors[vSt] != 0: continue
        if not bfs(vSt):
            return False
    return True

def WarshallFloyd(adjList):
    numV = len(adjList)
    D = [[float('inf')]*numV for _ in range(numV)]
    for u, adj in enumerate(adjList):
        for v in adj:
            D[u][v] = 1
        D[u][u] = 0
    for k in range(numV):
        Dk = D[k]
        for i in range(numV):
            Di = D[i]
            Dik = Di[k]
            for j in range(numV):
                D2 = Dik + Dk[j]
                if D2 < Di[j]:
                    D[i][j] = D2
    return D


if not IsBipartiteGraph(adjL):
    print(-1)
else:
    distss = WarshallFloyd(adjL)
    maxDist = max(map(max, distss))
    print(maxDist+1)

Submission status: Accepted

Solution code:
# AGC039B - Graph Partition (153ms)
from collections import deque


def is_bipartite() -> bool:
    stack, color = [(1, 1)], [0] * (N + 1)
    color[1] = 1
    while stack:
        v, cur_color = stack.pop()
        next_color = -cur_color
        for u in E[v]:
            if color[u] == cur_color:
                return False
            if not color[u]:
                color[u] = next_color
                stack.append((u, next_color))
    return True


def bfs(source: int) -> int:
    queue = deque([source])
    dist = [0] * (N + 1)  # dist[i] := distance from V_source to V_i
    dist[source] = 1
    while queue:
        v = queue.popleft()
        cur = dist[v]
        for u in E[v]:
            if not dist[u]:
                dist[u] = cur + 1
                queue.append(u)
    return max(dist)


def main():
    # if bipartite graph -> diameter of the graph + 1
    global N, E
    N, *S = open(0)
    N = int(N)
    E = [0] + [[i for i, flg in enumerate(s, 1) if flg == "1"] for s in S]
    if is_bipartite():
        ans = max(bfs(i) for i in range(1, N + 1))
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
graph = [[300] * (N+1) for _ in range(N+1)] # 1行目と1列目は使わない
edges = []
for i in range(N+1):
    graph[i][i] = 0
for i in range(1, N+1):
    S = list(str(input()))
    for j in range(len(S)):
        if S[j] == '1':
            edges.append((i, j+1))
            graph[i][j+1] = graph[j+1][i] = 1
for k in range(N+1):
    for i in range(N+1):
        for j in range(i+1, N+1):
            x = graph[i][k] + graph[k][j]
            if x < graph[i][j]:
                graph[i][j] = graph[j][i] = x
# 二部グラフかどうかの判定のために0か1の色を塗る
colors = [None] * (N+1)
colors[1] = 0
que = [1]
while que:
    x = que.pop()
    for i in range(1, N+1):
        if graph[x][i] != 1 or x == i:
            continue
        if colors[i] is None:
            colors[i] = 1 - colors[x]
            que.append(i)

# 二部グラフかどうか
is_bg = all(colors[a] != colors[b] for a, b in edges)
if not is_bg:
    print(-1)
    exit()
print(max(max(x[1:]) for x in graph[1:]) + 1)

Submission status: Accepted

Solution code:
#自力で書いた

from collections import deque
n = int(input())
l = [input() for i in range(n)]

diam = -1    
for i in range(n):
    queue = deque([i])
    dist = [-1]*n
    dist[i] = 0
    while queue:
        u = queue.popleft()
        d = dist[u]
        ll = l[u]
        for v in range(n):
            if ll[v]=="1":
                if dist[v]==-1: #未踏.
                    dist[v] = d + 1
                    queue.append(v)
                else:
                    if abs(d-dist[v]) != 1:
                        print(-1)
                        exit()
    diam = max(diam, max(dist))

print(diam + 1)

Submission status: Accepted

Solution code:
n = int(input())
dis = [[0] * 205 for _i in range(205)]
for i in range(1, n + 1):
    dis[i][i] = 0
for i in range(1, n + 1):
    a = list(map(str, input().strip()))
    for j in range(n):
        if a[j] == '1':
            dis[i][j + 1] = 1


def bfs(x):
    mx = 0
    from collections import deque
    q = deque()
    l = [0] * 205
    q.append(x)
    l[x] = 1
    while len(q):
        x = q.popleft()
        mx = max(mx, l[x])
        for i in range(1, n + 1):
            if dis[x][i]:
                if l[i]:
                    if abs(l[i]-l[x]) == 1:
                        continue
                    else:
                        print(-1)
                        exit(0)
                else:
                    l[i] = l[x] + 1
                    q.append(i)
    return mx


ans = [0] * 205
for i in range(1, n + 1):
    ans[i] = bfs(i)

mark = [0] * 205
p = 0


def dfs(x):
    mark[x] = 1
    global p
    p = max(p, ans[x])
    for i in range(1, n + 1):
        if dis[x][i] and not mark[i]:
            dfs(i)


aas = 0
for i in range(1, n + 1):
    if not mark[i]:
        p = 0
        dfs(i)
        aas += p
print(aas)

Submission status: Accepted

Solution code:
import numpy as np
import sys
from scipy.sparse.csgraph import floyd_warshall, csgraph_from_dense
N = int(sys.stdin.buffer.readline())
S = np.frombuffer(sys.stdin.buffer.read(),
                  dtype='S1').reshape(N, -1)[:, :N].astype(int)
G = csgraph_from_dense(S)
F = floyd_warshall(G).astype(int)
F2 = F % 2
I0 = np.where(F2[0] == 0)
I1 = np.where(F2[0] == 1)
if (S[I0][:, I0] == 0).all() and (S[I1][:, I1] == 0).all():
    print(F.max() + 1)
    exit()
print(-1)

Submission status: Accepted

Solution code:
from collections import deque

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

for i in range(n):
    for j, e in enumerate(input()):
        if int(e): graph[i].append(j)

def bfs(start):
    q = deque([start])
    dist = [-1] * n
    dist[start] = 0
    length = 0
    while q:
        v = q.popleft()
        length = max(length, dist[v])
        for nv in graph[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v] + 1
                q.append(nv)
            elif dist[nv] == dist[v]:
                print(-1)
                exit()
    return length + 1

ans = 0
for i in range(n):
    ans = max(ans, bfs(i))

print(ans)

Submission status: Accepted

Solution code:
def bfs(dp, arr, i,  visited):
	q = []
	q.append(i)
	visited[i] = True
	while q:
		i = q.pop(0)
		visited[i] = True
		for j in arr[i]:
			if dp[j] == -1:
				dp[j] = dp[i] + 1
			elif dp[i] == dp[j]:
				return -1
			
			if visited[j] == False:
				visited[j] = True
				q.append(j)
	return 0

n=int(input())
i=0
arr=[]
degree = [0]*n
while i<n:
	s=input()
	a=[]
	for j,e in enumerate(s):
		if e=='1':
			a.append(j)
			degree[i]+=1
	arr.append(a)	
	i+=1

res = -1
ans = -1
for i in range(n):
	dp = [-1]*n
	visited=[False for x in range(n)]
	dp[i] = 1
	res=bfs(dp, arr, i, visited)
	if res  == 0:
		ans = max(ans , max(dp))

print(ans)

Submission status: Accepted

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

lst = [0] * N
lst[0] = 1

stack = [0]
flag = True
while len(stack) != 0:
    tmp = stack.pop()
    for index, x in enumerate(S[tmp]):
        if x == 0:
            continue
        if lst[index] == 0:
            lst[index] = -lst[tmp]
            stack.append(index)
        else:
            if lst[tmp] == -lst[index]:
                pass
            else:
                flag = False
                break
    if not flag:
        print (-1)
        exit()

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

g = np.array(S)
anslst = floyd_warshall(g)
ans = int(np.max(anslst))

print (ans + 1)

Submission status: Accepted

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

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

ans = -1

for i in range(n):
    edges = [[] for _ in range(n)]
    for j in range(n):
        for k in range(j,n):
            if s[j][k] == '1':
                edges[j].append(k)
                edges[k].append(j)

    tmp = 0
    stack = [i]
    visit = [False]*n
    visit[i] = True
    flag = True
    while True:
        li = []
        while stack:
            li2 = []
            l = stack.pop(-1)
            for j in edges[l]:
                li2.append(j)
            for j in li2:
                edges[j].remove(l)
            li += li2
        li = list(set(li))
        for j in li:
            if visit[j]:
                flag = False
        if flag:
            stack = li
            for j in li:
                visit[j] = True
            tmp += 1
        else:
            break
        if not stack:
            ans = max(ans,tmp)
            break

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import scipy.sparse.csgraph as c,numpy
s=numpy.int8([list(t[:-1])for t in open(0)][1:])
m=c.dijkstra(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=numpy.int8([list(t[:-1])for t in open(0)][1:])
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 sys
import copy

input = sys.stdin.readline

N = int(input())
OS = [[int(x) for x in list(input().strip())] for y in range(N)]

distmax = 0
for i in range(N):
	S = copy.deepcopy(OS)
	distlist = [-1]*N
	distlist[i] = 0
	queue = [i]
	dist = 0
	shortcut = False
	while len(queue)>0:
		dist += 1
		nq = []
		for ii in queue:
			for jj, neighbor in enumerate(S[ii]):
				if neighbor==1:
					if distlist[jj]==-1:
						distlist[jj] = dist
						S[jj][ii] = 0
						nq.append(jj)
					elif distlist[jj]!=dist:
						shortcut = True
						break
					else:
						S[jj][ii] = 0
			if shortcut: break
		if shortcut: break
		queue = nq
	dist -= 1
	if (not shortcut) and (dist>distmax):
		distmax = dist

if distmax==0:
	ans = -1
else:
	ans = distmax+1
print(ans)

Submission status: Accepted

Solution code:
# AGC039B - Graph Partition (156ms)
from collections import deque


def is_bipartite() -> bool:
    stack = [(1, 1)]
    color = [0] * (N + 1)
    color[1] = 1
    while stack:
        v, cur_color = stack.pop()
        next_color = -cur_color
        for u in E[v]:
            if color[u] == cur_color:
                return False
            if not color[u]:
                color[u] = next_color
                stack.append((u, next_color))
    return True


def bfs(start) -> int:
    que = deque([start])
    dist = [0] * (N + 1)  # dist[i] := distance from V_start to V_i
    dist[start] = 1
    while que:
        v = que.popleft()
        cur = dist[v]
        for u in E[v]:
            if not dist[u]:
                dist[u] = cur + 1
                que.append(u)
    return max(dist)


def main():
    # if bipartite graph -> diameter of the graph + 1
    global N, E
    N, *S = open(0).read().split()
    N = int(N)
    E = [0] + [[i for i, flg in enumerate(s, 1) if flg == "1"] for s in S]
    if is_bipartite():
        ans = max(bfs(i) for i in range(1, N + 1))
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# AGC039B - Graph Partition
from collections import deque


def is_bipartite() -> bool:
    stack = [(1, 1)]
    color = [-1] * (N + 1)
    color[1] = 1
    while stack:
        v, cur_color = stack.pop()
        next_color = cur_color ^ 1
        for u in E[v]:
            if color[u] == cur_color:
                return False
            if color[u] == -1:
                color[u] = next_color
                stack.append((u, next_color))
    return True


def bfs(start) -> int:
    que = deque([start])
    dist = [0] * (N + 1)  # dist[i] := distance from V_start to V_i
    dist[start] = 1
    while que:
        v = que.popleft()
        cur = dist[v]
        for u in E[v]:
            if not dist[u]:
                dist[u] = cur + 1
                que.append(u)
    return max(dist)


def main():
    # if bipartite graph -> diameter of the graph + 1
    global N, E
    N, *S = open(0).read().split()
    N = int(N)
    E = [0] + [[i for i, flg in enumerate(s, 1) if flg == "1"] for s in S]
    if is_bipartite():
        ans = max(bfs(i) for i in range(1, N + 1))
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# AGC039B - Graph Partition
from collections import deque


def is_bipartite() -> bool:
    stack = deque([(1, 1)])
    color = [-1] * (N + 1)
    color[1] = 1
    while stack:
        v, cur_color = stack.pop()
        next_color = cur_color ^ 1
        for u in E[v]:
            if color[u] == cur_color:
                return False
            if color[u] == -1:
                color[u] = next_color
                stack.append((u, next_color))
    return True


def bfs(start) -> int:
    que = deque([start])
    dist = [-1] * (N + 1)  # dist[i] := distance from V_start to V_i
    dist[start] = 0
    while que:
        v = que.popleft()
        cur = dist[v]
        for u in E[v]:
            if dist[u] == -1:
                dist[u] = cur + 1
                que.append(u)
    return max(dist)


def main():
    # if bipartite graph -> diameter of the graph + 1
    global N, E
    N, *S = open(0).read().split()
    N = int(N)
    E = [0] + [[i for i, flg in enumerate(s, 1) if flg == "1"] for s in S]
    if is_bipartite():
        ans = max(bfs(i) for i in range(1, N + 1)) + 1
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# AGC039B - Graph Partition
def is_bipartite() -> bool:
    stack = [(1, 1)]
    color = [-1] * (N + 1)
    color[1] = 1
    while stack:
        v, cur_color = stack.pop()
        next_color = cur_color ^ 1
        for u in E[v]:
            if color[u] == cur_color:
                return False
            if color[u] == -1:
                color[u] = next_color
                stack.append((u, next_color))
    return True


def bfs(start) -> int:
    que = [start]
    dist = [-1] * (N + 1)  # dist[i] := distance from V_start to V_i
    dist[start] = 0
    while que:
        v = que.pop(0)
        cur = dist[v]
        for u in E[v]:
            if dist[u] == -1:
                dist[u] = cur + 1
                que.append(u)
    return max(dist)


def main():
    # if bipartite graph -> diameter of the graph + 1
    global N, E
    N, *S = open(0).read().split()
    N = int(N)
    E = [0] + [[i for i, flg in enumerate(s, 1) if flg == "1"] for s in S]
    if is_bipartite():
        ans = max(bfs(i) for i in range(1, N + 1)) + 1
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# AGC039B - Graph Partition
from collections import deque


def is_bipartite() -> bool:
    stack = [(1, 1)]
    color = [-1] * (N + 1)
    color[1] = 1
    while stack:
        v, cur_color = stack.pop()
        next_color = cur_color ^ 1
        for u in E[v]:
            if color[u] == cur_color:
                return False
            if color[u] == -1:
                color[u] = next_color
                stack.append((u, next_color))
    return True


def bfs(start) -> int:
    que = deque([start])
    dist = [-1] * (N + 1)  # dist[i] := distance from V_start to V_i
    dist[start] = 0
    while que:
        v = que.popleft()
        cur = dist[v]
        for u in E[v]:
            if dist[u] == -1:
                dist[u] = cur + 1
                que.append(u)
    return max(dist)


def main():
    # if bipartite graph -> diameter of the graph + 1
    global N, E
    N, *S = open(0).read().split()
    N = int(N)
    E = [0] + [[i for i, flg in enumerate(s, 1) if flg == "1"] for s in S]
    if is_bipartite():
        ans = max(bfs(i) for i in range(1, N + 1)) + 1
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()