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 deque, defaultdict
from itertools import combinations
from itertools import product

def bipartite(V, E):
    '''
    Input:
    V = [0, 1, ..., N-1]: a list of vertices of the graph
    E: the adjacency list of the graph
    Output:
    If the graph is bipartite, return [(U_1, U_2) (the parts of the bipartite graph) for each component].
    Else, return None.
    '''
    color = {v: None for v in V}
    part = []
    for v in V:
        if color[v] is not None: continue
        stack = [(v, 0)] # color v with 0
        parts = {0: [], 1: []}
        while stack:
            v, c = stack.pop()
            if color[v] is not None: # consistent
                continue
            color[v] = c
            parts[c].append(v)
            for u in E[v].keys():
                if color[u] is None: # not visited yet
                    stack.append((u, c^1)) # paint u with different color from v's one
                elif color[u] != c: # consistent
                    continue
                else: # inconsistent
                    return None
        part.append(parts)
    return part

def floyd_warshall(V, E):
    '''
    Input:
        V = list(range(N))
        E = defaultdict(dict)
    Output:
        If there exists a negative cycle, return (None, prev), where prev is
        the table, whose (i, j)-element is the previous vertices in the shortest (i, j)-path
        Otherwise return (dist, prev), where dist is the table of the minimum cost
        between arbitrary vertex u, v in the given graph
    '''
    INF = float('inf')
    N = len(V)
    dist = {u: {v: INF for v in V} for u in V}
    prev = {u: {v: None for v in V} for u in V}
    for v in V:
        dist[v][v] = 0; prev[v][v] = -1
        for u, c in E[v].items(): dist[v][u] = c; prev[v][u] = v;
    for k in V:        
        for i, j in product(V, repeat=2):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
                prev[i][j] = prev[k][j]
    for v in V:
        if dist[v][v] < 0: return None, prev
    return dist, prev

N = int(input())
V = list(range(N))
E = defaultdict(dict)
for u in range(N):
    for v, s in enumerate(input()):
        if s == '1': E[u][v] = 1
if bipartite(V, E) is None:
    print(-1)
else:
    dist, _ = floyd_warshall(V, E)
    diameter = -1
    for u, v in combinations(V, 2):
        diameter = max(diameter, dist[u][v])
    print(diameter + 1)

Submission status: Accepted

Solution code:
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 check(vSt):
    vs = set([vSt])
    useds = [False] * (N)
    useds[vSt] = True
    depth = 0
    while vs:
#        print(depth, vs)
        v2s = set()
        for v in vs:
            for v2 in adjL[v]:
                if not useds[v2]:
                    v2s.add(v2)
                    useds[v2] = True
        for u in v2s:
            for v in v2s:
                if Sss[u][v] == '1':
                    return -1
        vs = v2s
        depth += 1
    return depth

ans = -1
for v in range(N):
    ret = check(v)
    if ret != -1:
        ans = max(ans, ret)

print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


def dfs(graph: list, node: int, start: int) -> list:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF] * node

    # 始点ノードの距離を0とし、dfsのためのstackを作成
    dist[start] = 0
    stack = [(0, start)]

    while stack:
        cost, cur_node = stack.pop()

        # 未探索のノードをstackに入れる
        for nex_cost, nex_node in graph[cur_node]:
            if dist[nex_node] != INF:
                continue
            else:
                dist[nex_node] = dist[cur_node] + nex_cost
                stack.append((dist[nex_node], nex_node))

    return dist

def judge(graph, edges):
    node = len(graph)
    start = 0

    dist = dfs(graph, len(graph), 0)

    for i, j in edges:
        if abs(dist[i]-dist[j])%2 == 0:
            return False

    return True

import numpy as np

n = ni()
grid = [lc() for _ in range(n)]
graph = [[] for _ in range(n)]
numgraph = np.zeros((n, n))
edges = []
for row, si in enumerate(grid):
    for col, sij in enumerate(si):
        if sij == "1":
            edges.append((row, col))
            graph[row].append((1, col))
            numgraph[row][col] = 1

# 二部グラフ判定
is_nibu = judge(graph, edges)

