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 sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

from collections import deque

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

def bfs(start):
    res = 0
    dist = [-1] * N
    dist[start] = 1
    q = deque()
    q.append([start, 1])
    st = set()
    st.add((start, 1))

    while q:
        i, d = q.popleft()
        if dist[i] == -1:
            dist[i] = d
            res = max(res, d)
        elif dist[i] != d:
            res = -1
            break
        for j in range(N):
            if S[i][j] == '1' and dist[j] != d-1:
                if (j, d+1) not in st:
                    q.append([j, d+1])
                    st.add((j, d+1))
    return res

ans = -1
for i in range(N):
    k = bfs(i)
    if k == -1:
        break
    else:
        ans = max(ans, k)

print(ans)

Submission status: Accepted

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

def dfs(v, color):
    colors[v] = color
    for to in g[v]:
        if colors[to] == color: return False
        if colors[to] == 0 and not dfs(to, -color):
            return False
    return True

def Washall_Floyd(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

n = int(input())
g = [[] for _ in range(n)]
f_inf =float('inf')
dist = [[f_inf]*n for _ in range(n)]
for i in range(n): dist[i][i]=0

for i in range(n):
    S = input()
    for j in range(n):
        if S[j] == '1':
            g[i].append(j)
            dist[i][j] = 1
            dist[j][i] = 1

colors = [0] * n
ans = -1
if not dfs(0, 1):
    print(ans)
else:
    Washall_Floyd(dist)
    for d in dist:
      tmp = max(d)
      ans = max(tmp, ans)
    print(ans+1)

Submission status: Accepted

Solution code:
"""
AtCoder Grand Contest 039  B - Graph Partition / 


（１）ある集合V_iに含まれるノードから伸びる辺について、その先の集合がV_i-1かV_i+1になるように分ける
（２）その時の集合の個数の最大値を求める

（１）を言い換えると、あるノードが偶数番の集合に属しているとき、それと繋がっているノードが奇数番号の集合かつ差が１である
　→二部グラフ
（２）V_1とV_kがあるとき、少なくともそれらはk本の辺をたどらなければ繋がれないはずなので、最も距離の長い辺（直径）を探す
"""

from collections import deque

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

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


q = deque()
q.append(0)
checked = [0] * N
checked[0] = 1
while q:
    curr = q.popleft()
    for nxt in es[curr]:
        # 未探索なので、currと別の集合に設定
        if checked[nxt] == 0:
            checked[nxt] = checked[curr] * -1
            q.append(nxt)
        else:
            # 探索済みなので、別の集合に属しているか確認し、同じであれば条件を満たさない
            if checked[nxt] == checked[curr]:
                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:
from collections import deque
n=int(input())
g=[[] for i in range(n)]
for i in range(n):
    p=list(str(input()))
    for j in range(n):
        if p[j]=='1':
            g[i].append(j)
q=deque([0])
v=[-1]*n
v[0]=0
while q:
    p=q.popleft()
    for i in g[p]:
        if v[i]==-1:
            v[i]=1-v[p]
            q.append(i)
        else:
            if v[i]!=1-v[p]:
                print(-1)
                exit()
ans=0
for s in range(n):
    q=deque([s])
    v=[0]*n
    v[s]=1
    while q:
        p=q.popleft()
        for i in g[p]:
            if v[i]==0:
                v[i]=1+v[p]
                q.append(i)
    ans=max(ans,max(v))
print(ans)

Submission status: Accepted

Solution code:
class Graph(): #non-directed
    def __init__(self,n,edge):
        self.n = n
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0] - 1].append(e[1] - 1)
            self.graph[e[1] - 1].append(e[0] - 1)

    def is_bipartite(self):
        group = [None for _ in range(self.n)]
        stack = [(0, 1)]
        while stack:
            node, nodecolor = stack.pop()
            group[node] = nodecolor
            for adj in self.graph[node]:
                if group[adj] == nodecolor:
                    return False
                if group[adj] is None:
                    adjcolor = 1 - nodecolor
                    stack.append((adj, adjcolor))
        return True

    def warshall_floyd(self, INF=10**18):
        dist = [[INF for j in range(self.n)] for i in range(self.n)]
        for i in range(self.n):
            dist[i][i] = 0
        for i in range(self.n):
            for j in self.graph[i]:
                dist[i][j] = 1
        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    if dist[i][k] != INF and dist[k][j] != INF:
                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        return dist

    def diam(self):
        res = 0
        dist = self.warshall_floyd()
        for i in range(self.n):
            for j in range(self.n):
                res = max(res, dist[i][j] + 1)
        return res

