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:
N = int(input())
S = [list(map(int, list(input()))) for _ in range(N)]
for i in range(N):
  for j in range(N):
    if i == j:
      continue
    if S[i][j] == 0:
      S[i][j] = float("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)
"""
g = [[0] * N for _ in range(2 * N)]
ig = [0] * N
order = [i for i in range(N)]
order.sort(key = lambda x: -max(S[x]))
g[N][order[0]] = 1
ig[order[0]] = N
"""
color = [0] * N
def dfs(v, c):
  global color
  color[v] = c
  for i in range(N):
    if S[v][i] == 1:
      if color[i] == c:
        return False
      if color[i] == 0 and not (dfs(i, -c)):
        return False
  return True

if dfs(1, 1):
  res = 0
  for r in S:
    res = max(max(r), res)
  print(res + 1)
else:
  print(-1)

Submission status: Accepted

Solution code:

def acinput():
    s=input()
    if len(s)==0:
        return False

    return list(map(int,s.split(" ")))
    

def search(x):
    global g,N,nodenum
    queue=[(x,1)]
    wnum=2
    nodenum=[-1]*N
    nodenum[x]=1
    visited=[0]*N
    while True:
        nqueue=[]
        for node,k in queue:
            for snode in g[node]:
                if nodenum[snode]<0:                    
                    nodenum[snode]=wnum
                    nqueue.append((snode,wnum))
                else:
                    if (not visited[snode]) and nodenum[snode]!=wnum:
                        return -1
            visited[node]=1

        queue=nqueue
        if len(queue)==0:
            return wnum-1
        wnum+=1
        
        

N=int(input())

g=[[] for i in range(N)]
for i in range(N):
    s=list(input())
    for j in range(len(s)):
        if s[j]=="1":
            g[i].append(j)

res=-1
for i in range(N):
    res=max(res,search(i))

print(res)

Submission status: Accepted

Solution code:
import sys
from bisect import *
from collections import *
from copy import deepcopy
from datetime import *
from heapq import *
from itertools import *
# from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    N = int(input())
    graph = [set() for _ in range(N)]
    for i in range(N):
        S = input().rstrip()
        for j in range(N):
            if S[j] == '1':
                graph[i].add(j)
    # graphには頂点iにつながっている頂点が入っている
    # graphの適当な点から初めて、取れるだけ列挙していく
    ans = -1
    for i in range(N):
        visited = {i}
        cur_points = {i}
        tmp = 1
        # 全て訪問し終えるまで
        while len(visited) < N:
            next_points = set()
            # 現在のポイントからまだ言っていないところを全列挙
            for point in cur_points:
                next_points |= graph[point]
            next_points -= cur_points
            # 次のポイントないで繋がりがあるものはないか
            link_checker = False
            for point in next_points:
                if graph[point] & next_points:
                    link_checker = True
                    break
            # 繋がりがあればここはダメ。次の頂点から始める
            if link_checker:
                break
            # 繋がりがないなら、cur_pointsを更新して次へ
            visited |= next_points
            cur_points = next_points
            tmp += 1
        else:
            ans = max(ans,tmp)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
S = [list(map(int,input())) for i in range(n)]
Graph = [[] for i in range(n)]
for i in range(n):
    for j in range(n):
        if S[i][j]==1:
            Graph[i]+=[j]
colors = [0 for i in range(n)]

def is_bipartite(es):
    stack = [(0,1)]
    while stack:
        v,color = stack.pop()
        colors[v] = color
        for to in es[v]:
            if colors[to] == color:
                 return False
            if colors[to] == 0:
                 stack.append((to, -color))
    return True

if not is_bipartite(Graph):
    print(-1)
    exit()

S2 = [[float("inf") for i in range(n)] for i in range(n)]
for i in range(n):
    for j in range(n):
        if S[i][j]==1:
            S2[i][j]=1
        elif i==j:
            S2[i][j]=0

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

warshall_floyd(S2)

diam = 0
for i in range(n):
    for j in range(n):
        diam = max(diam,S2[i][j])
print(diam+1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def main():
    N = int( input())
    S = [ list( map( int, list( input())[:-1])) for _ in range(N)]
    E = [[] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if S[i][j] == 1:
                E[i].append(j)
    
    d = deque([0])
    V = [-1]*N
    V[0] = 1
    
    while d:
        v = d.pop()
        now = V[v]
        for w in E[v]:
            if V[w] == -1:
                V[w] = now+1
                d.append(w)
                continue

            if (now + V[w])%2 == 1:
                continue
            print(-1)
            return
    ans = 2

    for i in range(N):
        d = deque([i])
        V = [-1]*N
        V[i] = 1
        check = True
        while d:
            v = d.popleft()
            now = V[v]
            for w in E[v]:
                if V[w] == -1:
                    V[w] = now+1
                    d.append(w)
                    continue
                if now+1 == V[w] or now-1 == V[w]:
                    continue
                check = False
                break
            if not check:
                break
        if not check:
            continue
        if max(V) > ans:
            ans = max(V)
    print(ans)
    
            
                
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


class Node(object):

  def __init__(self, idx):
    self.idx = idx
    self.edges = []
    self.depth = -1

  def __str__(self):
    return '{}: -> {}'.format(self.idx, ','.join(str(e.idx) for e in self.edges))


def search(nodes):
  new_nodes = set()

  for node in nodes:
    for edge in node.edges:
      if edge.depth == -1:
        edge.depth = node.depth + 1
        new_nodes.add(edge)
      elif abs(edge.depth - node.depth) != 1:
        return False

  if len(new_nodes) == 0:
    return True

  return search(new_nodes)


def main():
  nodes = [Node(i) for i in range(int(input()))]
  value = 0

  for i in range(len(nodes)):
    for j, v in enumerate(map(int, input().strip())):
      if v == 1:
        nodes[i].edges.append(nodes[j])

  for i in range(len(nodes)):
    for node in nodes:
      node.depth = -1

    start = nodes[i]
    start.depth = 1

    if not search([start]):
      print(-1)
      return

    for node in nodes:
      value = max(node.depth, value)

  print(value)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
#warshall_floyd法
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 = int(input())
d = [[float("inf") for i in range(n)] for i in range(n)] 
l=[]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(n):
    s=input()
    for j in range(n):
        if s[j]=="1":
            d[i][j] = 1
            l.append([i,j])
for i in range(n):
    d[i][i] = 0
wf=warshall_floyd(d)
visited = [1]+[0 for i in range(n-1)]
for _ in range(1000):
    for i in l:
        if visited[i[0]]!=0:
            if visited[i[0]]==1:
                if visited[i[1]]==1:
                    print(-1)
                    exit()
                elif visited[i[1]]==0:
                    visited[i[1]]=-1
            else:
                if visited[i[1]]==-1:
                    print(-1)
                    exit()
                elif visited[i[1]]==0:
                    visited[i[1]]=1
ans=0
for i in wf:
    ans=max(ans,max(i)+1)
print(ans)

Submission status: Accepted

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

adj_dict={i:[] for i in range(N)}

for i in range(N):
  for j in range(i,N):
    if S[i][j]:
      adj_dict[i].append(j)
      adj_dict[j].append(i)

ans = 0
for i in range(N):
  #頂点iから開始
  l=0
  visited = set([i])
  prev_layer = set()
  cur_layer = set([i])
  next_layer = set()
  
  #visited管理しなくてもN回でよい
  while len(visited)<N:
    l+=1
    for v in cur_layer:
      visited.add(v)
      for u in adj_dict[v]:
        if u in cur_layer:
          print(-1)
          exit()
        next_layer.add(u)
    prev_layer = cur_layer
    cur_layer = next_layer
    next_layer = set()
  ans = max(ans,l)
  
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
s = []
for i in range(N):
    s.append(list(input()))
for i in range(N):
    s[i] = [int(j) for j in s[i]]

from collections import deque
from collections import defaultdict

g = defaultdict(set)

for i in range(N):
    for j in range(N):
        if s[i][j] == 1:
            g[i+1].add(j+1)
            g[j+1].add(i+1)

ans = -1
for i in range(N):
    q = []
    q.append(i+1)
    visit = [-1]*(N+1)
    visit[i+1] = 1
    temp = 0
    while q:
        nextq = []
        for now in q:
            for next in g[now]:
                if visit[next] == -1:
                    visit[next] = visit[now] + 1
                    nextq.append(next)
                else:
                    if abs(visit[next] - visit[now]) == 1:
                        continue
                    else:
                        temp = -1
        if temp == -1:
            break
        q = nextq[:]
    if temp != -1:
        ans = max(max(visit), ans)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
s = [input() for i in range(n)]
ans = -2
for k in range(n):
    q = deque([k])
    d = [float('inf')] * n
    d[k] = 0
    while q:
        flg = 0
        p = q.popleft()
        for i, c in enumerate(s[p]):
            if c == '1':
                if d[i] == float('inf'):
                    d[i] = d[p] + 1
                    q.append(i)
                elif d[i] != d[p] + 1 and d[i] != d[p] - 1:
                    flg = 1
                    break
        if flg:
            break
    if flg:
        continue
    for i in range(n):
        ans = max(ans, d[i])
print(ans + 1)

Submission status: Accepted

Solution code:
#  --*-coding:utf-8-*--


def f(N, S, st):
    R = [0]*(N)

    Q = set([st])
    R[st] = 1
    idx = 1
    cnt = 0

    while(len(Q) > 0):
        Q2 = set()
        cnt += 1
        idx += 1
        
        for i in Q:
            for j, s in enumerate(S[i]):
                if s == '1':
                    if R[j] == idx - 1:
                        return -1
                    elif R[j] == 0:
                        R[j] = idx
                        Q2.add(j)
                    
        Q = Q2
        
    return cnt
        


def g(N, S):
    m = 0

    for i in range(N):
        k = f(N, S, i)
        if k == -1:
            return -1

        m = max(m, k)

    return m



def main():
    N = int(input())
    S = list(input() for _ in range(N))

    print(g(N, S))





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

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

M = [[] for i in range(n)]
for i in range(n):
    for j in range(n):
        if S[i][j] == "1":
            M[i].append(j)
ans = -1
owa = 0
for i in range(n):
    a0 = -1
    Q = [[i, 0]]
    st = 0
    D = [-1] * n
    while st < len(Q):
        a = Q[st][0]
        d = Q[st][1]
        D[a] = d
        for x in M[a]:
            if D[x] == -1:
                Q.append([x, d+1])
                D[x] = d+1
            elif D[x] != d-1 and D[x] != d+1:
                owa = 1
                break
        if owa == 1:
            break
        st += 1
    if owa == 0:
        a0 = max(D)+1
    ans = max(ans, a0)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
G = []
for i in range(n):
    a = []
    for j, c in enumerate(map(int, input())):
        if c == 1:
            a.append(j)
    G.append(a)

from collections import deque

def bfs(i):
    used = [-1]*n
    used[i] = 0
    que = deque()
    que.append(i)
    depth = 0
    while que:
        nxt = deque()
        while que:
            a = que.pop()
            for to in G[a]:
                if used[to] >= 0 and (used[to] != depth-1 and used[to] != depth+1):
                    return 0
                if used[to] < 0 :
                    nxt.append(to)
                    used[to] = depth+1
        que = nxt
        depth += 1
    for i in used:
        if i < 0:
            return 0
    return depth

ans = max(bfs(i) for i in range(n))
if ans == 0:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
inf=float("inf")
table=[[inf]*n for i in range(n)]
for i in range(n):
  s=input()
  for j in range(n):
    if s[j]=="1":
      table[i][j]=1
    
def warshall_floyd(d):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if d[i][k]!=inf and d[k][j]!=inf:
          d[i][j]=min(d[i][j],d[i][k]+d[k][j])
          if d[i][j]<float("inf") and d[i][j]%2!=(d[i][k]+d[k][j])%2:
            return False
  return d

d=warshall_floyd(table)

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

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

S = []



for i in range(N):

    s = input()
    S.append(s)


"""
lis = [float("inf")] * N
lis[0] = 0
q = deque([])

q.append(0)

#print (S,lis)

while len(q) > 0:

    now = q.pop()

    for i in range(N):

        #print (i,now)
        if S[now][i] == "1" and lis[i] > lis[now] + 1:
            lis[i] = lis[now] + 1
            q.append(i)

mind = 0
#print (lis)

for i in lis:
    if lis[mind] < lis[i]:
        mind = i

"""
ans = 0

for mind in range(N):


    lis = [float("inf")] * N
    lis[mind] = 0
    q = deque([])
    q.append(mind)

    #print (q,len(q),lis)

    while len(q) > 0:

        now = q.pop()
        #print (now)
    

        for i in range(N):

            if S[now][i] == "1" and lis[i] > lis[now] + 1:

                lis[i] = lis[now] + 1
                q.append(i)

    ans = max(ans,max(lis))


mind = 0
nlis = [None] * N
nlis[mind] = 0
q = deque([])
q.append(mind)
flag = True

while len(q) > 0:

    now = q.pop()  

    for i in range(N):

        if S[now][i] == "1" and nlis[i] == None:
   
            nlis[i] = nlis[now] ^ 1
            q.append(i)

        elif S[now][i] == "1" and nlis[now] == nlis[i]:
            flag = False
            break

    if not flag:
        break

if flag:
    print (ans + 1)

else:
    print (-1)

Submission status: Accepted

Solution code:
from collections import deque
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall


def bfs(links):
    color = [-1] * n
    last_v = None
    q = deque([(0, 0)])
    while q:
        v, c = q.popleft()
        if color[v] != -1:
            if color[v] != c:
                return -1
            continue
        else:
            color[v] = c
        last_v = v
        new_c = c ^ 1
        for u in links[v]:
            if color[u] != -1:
                if color[u] != new_c:
                    return -1
                continue
            q.append((u, new_c))
    return last_v


def bfs2(s, links):
    visited = set()
    q = deque([(s, 1)])
    last_d = -1
    while q:
        v, d = q.popleft()
        if v in visited:
            continue
        visited.add(v)
        last_d = d
        for u in links[v]:
            if u in visited:
                continue
            q.append((u, d + 1))
    return last_d


def solve(n, links, matrix):
    res = bfs(links)
    if res == -1:
        return -1
    # return bfs2(res, links)
    g = csgraph_from_dense(matrix)
    f = floyd_warshall(g)
    return int(f.max()) + 1


n = int(input())
links = [set() for _ in range(n)]
matrix = []
for i in range(n):
    s = input().strip()
    for j, c in enumerate(s):
        if c == '0':
            continue
        links[i].add(j)
    matrix.append(list(map(int, s)))

print(solve(n, links, matrix))

Submission status: Accepted

Solution code:
from collections import deque


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


graph = [[] for i in range(n)]
#二部グラフ判定
for i in range(n):
    for j in range(i+1, n):
        if s[i][j] == "1":
            graph[i].append(j)
            graph[j].append(i)

q = ([0])
visited = [-1]*n
visited[0] = 0
is_2graph = True
while q:
    pos = q.pop()
    for next_pos in graph[pos]:
        if visited[next_pos] == -1:
            visited[next_pos] = visited[pos] ^ 1
            q.append(next_pos)
        else:
            if visited[pos]^1 != visited[next_pos]:
                is_2graph = False
if not is_2graph:
    print(-1)
    exit()


INF = 10**9
dp = [[INF]*n for i in range(n)]
for i in range(n):
    dp[i][i] = 0

for i in range(n):
    for j in range(n):
        if s[i][j] == "1":
            dp[i][j] = 1
            dp[j][i] = 1

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

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

Submission status: Accepted

Solution code:
n = int(input())
raw = []
for i in range(n):
  tmp = input()
  now = []
  for j in range(n):
    if tmp[j] == '1':
      now.append(j)
  raw.append(now)
#print(raw)
ans = []
for st in range(n):
  gr = [-1 for _ in range(n)]
  gr[st] = 1
  time = 1
  now = {st}
  while now:
    time += 1
    last = now
    now = set()
    #print(last)
    for x in last:
      for y in raw[x]:
        if gr[y] == time-2:
          pass
        elif gr[y] == time:
          pass
        elif gr[y] == -1:
          gr[y] = time
          now.add(y)
        else:
          print(-1)
          #print(time,y,gr[y])
          break
      else:
        continue
      break
    else:
      continue
    break
  else:
    #print(time)
    ans.append(time-1)
    continue
  break
else:
  print(max(ans))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
G=[[] for i in range(n)]
for i in range(n):
    s=input().rstrip()
    for j in range(i,n):
        if s[j]=='1':
            G[i].append(j)
            G[j].append(i)
Ans=-1
for i in range(n):
    ans=1
    que=[i]
    cs=set(que)
    check=[False]*n
    check[i]=True
    nex=[]
    M=False
    while True:
        while len(que)>0:
            now=que.pop()
            for j in G[now]:
                if j in cs:
                    M=True
                elif check[j]:
                    pass
                else:
                    check[j]=True
                    nex.append(j)
        que=nex
        if que==[]:
            break
        cs=set(que)
        nex=[]
        ans+=1
    if M:
        ans=-1
    Ans=max(ans,Ans)
print(Ans)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
S = list(input() for i in range(N))
ans = -1
for i in range(N):
    queue = deque([i])
    V = [0]*N
    V[i] = 1
    while queue:
        q = queue.popleft()
        m = V[q]
        for i in range(N):
            if S[q][i] == "1":
                if V[i] == 0:
                    V[i] = m+1
                    queue.append(i)
                elif abs(V[i]-m) != 1:
                    print(-1)
                    exit()
    ans = max(max(V),ans)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque


def search(N, adj, start):
    dist = [-1] * N
    q = deque()
    q.append((start, 0, -1))
    while len(q):
        p, d, prev = q.popleft()
        if dist[p] != -1:
            if dist[p] != d:
                return None
            continue
        dist[p] = d
        for nxt in adj[p]:
            if nxt == prev:
                continue
            if dist[nxt] == -1:
                q.append((nxt, d+1, prev))
    return dist


def main():
    N = int(input())
    S = [input() for _ in range(N)]
    adj = [set() for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if S[i][j] == "1":
                adj[i].add(j)
    start = 0
    dist = search(N, adj, 0)
    if dist == None:
        print(-1)
        return
    ans = 0
    for i in range(N):
        tmp = max(search(N, adj, i)) + 1
        ans = max(ans, tmp)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

N=int(input())
S=[input().strip() for i in range(N)]

E=[[] for i in range(N)]

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

USE=[-1]*N

Q=deque()
Q.append(0)
USE[0]=0


while Q:
    x=Q.pop()

    for to in E[x]:
        if USE[x]==USE[to]:
            print(-1)
            sys.exit()
            
        elif USE[to]==-1:
            USE[to]=1-USE[x]
            Q.append(to)

for i in range(N):
    for j in range(N):
        if S[i][j]=="1" and USE[i]==USE[j]:
            print(-1)
            sys.exit()

ANS=0
for i in range(N):
    Q=deque()
    Q.append(i)
    USE=[0]*N
    USE[i]=1
    H=[0]*N

    while Q:
        NQ=deque()
        while Q:
            
            x=Q.pop()

            for to in E[x]:
                if USE[to]==0:
                    H[to]=H[x]+1
                    USE[to]=1
                    NQ.append(to)

        Q=NQ

    ANS=max(ANS,max(H)+1)

print(ANS)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, S):
    E = []
    G = defaultdict(list)
    for i, s in enumerate(S):
        for j, c in enumerate(s[:]):
            if i < j and c == '1':
                E.append((i, j))
                G[i].append(j)
                G[j].append(i)
    
    def f(s):
        e = set(E)
        vs = [set([s])]
        while e:
            vs1 = set()
            for i in vs[-1]:
                for j in G[i]:
                    vs1.add(j)
                    if i > j:
                        u, v = j, i
                    else:
                        u, v = i, j
                    if (u, v) in e:
                        e.remove((u, v))
            vs.append(vs1)
            for i in vs[-1]:
                for j in G[i]:
                    if j in vs[-1]:
                        return -1

        return len(vs)

    ans = -1
    for i in range(N):
        ans = max(ans, f(i))
    return ans


def main():
    N = read_int()
    S = [read_str() for _ in range(N)]
    print(slv(N, S))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
    def solve(i):
        C=[0]*n
        C[i]=1
        q=deque()
        q.append(i)
        while q:
            v=q.popleft()
            for to in Edges[v]:
                if C[to]==0:
                    q.append(to)
                    C[to]=C[v]+1
                else:
                    if C[to]!=C[v]+1 and C[to]!=C[v]-1:
                        return -1
        return max(C)
    n=int(input())
    S=[input().strip() for _ in range(n)]
    Edges=[[] for _ in range(n)]
    for i,s in enumerate(S):
        for j in range(n):
            if s[j]=='1':
                Edges[i].append(j)
    ans=-1
    for i in range(n):
        #print(solve(i))
        ans=max(ans,solve(i))
    return ans

if __name__=='__main__':
    print(main())

Submission status: Accepted

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

N = int(readline())
Edge = [[] for _ in range(N)]
for i in range(N):
    S = readline().strip()
    for j in range(N):
        if S[j] == '1':
            Edge[i].append(j)

def check(Edge):
    s = 0
    Q = deque([s])
    N = len(Edge)
    col = [None]*N
    col[s] = 0
    while Q:
        vn = Q.pop()
        for vf in Edge[vn]:
            if col[vn] == col[vf]:
                return False
            if col[vf] is None:
                col[vf] = 1 - col[vn]
                Q.appendleft(vf)
    
    return True

def bfs(s, Edge):
    N = len(Edge)
    Q = deque([s])
    inf = 10**9+7
    dist = [inf]*N
    dist[s] = 0
    used = set([s])
    while Q:
        vn = Q.pop()
        for vf in Edge[vn]:
            if vf in used:
                continue
            used.add(vf)
            dist[vf] = min(dist[vn]+1, dist[vf])
            Q.appendleft(vf)
    
    return dist

if not check(Edge):
    print(-1)
else:
    ans = 0
    for i in range(N):
        ans = max(ans, max(bfs(i, Edge)))
    print(ans+1)

Submission status: Accepted

Solution code:
import collections


class Graph:
    def __init__(self, n_nodes):
        self.n_nodes = n_nodes
        self.edges = [[] for _ in range(n_nodes)]

    def add_edge(self, s, t):
        self.edges[s].append(t)
        self.edges[t].append(s)


n = int(input())
graph = Graph(n)
for i in range(n):
    s = input().rstrip()
    for j in range(i + 1, n):
        if s[j] == '1':
            graph.add_edge(i, j)


def check(node):
    for new_node in graph.edges[node]:
        if orders[new_node] == -1:
            q.append(new_node)
            orders[new_node] = orders[node] + 1
        elif abs(orders[new_node] - orders[node]) != 1:
            return False
    return True


res = []
for i in range(n):
    orders = [-1] * n
    q = collections.deque()
    q.append(i)
    orders[i] = 1
    while q:
        node = q.popleft()
        ok = check(node)
        if not ok:
            break
    else:
        res.append(max(orders))
if len(res) == 0:
    print(-1)
else:
    print(max(res))

Submission status: Accepted

Solution code:
n = int(input())
s = []
for i in range(n):
    s.append(list(input()))
flag = True
num = [True] * n
num[0] = "e"
check_list = [1]
while check_list:
    check = check_list.pop(0)
    for i in range(n):
        if s[check - 1][i] == "1":
            if num[check - 1] == "e":
                if num[i] == "e":
                    flag = False
                    break
                elif num[i] == "o":
                    pass
                else:
                    num[i] = "o"
                    check_list.append(i + 1)
            else:
                if num[i] == "o":
                    flag = False
                    break
                elif num[i] == "e":
                    pass
                else:
                    num[i] = "e"
                    check_list.append(i + 1)
    if flag == False:
        break
if flag == False:
    print(-1)
else:
    step_list = []
    for i in range(n):
        num = [True] * n
        step = 0
        check_list = [[i + 1]]
        num[i] = False
        while check_list != [[]]:
            check_list2 = check_list.pop(0)
            new_check_list = []
            for j in check_list2:
                for k in range(n):
                    if s[j - 1][k] == "1":
                        if num[k] == True:
                            num[k] = False
                            new_check_list.append(k + 1)
            check_list.append(new_check_list)
            step += 1
        step_list.append(step)
    print(max(step_list))

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())

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

# print(S_array)
# s_deg_array = [0] * N

# for i in range(N):
#     for j in range(i + 1, N):
#         if S_array[i][j] == 1:
#             s_deg_array[i] += 1
#             s_deg_array[j] += 1

ans_max = 0

for fp in range(N):
    ans = 0
    d = deque()
    d.append(fp)
    used_array = [-1] * N
    value_array = [-1] * N
    used_array[fp] = 1
    value_array[fp] = 1
    while len(d):
        p = d.popleft()
        v = value_array[p]
        # print(p, v)
        for i, s in enumerate(S_array[p]):
            if s == 0:
                continue
            if used_array[i] == -1:
                used_array[i] = 1
                value_array[i] = v + 1
                ans = max(ans, v + 1)
                d.append(i)
            else:
                if value_array[i] != v - 1 and value_array[i] != v + 1:
                    print(-1)
                    exit()
    ans_max = max(ans, ans_max)

print(ans_max)