if is_nibu:
    from scipy.sparse.csgraph import floyd_warshall
    dists = floyd_warshall(numgraph)
    ans = 0
    for i in range(n):
        ans = max(ans, max(dists[i,:]))

    print(int(ans) + 1)

else:
    print(-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#AGC39 B

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

def is_bipartite():
    return dfs(0,1)

def warshall_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 = I()
S = [input() for _ in range(n)]
dist = [[inf]*n for _ in range(n)]
colors = [0]*n
es = [[] for _ in range(n)]
for i in range(n):
    s = S[i]
    for j in range(i+1,n):
        if s[j] == '1':
            dist[i][j] = 1
            dist[j][i] = 1
            es[i].append(j)
            es[j].append(i)

for i in range(n):
    dist[i][i] = 0
d = warshall_floyd(dist)
flg = is_bipartite()
if not flg:
    print(-1)
    quit()
ans = 0
for i in range(n):
    ans = max(ans,max(d[i]))
print(ans+1)

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**7)
n=int(input())
l=[list(input()) for i in range(n)]
colors = [0 for i in range(n)]
es=[[] for i in range(n)]
Edges=es
for i in range(n):
  for j in range(n):
    if l[i][j]=='1':
      es[i].append(j)
def dfs(v,color):
    colors[v] = color
    for to in es[v]:
        if colors[to] == color:
            return False
        if colors[to] == 0 and not dfs(to, -color):
            return False
    return True
 
def is_bipartite():
    return dfs(0,1)
if is_bipartite()==0:
  print(-1)
  sys.exit()


def bfs(v):
    Visited=[False]*n
    q=deque()
    q.append((v,0))
    Visited[v]=True
    ret=(v,0)
    while q:
        fr,dist=q.popleft()
        if ret[1]<dist:
            ret=(fr,dist)
        for to in Edges[fr]:
            if not Visited[to]:
                Visited[to]=True
                q.append((to,dist+1))
    return ret

ans=[]
for i in range(n):
  ans.append(bfs(i)[1])
print(max(ans)+1)

Submission status: Accepted

Solution code:
from collections import deque

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

E = [[] for _ in range(N)]
for i, s in enumerate(S):
    for j in range(N):
        if s[j] == "1":
            E[i].append(j)
            E[j].append(i)

def solve(a):
    rank = [-1] * N
    rank[a] = 0

    Q = deque([a])
    while Q:
        v = Q.popleft()
        r = rank[v]
        for u in E[v]:

            if rank[u] == -1:
                rank[u] = r + 1
                Q.append(u)

            elif rank[u] == r:
                return -2

    return max(rank)


print(max(solve(i) for i in range(N)) + 1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")
from collections import deque

import sys
import math
from collections import defaultdict, deque
INF = float("inf")


class Graph(object):
    """グラフを扱うオブジェクト
    """

    def __init__(self, N):
        self.N = N
        self.E = [[] for _ in range(N)]
        pass

    def add_edge(self, from_, to_):
        """必ず0インデックスで入力すること。
        """
        self.E[from_].append((to_, 1))
        pass


def solve(N: int, S: "List[str]"):

    g = Graph(N)
    for i, s in enumerate(S):
        for j, c in enumerate(s):
            if c == "1":
                g.add_edge(i, j)

    ddd = -1
    for node in range(N):
        depth = [-2]*N
        q = deque()
        q.append((node, 1))
        while len(q) > 0:
            node, d = q.popleft()
            if depth[node] != -2:
                continue
            depth[node] = d
            for i, w in g.E[node]:
                if depth[i] == -2:
                    q.append((i, d+1))
                elif d == depth[i]:
                    print(-1)
                    return
        ddd = max(ddd, d)
    print(ddd)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, S)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
connect_matrix = [ list(input()) for i in range(n) ]

def bfs(x):
    node_set = [ None for i in range(n)]
    color_list = [ "White" for i in range(n) ]
    search_list = [x]
    d = 0
    node_set[x] = 0
    color_list[x] = "Black"
    ans = 0
    while search_list != []:
        d += 1
        new_search_list = []
        for i in search_list:
            for j, v in enumerate(connect_matrix[i]):
                if v == "1":
                    if color_list[j] == "White":
                        if node_set[j] is None:
                            node_set[j] = node_set[i] + 1

                        new_search_list.append(j)
                        color_list[j] = "Black"
                    else:
                        if (node_set[j] + node_set[i]) % 2 == 0:
                            ans = -1
        search_list = new_search_list
    return ans, d-1