N = int(input())
E = []

for i in range(N - 1):
    S = list(map(int,input()))
    for j in range(i + 1, N):
        if S[j]:
            E.append((i + 1, j + 1))

G = Graph(N, E)

if G.is_bipartite():
    print(G.diam())

else:
    print(-1)

Submission status: Accepted

Solution code:
import scipy.sparse.csgraph as s
def b(u,x):c[u]=x;return all(d[u][v]^1or(c[u]!=c[v])&(c[v]or b(v,-x))for v in X)
N,*S=open(0)
N=int(N)
X=range(N)
d=[[i^j and(S[i][j]=='1'or N)for j in X]for i in X]
c=[0]*N
print(int(b(0,1)and s.floyd_warshall(d).max()+2)-1)

Submission status: Accepted

Solution code:
def b(u,x):
 c[u]=x
 return all((c[u]!=c[v])&(c[v]or b(v,-x))for v in X if d[u][v]==1)
N=int(input())
X=range(N)
S=[input()for _ in X]
d=[[1 if S[i][j]=='1'else(N if i^j else 0)for j in X]for i in X]
for k in X:
 for i in X:
  for j in X:d[i][j]=min(d[i][j],d[i][k]+d[k][j])
c=[0]*N
print(max(max(e)for e in d)+1 if b(0,1)else-1)

Submission status: Accepted

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

def floyd_warshall(dist):
    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])

def is_bipartite(u):
    for v in range(N):
        if u == v or dist[u][v] != 1:
            continue
        if color[v] == -1:
            color[v] = 1 - color[u]
            if not is_bipartite(v):
                return False
        elif color[u] == color[v]:
            return False
    return True

N = int(input())
S = [input().rstrip() for _ in range(N)]
dist = [[1 if S[i][j] == '1' else (0 if i == j else float('inf')) for j in range(N)] for i in range(N)]
color = [-1] * N
color[0] = 0
ans = 0
if is_bipartite(0):
    floyd_warshall(dist)
    ans = max(max(d) for d in dist) + 1
else:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque, defaultdict
import sys
input = sys.stdin.readline

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[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.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

N = int(input())
S = [input().rstrip() for _ in range(N)]
uf = UnionFind(N)
for i in range(N):
    for j in range(i):
        if S[i][j] == '1':
            uf.unite(i, j)
depth = defaultdict(int)
for i in range(N):
    color = [-1] * N
    queue = deque()
    queue.append((i, 1))
    color[i] = 0
    max_d = 1
    while queue:
        j, d = queue.popleft()
        max_d = max(max_d, d)
        for k in range(N):
            if k == j or S[j][k] == '0':
                continue
            if color[k] == -1:
                color[k] = 1 - color[j]
                queue.append((k, d+1))
            elif color[k] == color[j]:
                print(-1)
                exit()
    depth[uf.find(i)] = max(depth[uf.find(i)], max_d)
ans = sum(depth[i] for i in range(N))
print(ans)

Submission status: Accepted

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

read = sys.stdin.read
readline = sys.stdin.readline

N = int(readline())
S = np.array([list(i) for i in read().split()], np.int64)
edges = np.where(S == 1)

# 二部グラフかを判定する。隣り合う頂点の色が被らないように白黒で塗り分ける
graph = [[] for _ in range(N)]

for i, j in zip(edges[0].tolist(), edges[1].tolist()):
    graph[i].append(j)
    graph[j].append(i)


def judge(start):
    colors = [-1] * N
    colors[start] = 0
    queue = deque([(start, 0)])
    while queue:
        V, c = queue.popleft()
        c ^= 1
        for v in graph[V]:
            if colors[v] == -1:
                colors[v] = c
                queue.append((v, c))
            else:
                if colors[v] != c:
                    return False
    return True


start = edges[0][0]
if judge(start):
    d = floyd_warshall(S)
    print(int(np.max(d)) + 1)
else:
    print(-1)

Submission status: Accepted

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

read = sys.stdin.read
readline = sys.stdin.readline

N = int(readline())
S = np.array([list(i) for i in read().split()], np.int64)
edges = np.where(S == 1)

# 二部グラフかを判定する。隣り合う頂点の色が被らないように白黒で塗り分ける
graph = [[] for _ in range(N)]
start = None
for i, j in zip(edges[0].tolist(), edges[1].tolist()):
    graph[i].append(j)
    graph[j].append(i)
    start = i


def judge(start):
    colors = [-1] * N
    colors[start] = 0
    queue = deque([(start, 0)])
    while queue:
        V, c = queue.popleft()
        c ^= 1
        for v in graph[V]:
            if colors[v] == -1:
                colors[v] = c
                queue.append((v, c))
            else:
                if colors[v] != c:
                    return False
    return True


if judge(start):
    d = floyd_warshall(S)
    print(int(np.max(d)) + 1)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
sys.setrecursionlimit(10**7)

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

n = int(input())
S = np.frombuffer(read(),'S1').reshape(n, n+1)[:, :n].astype(np.int64)
G = csgraph_from_dense(S)

F = floyd_warshall(G).astype(np.int64)

C = [-1]*n
def dfs(v, c):
  C[v] = c
  for nv, i in enumerate(S[v]):
    if not i:
      continue
    if C[nv] != -1:
      if not (C[v] ^ C[nv]):
        return False
    else:
      if not dfs(nv, c^1):
        return False
  return True

if dfs(0, 0):
  ans = F.max() + 1
  print(ans)
else:
  print(-1)

Submission status: Accepted

Solution code:
from collections import deque
def bfs(G, s):
    cost=[-1]*len(G)
    cost[s]=1
    deq=deque([s])
    while deq:
        u=deq.popleft()
        for v in G[u]:
            if cost[v]<0:
                cost[v]=cost[u]+1
                deq.append(v)
            elif abs(cost[u]-cost[v])!=1:
                return -1
    return max(cost)

def main():
    N=int(input())
    S=[[bool(int(i)) for i in input()] for _ in range(N)]
    G=[[] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if S[i][j]:
                G[i].append(j)
    print(max(bfs(G,i) for i in range(N)))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

data=[[] for i in range(N)]
for y in range(N):
    for x in range(N):
        if S[y][x]=="1":
            data[y].append(x)

visited=[-1 for i in range(N)]
visited[0]=0
stack=[[0,0]]

while stack:
    a,m=stack.pop()
    for p in data[a]:
        if visited[p]==m:
            print(-1)
            exit()
        else:
            if visited[p]==-1:
                n=(m+1)%2
                visited[p]=n
                stack.append([p,n])


d=[[10**18 for m in range(N)] for i in range(N)]

for x in range(len(d)):
    d[x][x]=0
for x in range(len(data)):
    for y in data[x]:
        d[x][y]=1
        d[y][x]=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])
print(max([max([i for i in l]) for l in d])+1)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
N = int(input())
dic = defaultdict(list)
for i in range(N):
  inf = [int(c) for c in input()]
  for j in range(N):
    if inf[j]:
      dic[i] += [j]
      dic[j] += [i]
ans = 0
for i in range(N):
  q = deque([i])
  dist = [float('inf')]*N
  dist[i] = 0
  m = 0
  while q:
    p = q.popleft()
    for e in dic[p]:
      if dist[e]==dist[p]:
        print(-1)
        import sys
        sys.exit()
      if dist[e]>dist[p]+1:
        dist[e] = dist[p]+1
        q += [e]
        m = max(m,dist[e])
  ans = max(ans,m)
print(ans+1)

Submission status: Accepted

Solution code:
from sys import stdout
from collections import deque
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
dst = [ [] for i in range(n) ]
for i in range(n):
    s = input().strip()
    for j in range(n):
        if s[j]=='1':
            dst[i].append(j)
            dst[j].append(i)

ddprint(dst)

mx = 0
for i in range(n):
    d = [-1]*n
    d[i] = 0
    q = deque([i])
    while len(q)>0:
        x = q.popleft()
        for y in dst[x]:
            if d[y]>=0 and (d[y]-d[x])%2 == 0:
                ddprint("x {} y {} dx {} dy {}".format(x,y,d[x],d[y]))
                print(-1)
                exit()
            if d[y]<0:
                d[y] = d[x]+1
                mx = max(mx,d[y])
                q.append(y)
print(mx+1)

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
N = int(input())
edge = np.array([list(input()) for _ in range(N)]).astype(int)

def is_bipartite(N, edge):
    color = [-1]*N
    graph = [np.nonzero(i)[0].tolist() for i in edge]

    node = [0]
    color[0] = 0
    while node:
        s = node.pop()
        col_s = color[s]
        for t in graph[s]:
            col_t = color[t]
            if col_t == -1:
                color[t] = 1-col_s
                node.append(t)
            elif col_t == col_s:
                return False
            else:
                continue
    return True