judge_list = []
dist_list = []
for i in range(n):
    a = bfs(i)
    judge_list.append(a[0])
    dist_list.append(a[1])

if -1 in judge_list:
    print(-1)
else:
    print(max(dist_list)+1)

Submission status: Accepted

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

M = [set(y for y in range(N) if S[x][y]) for x in range(N)]
v_max = -1
for i in range(N):
  V = [set([i])]
  nodes = set(range(N)) - V[0]
  while len(nodes) > 0:
    V.append(set().union(*[M[x] for x in V[-1]]).intersection(nodes))
    for v in V[-1]:
      if V[-1] & M[v]:
        break
    else:
      nodes -= V[-1]
      continue
    break
  else:
    v_max = max(v_max, len(V))
print(v_max)

Submission status: Accepted

Solution code:
n=int(input())
gg=[input() for _ in [0]*n]
graph=[[] for _ in [0]*n]


inf=10**10
dist=[[inf for _ in [0]*n] for _ in [0]*n]

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==False:
        break

        

if flag==False:
    print(-1)
else:
    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]))
    print(max([max([i for i in j]) for j in dist])+1)

Submission status: Accepted

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

n = int(input())
s = list()
for i in range(n):
    s.append([int(x) for x in list(input())])
s=np.array(s)
d=floyd_warshall(csr_matrix(s))
c=d[:, np.argmax(d)%n]
for i in range(n):
    for j in range(i+1, n):
        if (s[i, j] == 1) and abs(c[i] - c[j]) != 1:
            print(-1)
            exit()
r=int(np.amax(d)+1)
print(r)

Submission status: Accepted

Solution code:
from collections import deque

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

def bfs(s, start):
    plan = deque([(start, 0)])
    lengths = {}
    while len(plan) > 0:
        vertex, length = plan.popleft()
        if vertex in lengths:
            if (lengths[vertex] - length) % 2 != 0:
                return -1
        else:
            lengths[vertex] = length
            plan.extend([(i, length + 1) for i, c in enumerate(s[vertex]) if c == 1 and i not in lengths])
    return max(lengths.values())

bfs_result = 0
for start in range(n):
    res = bfs(s, start)
    if res < 0:
        bfs_result = -2
        break
    elif res > bfs_result:
        bfs_result = res
print(bfs_result + 1)

Submission status: Accepted

Solution code:
N=int(input())

graph=[]
for i in range(N):
  graph.append([])

for i in range(N):
  S=list(map(int,input()))
  for j in range(N):
    if S[j]==1:
      graph[i].append(j)
      
#print(graph)
max_set=-1
for i in range(N):
  node_list=[-1]*N
  #bfs
  d=1
  queue={i}
  illegal=False
  while(True):
    new_queue=set()
    for q in queue:
      node_list[q]=d
      for qq in graph[q]:
        if node_list[qq]==-1:
          new_queue.add(qq)
        elif node_list[qq]!=d-1:
          illegal=True
          break
      
    if illegal:
      break
    elif len(new_queue)==0:
      #print(node_list,d)
      max_set=max(max_set,d)
      break
    else:
      #print(node_list,new_queue)
      queue=new_queue
      d+=1
      
print(max_set)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import dijkstra as di
from collections import deque

def dfs(graph, start, n):
    queue = deque()
    tmp = []
    visited = [0] * n
    queue.append(start)
    visited[start] = 1

    while queue:
        a = queue.popleft()
        for j in range(n):
            if not graph[a][j]:
                continue
            elif graph[a][j] and not visited[j]:
                queue.append(j)
                visited[j] = visited[a] + 1
            elif graph[a][j] and visited[j]:
                if abs(visited[a] - visited[j]) != 1:
                    # print(a, j, visited[a], visited[j], start, visited)
                    return False
    return True

n = int(input())
ad_lst = [list(map(int, input())) for _ in range(n)]
p_route = di(ad_lst)
ans = 0
mx = [0,0]
for i in range(n):
    for j in range(n):
        if p_route[mx[0]][mx[1]] < p_route[i][j]:
            mx = [i,j]