if is_bipartite(N, edge):
    wf = floyd_warshall(edge).astype(int)
    ans = wf.max()+1
else:
    ans = -1

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
ls = [list(input()) for i in range(n)]
graph = [[] for i in range(n+1)]
visited = [0 for i in range(n+1)]
parity = [-1 for i in range(n+1)]
dist = [0 for i in range(n+1)]
for i in range(n):
  for j in range(i,n):
    if ls[i][j] == "1":
      graph[i+1].append(j+1)
      graph[j+1].append(i+1)
que = deque([(1,0)])
parity[1] = 0
visited[1] = 1
while que:
  x,cnt = que.popleft()
  dist[x] = cnt
  for y in graph[x]:
    if visited[y] == 0:
      que.append((y,cnt+1))
      visited[y] = 1
      parity[y] = 1-parity[x]
ans = []
for v in range(1,n+1):
  que.append((v,0))
  visited = [0 for i in range(n+1)]
  visited[v] = 1
  dist = [0 for i in range(n+1)]
  while que:
    x,cnt = que.popleft()
    dist[x] = cnt
    for y in graph[x]:
      if visited[y] == 0:
        que.append((y,cnt+1))
        visited[y] = 1
      if parity[y] == parity[x]:
        print(-1)
        exit()
  ans.append(max(dist))
print(max(ans)+1)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
ls = [list(input()) for i in range(n)]
graph = [[] for i in range(n+1)]
visited = [0 for i in range(n+1)]
parity = [-1 for i in range(n+1)]
dist = [0 for i in range(n+1)]
for i in range(n):
  for j in range(i,n):
    if ls[i][j] == "1":
      graph[i+1].append(j+1)
      graph[j+1].append(i+1)
que = deque([(1,0)])
parity[1] = 0
visited[1] = 1
while que:
  x,cnt = que.popleft()
  dist[x] = cnt
  for y in graph[x]:
    if visited[y] == 0:
      que.append((y,cnt+1))
      visited[y] = 1
      parity[y] = 1-parity[x]
# k = max(dist)
# farls = []
# for i in range(1,n+1):
#   if dist[i] == k:
#     farls.append(i)
ans = []
for far in range(1,n+1):
  que.append((far,0))
  visited = [0 for i in range(n+1)]
  visited[far] = 1
  dist = [0 for i in range(n+1)]
  while que:
    x,cnt = que.popleft()
    dist[x] = cnt
    for y in graph[x]:
      if visited[y] == 0:
        que.append((y,cnt+1))
        visited[y] = 1
      if parity[y] == parity[x]:
        print(-1)
        exit()
  ans.append(max(dist))
print(max(ans)+1)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    sa = [S() for _ in range(n)]
    e = collections.defaultdict(set)
    for i in range(n):
        s = sa[i]
        for j in range(i+1,n):
            if s[j] == '1':
                e[i].add(j)
                e[j].add(i)

    r = -1
    for i in range(n):
        k = 1
        a = [set(), set([i])]
        u = set([i])
        while len(u) < n:
            k += 1
            v = set()
            for c in a[k-1]:
                v |= e[c]
            v -= a[k-2]
            if len(v & u) > 0:
                k = -1
                break
            vv = set()
            for c in v:
                vv |= e[c]
            if len(vv & v) > 0:
                k = -1
                break
            a.append(v)
            u |= v
        if r < k:
            r = k

    return r


print(main())

Submission status: Accepted

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

INF = 10 ** 15

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

for i in range(N):
  for j in range(N):
    if S[i][j] == 0  and i != j:
      S[i][j] = INF

for k in range(N):
  for i in range(N):
    for j in range(N):
      S[i][j] = min(S[i][j], S[i][k] + S[k][j])
#print("S:", S)

answer = -2
for i in range(N):
  flag = 1
  for A, B in AB:
    if abs(S[i][A] - S[i][B]) != 1:
      flag = 0
      break
  if flag:
    answer = max(answer, max(S[i]))

print(answer + 1)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import numpy as np
import collections
from functools import cmp_to_key
import heapq