print(int(p_route[mx[0]][mx[1]] + 1) if dfs(ad_lst, mx[0], n) else -1)

Submission status: Accepted

Solution code:
n=int(input())
t=[[]for i in range(n)]
for i in range(n):
    c=input()
    for j in range(n):
        if c[j]=="1":
            t[i].append(j)
def f(x):
    a=[-1]*n
    a[x],q=1,[[x,1]]
    while q:
        b,c=q.pop(0)
        for i in t[b]:
            if a[i]!=-1:
                if abs(a[i]-c)!=1:
                    return -1
                    break
            else:
                a[i]=c+1
                q.append([i,c+1])
    return max(a)
print(max([f(i)for i in range(n)]))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
#ts=time.time()
#sys.setrecursionlimit(10**6)
#input=sys.stdin.readline
show_flg=False
#=True

inf=float('inf')
n=I()
s=[[inf]*n for _ in range(n)]
g=[[] for i in range(n)]
for r in range(n):
    ri=list(input())
    for c in range(n):
        if ri[c]=='1':
            s[r][c]=1
            g[r].append(c)  

def wf(d):
    n=len(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

d=wf(s)
diam=-1
bg=0
ed=n-1
for r in range(n):
    for i,dist in enumerate(d[r]):
        if i==r:
            continue
        if diam<dist:
            diam=dist
            bg=r
            ed=i

v=[-1]*(n)

def bfs(x):
    p=deque()
    p.append(x)
    v[x]=0
    while p:
        c=p.popleft()
        for i in g[c]:
            if v[i]==-1:
                p.append(i)
                v[i]=v[c]+1
    return

bfs(bg)

for i in range(n):
    for nb in g[i]:
        if abs(v[nb]-v[i])!=1:
            print(-1)
            exit()
            #show(i,nb,v[i],v[nb])

print(diam+1)
exit()
'''
show(s)
show(wf(s))
show(diam,bg,ed)
show(v)
'''

Submission status: Accepted

Solution code:
import sys
from collections import deque

n = int(input())
nex = [[] for _ in range(n)]
d = [[1000]*n for _ in range(n)]
for i in range(n):
    ni = list(sys.stdin.readline().rstrip())
    for j in range(n):
        if ni[j] == '1':
            nex[i].append(j)
            d[i][j] = 1
        elif i == j:
            d[i][j] =0
        else:
            d[i][j] = 1000000

maxi = 0
maxii = 0
vr = [set() for _ in range(n)]
nexcache = deque()
di = 1
dil = [-1] * n
dil[0] = 0
vr[0].add(0)
for i in range(len(nex[0])):
        vr[nex[0][i]].add(1)
        vr[nex[0][i]].add(-1)
        nexcache.append(nex[0][i])
        maxi = 1
        maxii = nex[0][i]
        dil[nex[0][i]] = 1
error = False
while len(nexcache) > 0:
    nnx = []
    for ne in nexcache:
        couho = set()
        for i in vr[ne]:
            couho.add(i+1)
            couho.add(i-1)
        for i in nex[ne]:
            if dil[i] == -1:
                vr[i] = vr[i].union(couho)
                nnx.append(i)
                dil[i] = di+1
                if maxi < di+1:
                    maxi = di+1
                    maxii = i
            else:
                if dil[i] != di-1 and dil[i] != di+1:
                    error = True
                    break
        if error:
            break
    di+=1
    nexcache = nnx

if error:
    print(-1)
    exit()

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

result = 0
for i in range(n):
    for j in range(i):
        if d[i][j] > result:
            result = d[i][j]

print(result+1)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
S = [list(input()) for _ in range(N)]


def bfs(i):

    d = [-1 for _ in range(N)]
    d[i] = 0

    que = deque([(i, 0, -1)])

    finished = set()
    while que:
        ci, dist, p = que.popleft()
        # print(ci, dist, p)

        for j in range(N):
            if S[ci][j] == '1':
                if j != p and d[j] >= 0:
                    if d[j] == dist or (d[j] != dist+1 and j not in finished):
                        # print(ci, j)
                        return -1
                elif d[j] == -1:
                    d[j] = dist+1
                    que.append((j, dist+1, ci))
        finished.add(ci)

    return dist+1


ans = -1
for i in range(N):
    b = bfs(i)
    ans = max(ans, b)

print(ans)

Submission status: Accepted

Solution code:
import collections

def read():
    N = int(input().strip())
    S = list()
    for i in range(N):
        has_nodes = list(input().strip())
        s = list()
        for i, has_node in enumerate(has_nodes):
            if has_node == '1':
                s.append(i)
        S.append(s)
    return N, S

def bfs(start, V, graph):
    q = collections.deque()
    q.appendleft(start)
    depth = [-1] * V
    depth[start] = 0
    while len(q) > 0:
        s = q.pop()
        for t in graph[s]:
            if depth[t] == -1:
                depth[t] = depth[s] + 1
                q.appendleft(t)
    return depth

def argsort(seq):
    return sorted(range(len(seq)), key=seq.__getitem__)

def make_groups(V, depth):
    max_depth = max(depth)
    groups = dict()
    for v in range(V):
        d = depth[v]
        if d in groups.keys():
            groups[d].append(v)
        else:
            groups[d] = [v]
    return groups

def has_edge_in_sibling_nodes(V, graph, depth):
    for i in range(V):
        for j in range(i+1, V):
            if depth[i] == depth[j]:
                if j in graph[i]:
                    return True
    return False


def solve(N, S):
    # 全ての頂点に対してbfs、条件を満たす最大の深さを出力
    max_depth = -1
    for i in range(N):
        depth = bfs(i, N, S)
        if not has_edge_in_sibling_nodes(N, S, depth):
            max_depth = max(max_depth, max(depth) + 1)
    return max_depth

if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))

Submission status: Accepted

Solution code:
N=int(input())
S=[input() for _ in range(N)]
min_v=200
for i in range(N):
  v=S[i].count('1')
  if v<min_v:
    min_v=v
start_candidates=[]
for i in range(N):
  start_candidates.append(i)
ans_lst=[]
for start in start_candidates:
  visited=[False for _ in range(N)]
  visited[start]=True
  current=[start]
  ans=1
  while True:
    flag=True
    candidates=[]
    for i in current:
      for j in range(N):
        if not visited[j] and S[i][j]=='1':
          candidates.append(j)
          visited[j]=True
    if not candidates:
      break
    #1 candidatesの中に辺を持つ頂点対があるとout
    for a in candidates:
      for b in candidates:
        if S[a][b]=='1':
          ans=-1
          flag=False
          break
      if not flag:
        break
    if not flag:
      break
    #1 end
    ans+=1
    current=candidates
  ans_lst.append(ans)
print(max(ans_lst))

Submission status: Accepted

Solution code:
import copy
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

N = int(input())
graph = [[int(a) for a in list(input().rstrip())] for _ in range(N)]
INF = 10**9

dis = copy.deepcopy(graph)
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        if dis[i][j] == 0:
            dis[i][j] = INF

for k in range(N):
    for i in range(N):
        for j in range(N):
            dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j])