##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##
def main():
    N = ri()
    S = [""] * N
    for i in range(N): S[i] = rs()

    bw = [-1] * N
    q = collections.deque()
    bw[0] = 0
    q.append(0)
    while(len(q) > 0):
        now = q.popleft()
        for nxt in range(N):
            if S[now][nxt] == '0': continue
            if bw[nxt] == -1:
                bw[nxt] = bw[now] ^ 1
                q.append(nxt)
            elif bw[nxt] == bw[now]:
                print(-1)
                sys.exit(0)
    
    ma = 0
    e = [[] * N for i in range(N)]
    for i in range(N):
        for j in range(N):
            if(S[i][j] == '1'): e[i].append(j) 
    for i in range(N):
        dep = [-1] * N
        q = collections.deque()
        dep[i] = 0
        q.append(i)
        while(len(q) > 0):
            now = q.popleft()
            for nxt in e[now]:
                if dep[nxt] == -1:
                    dep[nxt] = dep[now] + 1
                    q.append(nxt)
        for j in range(N):
            ma = max(ma, dep[j])
    
    print(ma + 1)
        

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin
import sys
#import numpy as np
import collections
from functools import cmp_to_key
import heapq

##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##
def main():
    N = ri()
    S = [""] * N
    for i in range(N): S[i] = rs()

    bw = [-1] * N
    q = collections.deque()
    bw[0] = 0
    q.append(0)
    while(len(q) > 0):
        now = q.popleft()
        for nxt in range(N):
            if S[now][nxt] == '0': continue
            if bw[nxt] == -1:
                bw[nxt] = bw[now] ^ 1
                q.append(nxt)
            elif bw[nxt] == bw[now]:
                print(-1)
                sys.exit(0)
    
    inf = int(1e9)
    wf = [[inf] * N for i in range(N)]
    for i in range(N):
        for j in range(N):
            wf[i][j] = 1 if S[i][j] == '1' else inf
            if i == j: wf[i][j] = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])
    
    ma = 0
    for i in range(N):
        for j in range(N):
            ma = max(ma, wf[i][j])

    print(ma + 1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#二部グラフ化できるか
#最大深さ

from collections import deque

n = int(input())
s = []

for i in range(n):
    sij = input()
    s.append(sij)
    
d = [-1]*n

Q = deque()

d[0] = 0

Q.append(0)

while Q:
    v = Q.popleft()
    for i in range(n):
        if int(s[v][i]):
            if d[i]<0:
                d[i] = d[v] + 1
                Q.append(i)
            elif (d[i]-d[v])%2==0:
                print(-1)
                exit()

mxd = max(d)
mxd_id = d.index(mxd)

"""   
d2 = [-1]*n

d2[mxd_id] = 0

Q.append(mxd_id)

while Q:
    v = Q.popleft()
    for i in range(n):
        if int(s[v][i]):
            if d2[i]<0:
                d2[i] = d2[v] + 1
                Q.append(i)
"""

#最長距離の求め方をフロイドワーシャルに変更
dd = [[10**5 for i in range(n)] for j in range(n)]
for i in range(n):
    dd[i][i] = 0
    for j in range(n):
        if int(s[i][j]):
            dd[i][j] = 1
for k in range(n):
    for i in range(n):
        for j in range(n):
            dd[i][j] = min(dd[i][j], dd[i][k] + dd[k][j])
            

ans = 0

for i in range(n):
    for j in range(n):
        ans = max(ans, dd[i][j])

print(ans+1)

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse.csgraph import csgraph_from_dense
from collections import deque

n=int(input())
l=[]
ll=[]
E=[[] for i in range(n)]
# 二部グラフ判定用
V = [0 for i in range(n)]

for i in range(n):
    s=input()
    ll.append(s)
    for j in range(n):
        if s[j]=="1":
            l.append([i,j,1])
            E[i].append(j)
            E[j].append(i)

edge=np.array(l,dtype=np.int64).T
graph=csr_matrix(((edge[2],edge[:2])),(n,n))

dist_mat = floyd_warshall(graph).astype(np.int32)
 
max_d = dist_mat.max()
 
def dfs(cur, pre, col):
    stack = deque([[cur, pre, col]])
    while stack:
        cur, pre, col = stack.pop()
        if V[cur] and V[cur] != col:
            return False
        else:
            V[cur] = col
        for e in E[cur]:
            if e != pre:
                stack.append([e, cur, -1 * col])
        # 一度通った辺は通らない
        E[cur] = []
    return True
 
# 二部グラフ判定
if not dfs(0, -1, 1):
    print(-1)
    exit()

answer = max_d + 1
print(answer)

Submission status: Accepted

Solution code:
import sys
from collections import deque

n = int(input())

# 隣接行列と隣接リストを用意
dp = [[2*n for i in range(n)] for j in range(n)]
E = [[] for i in range(n)]

# 二部グラフ判定用
V = [0 for i in range(n)]

# 入力を受け取る
for i in range(n):
    s = input()
    for j in range(n):
        if s[j] == '1':
            E[i].append(j)
            dp[i][j] = 1
        if j == i:
            dp[i][j] = 0

def dfs(cur, pre, col):
    stack = deque([[cur, pre, col]])
    while stack:
        cur, pre, col = stack.pop()
        if V[cur] and V[cur] != col:
            return False
        else:
            V[cur] = col
        for e in E[cur]:
            if e != pre:
                stack.append([e, cur, -1 * col])
        # 一度通った辺は通らない
        E[cur] = []
    return True

# 二部グラフ判定
if not dfs(0, -1, 1):
    print(-1)
    sys.exit()

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

# 全頂点間の距離を求める
warshall_floyd()

# 直径を求める
diam = 0
for i in range(n):
    for j in range(n):
        diam = max(dp[i][j], diam)

print(diam+1)

Submission status: Accepted

Solution code:
def main():
    import numpy as np
    import scipy.sparse.csgraph as sp
    n = int(input())
    gg = [input() for _ in [0]*n]
    graph = [[] for _ in [0]*n]

    inf = float('inf')

    dist = np.full((n, n), inf)

    for i in range(n):
        dist[i, i] = 0
        for j in range(n):
            if gg[i][j] == "1":
                graph[i].append(j)
                dist[i, j] = 1
                dist[j, i] = 1
    q = [0]
    dp = [0]*n
    dp[0] = 1

    flag = True
    while q:
        i = q.pop()
        for j in graph[i]:
            if dp[j] == 0:
                dp[j] = dp[i]*(-1)
                q.append(j)
            elif dp[j] == dp[i]:
                flag = False
                break
        if flag is False:
            break

    dist = np.array(dist)

    if flag is False:
        print(-1)
    else:
        dist = sp.shortest_path(dist)
        print(int(max([max([i for i in j]) for j in dist])+1))


main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

N = int(input())
vec = [[] for _ in range(N)]
for i in range(N) :
    for j, v in enumerate(input()) :
        if v == '1' :
            vec[i].append(j)

def bfs(s) :
    dist = [float('inf')] * N
    queue = [(1, s)]
    dist[s] = 1
    
    while queue :
        co, cur = heappop(queue)
        if dist[cur] < co :
            continue
            
        for nex in vec[cur] :
            if co + 1 < dist[nex] :
                dist[nex] = co + 1
                heappush(queue, (co + 1, nex))
                
    for i in range(N) :
        for j in vec[i] :
            if abs(dist[i] - dist[j]) != 1 :
                return -1
    
    return max(dist)

ret = -1
for i in range(N) :
    ret = max(ret, bfs(i))
    
print(ret)

Submission status: Accepted

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

E = [set() for _ in range(N)]
for i in range(N):
  for j in range(N):
    if S[i][j] == '1':
      E[i].add(j)

C = [0 for _ in range(N)]
def dfs(v,c):
  C[v] = c
  for u in E[v]:
    if C[u] == c:
      return False
    if C[u] == 0 and not dfs(u,-c):
      return False
  return True

if not dfs(0,1):
  print(-1)
  exit()

G = [[float('inf') for _ in range(N)] for _ in range(N)]
for i in range(N):
  G[i][i] = 0
for i in range(N):
  for j in range(N):
    if S[i][j] == '1':
      G[i][j] = 1

for k in range(N):
  for i in range(N):
    for j in range(N):
      G[i][j] = min(G[i][k]+G[k][j],G[i][j])
ans = 0
for g in G:
  mx = max(g)
  ans = max(ans,mx)
print(ans+1)

Submission status: Accepted

Solution code:
q = list()
n = int(input())
a = [input() for _ in range(n)]
col = [-1]*n
col[0] = 0
q.append(0)
while q:
  v = q.pop()
  for i in range(n):
    if a[v][i] == '0':
      continue
    if col[i] < 0:
      col[i] = col[v]^1
      q.append(i)
    elif col[i] == col[v]:
      print(-1)
      exit(0)

dist = [[10**3]*n for _ in range(n)]
for i in range(n):
  for j in range(n):
    if a[i][j] == '1':
      dist[i][j] = 1
    elif i == j:
      dist[i][j] = 0

for k in range(n):
  for i in range(n-1):
    for j in range(i+1,n):
      if dist[i][j] > dist[i][k] + dist[k][j]:
        dist[i][j] = dist[i][k] + dist[k][j]
        dist[j][i] = dist[i][j]
print(max(max(x) for x in dist)+1)