state = [[] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            state[i].append(j)

D = [INF for _ in range(N)]
checked = [False for _ in range(N)]
D[0] = 0
checked[0] = True
ok = True

def dfs(p, d, ok):
    for np in state[p]:
        if checked[np]:
            c = d + 1 - D[np]
            if c > 1 and c % 2 == 1:
                ok = False
        else:
            checked[np] = True
            D[np] = d+1
            ok = dfs(np, d+1, ok)
    return ok

ok = dfs(0, 0, ok)

if not ok:
    print(-1)
else:
    ans = 0
    for i in range(N):
        for j in range(N):
            ans = max(ans, dis[i][j]+1)
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
dist = []
neighbours = [[] for i in range(N)]
for i in range(N):
    line = list(input())
    dist.append([1 if c == '1' else float('inf') for c in line ])
    for j, char in enumerate(line):
        if char == '1': neighbours[i].append(j)

for i in range(N): dist[i][i] = 0
# Find diameter
for k in range(N):
    for i in range(N):
        for j in range(N):
            if dist[i][k] + dist[k][j] < dist[i][j]:
                dist[i][j] = dist[i][k] + dist[k][j]

startVertex = 0
startDiam = 0
for i in range(N):
    for j in range(N):
        if dist[i][j] > startDiam:
            startDiam = dist[i][j]
            startVertex = i
            
isPossible = True

# Dijkstra
distances = [float('inf') for i in range(N)]
visited = [False for i in range(N)]

distances[startVertex] = 0

while True:
    curNode = min(range(N), key=lambda n:(visited[n], distances[n]))

    if visited[curNode]:
        break
    visited[curNode] = True

    for neighbour in neighbours[curNode]:
        if distances[neighbour] == float('inf'):
            distances[neighbour] = distances[curNode] + 1
        else:
            if abs(distances[neighbour] - distances[curNode]) != 1:
                isPossible = False

if not isPossible:
    print(-1)
else:
    total = len(set(distances))
    print(total)

Submission status: Accepted

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



ans=0
for i in range(1,n+1):
    bubun=[[] for iii in range(n+1)]
    bubun[0].append(i)
    check=0
    for j in range(n):
        for k in bubun[j]:
            for y in edge[k]:
                if y in bubun[j-1]:
                    continue
                elif y in bubun[j]:
                    break
                elif y in bubun[j+1]:
                    continue
                else:
                    bubun[j+1].append(y)
            else:
                continue
            break
        else:
            continue
        break
    else:
        for ii in bubun:
            if ii:
                check+=1
        ans=max(ans,check)
if ans==0:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
G = {i:[] for i in range(N)}
for i in range(N):
    S = input().strip()
    for j in range(N):
        if S[j]=="1":
            G[i].append(j)
cmax = 0
for i in range(N):
    hist = [0 for _ in range(N)]
    hist[i]=1
    num = 0
    heap = deque([(i,1)])
    ind = 0
    while ind==0 and num<N:
        cur = heap.popleft()
        num += 1
        y = cur[0]
        g = cur[1]
        cmax = max(cmax,g)
        for x in G[y]:
            if hist[x]==0:
                heap.append((x,g+1))
                hist[x]=g+1
            elif hist[x]==hist[y]:
                ind = 1
                break
    if ind==1:break
if ind==1:
    print(-1)
else:
    print(cmax)

Submission status: Accepted

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

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

from collections import deque

ans_tmp = 0
possible = True
for home in range(N):
    iswhite = [None] * N
    q = deque([(home, False, 0)])
    iswhite[home] = False
    while len(q) > 0:
        src, white, depth = q.popleft()
        # print("##", src, white, depth)
        if depth > ans_tmp:
            # home = src
            ans_tmp = depth
        #
        for dst in graph[src]:
            # print("###", dst, iswhite[dst])
            if iswhite[dst] == None:
                white_dst = (white != True)
                q.append((dst, white_dst, depth + 1))
                iswhite[dst] = white_dst
            elif white == iswhite[dst]:
                possible = False
                break
            else:
                continue
        #
        if possible == False:
            break
    
if possible:
    print(ans_tmp + 1)
else:
    # print("#", iswhite)
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque

class UnionFind:
    def __init__(self, n):
        self.rank = [0]*n
        self.parent = [i for i in range(n)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def merge(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
        elif self.rank[x] > self.rank[y]:
            self.parent[y] = x
        else:
            self.parent[x] = y
            self.rank[y] += 1

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



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

min_i = 0
min_count = n + 1
for i in range(n):
    count = 0
    for j in range(n):
        if s[i][j]:
            count += 1
    if count < min_count:
        min_count = count
        min_i = i

uf = UnionFind(n)

INF = 1001001001
ans = 0

for min_i in range(n):
    dist = [INF] * n
    dist[min_i] = 0
    q = deque([(min_i, 0, -1)])

    while q:
        v, d, p = q.popleft()
        box = []
        for nv in range(n):
            if s[v][nv] == '1':
                if nv == p:
                    continue
                if uf.same(v, nv):
                    print(-1)
                    exit()
                if d + 1 < dist[nv]:
                    dist[nv] = d + 1
                    q.append((nv, d + 1, v))
                    box.append(nv)
        for i in range(len(box) - 1):
            uf.merge(box[i], box[i + 1])
    ans = max(ans, max(dist) + 1)

print(ans)