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: Time Limit Exceeded

Solution code:
#直径が答えになるわけではない

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

# for s in S:
#     print (s)

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

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

INF = 10 ** 9
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])
            
ans = 0
for i in range(N):
    for j in range(N):
        ans = max(S[i][j], ans)

print (ans + 1)

Submission status: Time Limit Exceeded

Solution code:
# 二部グラフかどうかの判定法
import sys
n=int(input())
s=[list(input()) for _ in range(n)]
g=[[] for _ in range(n+1)]
for i in range(n):
    for j in range(i+1,n):
        if s[i][j]=="1":
            g[i+1].append(j+1)
            g[j+1].append(i+1)
#二部グラフかどうかの判定
flag=[-1]*(n+1)
forest=[]
for i in range(1,n+1):
    U=[]
    if flag[i]==-1:
        que=[[i]]
        j=1
        flag[i]=1
        while que:
            h=que.pop()
            H=[]
            for u in h:
                flag[u]=j%2
                U.append(u)
                for v in g[u]:
                    if flag[v]==-1:
                        H.append(v)
                        flag[v]=(j+1)%2
                    elif flag[v]==j%2:
                        print(-1)
                        sys.exit()
            if H:
                que.append(H)
            j+=1
    if U:
        forest.append(U)
#iからjまでの距離を求めていく。
sum=0
for lst in forest:
    m=0
    for i in lst:
        for j in lst:
            if i>=j:
                continue
            que=[[i]]
            flag=[0]*(n+1)
            flag[i]=1
            k=0
            while que:
                k+=1
                h=que.pop()
                H=[]
                for u in h:
                    if u==j:
                        break
                    for v in g[u]:
                        if flag[v]==0:
                            H.append(v)
                            flag[v]=1
                else:
                    if H:
                        que.append(H)
                    continue
                break
            m=max(m,k)
    sum+=m            
print(sum)

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import *

sys.setrecursionlimit(10 ** 6)

def main():
    def judge(u=0,b=False):
        bt[u]=b
        res=False
        for ku in range(n):
            if not to[u][ku]:continue
            if bt[ku]==b:
                return True
            if bt[ku]==None:
                res|=judge(ku,not b)
        return res

    def bfs(u):
        hp=[]
        heappush(hp,(0,u))
        while hp:
            d,u=heappop(hp)
            if dis[u]!=-1:continue
            dis[u]=d
            for v in range(n):
                if not to[u][v]:continue
                if dis[v]!=-1:continue
                heappush(hp,(d+1,v))

    n = int(input())
    to = [[c == "1" for c in input()] for _ in range(n)]
    bt=[None]*n
    if judge():
        print(-1)
        exit()
    ans=0
    for u in range(n):
        dis=[-1]*n
        bfs(u)
        ans=max(ans,max(dis)+1)
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
def dfs(v, c):
    color[v] = c
    for i in range(n):
        if g[v][i] == 1:
            if color[i] == c:
                return False
            if color[i] == 0 and not dfs(i, -c):
                return False
    return True


n = int(input())
g = []
for i in range(n):
    s = list(map(int, list(input())))
    for j in range(n):
        if s[j] == 0:
            s[j] = 1000000
        if i == j:
            s[j] = 0
    g.append(s)

# 二部グラフ判定
color = [0] * n
nibu = True
for i in range(n):
    if color[i] == 0:
        if not dfs(i, 1):
            nibu = False

if nibu:
    for k in range(n):
        for i in range(n):
            for j in range(n):
                g[i][j] = min(g[i][j], g[i][k] + g[k][j])
    ans = 0
    for i in range(n):
        ans = max(ans, max(g[i]))
    print(ans + 1)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]
n = int(input())
s = [input() for _ in range(n)]
parity = [-1 for _ in range(n)]

def dfs(x):
	for i in range(n):
		if s[x][i] == "1":
			if parity[i] == parity[x]:
				print(-1)
				sys.exit()
			elif parity[i] == -1:
				parity[i] = parity[x]^1
				dfs(i)
	return

parity[0] = 0
dfs(0)

dist = [[10**30 if s[i][j] == "0" else 1 for j in range(n)] for i in range(n)]
for i in range(n):
	dist[i][i] = 0

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(*dist, sep="\n")
diam = 0
for i in range(n):
	for j in range(n):
		if dist[i][j] < 10**30:
			diam = max(diam, dist[i][j])

print(diam+1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

###################################
def arrmax(list):
    array = np.array(list)
#    print(np.argmax(array, axis=1)) ##座標
#    print(np.amax(array,axis=None)) ##値
    return np.amax(array,axis=None)
#################################
##ワーシャルフロイド法
#################################
def warshall_floyd(d,n):
    #d[i][j]: iからjへの最短距離
    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
##############################
##２部グラフか判別
##############################
def judge(n,v,c):
    def f(v, c):
        # 頂点vに隣接する頂点全てを塗るあるいは判定する
        color[v] = c
        for i in range(len(g[v])):
            if color[g[v][i]] == c:
                return False
            elif color[g[v][i]] == 0 and not f(g[v][i], -c):
                # (g[v][i]がまだ塗られていない　かつ　そこを-cで塗っても問題ない) ではないなら
                return False
        return True

    color = [0] * n  # color[i]:点iの色(1 or -1)。但し塗られていないときは0とする
    k = 1  # 判定　1ならYes -1ならNo
    for i in range(n):
        if color[i] == 0:
            if not f(i, c):
                k = -1

    if k == 1:
        return True
    else:
        return False

#######################################
N = int(input())
S = [[0 for j in range(N)] for i in range(N)]
d = [[float("inf") for i in range(N)] for i in range(N)]
g = [[] for i in range(N)] #g[i]:点iに隣接している点のリスト
for i in range(N):
    S[i] = str(input())
    for j in range(N):
        if S[i][j]=="1":
            d[i][j]=1
            d[j][i]=1
            g[i].append(j)
            g[j].append(i)


for i in range(N):
    d[i][i] = 0 #自身のところに行くコストは０

if judge(N,d,1):
    print(arrmax(warshall_floyd(d,N))+1) ##直径出力+1
else:
    print("-1")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
import itertools
import math
INF = 10**9
MOD = 10**9+7

class UnionFind:

    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.height = [0] * n
        self.size = [1] * n

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

    def getsize(self, x):
        return self.size[self.find(x)]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.height[x] < self.height[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = self.par[x]
            self.size[x] += self.size[y]
            if self.height[x] == self.height[x]:
                self.height[x] += 1

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

def isBipertite(es):
    n = len(es)
    uf = UnionFind(2 * n)
    for v, e in enumerate(es):
        for u in e:
            uf.unite(v, n+u)
            uf.unite(u, n+v)
    for v in range(n):
        if uf.same(v, n+v):
            return False
    return True

N = int(input())
es = [input() for i in range(N)]
for i in range(N):
    es[i] = [j for j in range(N) if es[i][j] == '1']
if isBipertite(es):
    d = [[INF] * N for i in range(N)]
    for i in range(N):
        d[i][i] = 0
    for v in range(N):
        for u in es[v]:
            d[v][u] = 1
    for w in range(N):
        for v in range(N):
            for u in range(N):
                d[v][u] = min(d[v][u], d[v][w]+d[w][u])
    print(max([max(d[v]) for v in range(N)])+1)
else:
    print(-1)

Submission status: Time Limit Exceeded

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

#二部グラフ判定
L = [0 for i in range(N)]
L[0] = 1
q = [0]
res = 0

while len(q) > 0:
    idx = q.pop(-1)
    c = L[idx]*(-1)
    for i in range(N):
        if S[idx][i] == "1":
            if L[i] == 0:
                L[i] = c
                q.append(i)
            elif L[i] == c*(-1):
                res = 1
                q.clear()
                break
            

if res == 1:
    print(-1)
else:
    # Warshall-Floyd法で直径を求める
    d = [[10**4 for j in range(N)] for i in range(N)]
    # initialize
    for i in range(N):
        for j in range(N):
            if S[i][j] == "1":
                d[i][j] = 1
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if i != j:
                    d[i][j] = min(d[i][j], d[i][k]+d[k][j])

                
    ans = 0
    for i in range(N):
        for j in range(N):
            if d[i][j] < 10**4:
                ans = max(ans, d[i][j])
                
    print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
X = [[] for _ in range(N)]
for i in range(N):
    s = input()
    for j in range(N):
        if s[j] == "1":
            X[i].append(j)

def bipartite(n, E):
    col = [-1] * n
    f = 0
    for i in range(n):
        if col[i] >= 0: continue
        que = deque([[i, 0]])
        while que:
            v, c = que.popleft()
            col[v] = c
            for ne in E[v]:
                if col[ne] == c:
                    f = 1
                    break
                if col[ne] < 0:
                    que.append([ne, 1-c])

            if f:
                break
        if f:
            break
    return 1-f

def BFS(n, E, i0=0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c in E[x]:
            if D[c] == -1:
                D[c] = D[x] + 1
                Q.append(c)
    return D

if bipartite(N, X):
    print(max([max(BFS(N, X, i)) for i in range(N)])+1)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
X = [[] for _ in range(N)]
for i in range(N):
    s = input()
    for j in range(N):
        if s[j] == "1":
            X[i].append(j)

def bipartite(n, E):
    col = [-1] * n
    que = deque([[0, 0]])
    f = 0
    while que:
        v, c = que.popleft()
        col[v] = c
        for ne in E[v]:
            if col[ne] == c:
                f = 1
                break
            if col[ne] < 0:
                que.append([ne, 1-c])

        if f:
            break
    return 1-f

def BFS(n, E, i0=0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c in E[x]:
            if D[c] == -1:
                D[c] = D[x] + 1
                Q.append(c)
    return D

if bipartite(N, X):
    print(max([max(BFS(N, X, i)) for i in range(N)])+1)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = []
for i in range(N):
  Ss = input()
  S.append(Ss)
E = [set() for i in range(N)]
D = [[100000]*N for i in range(N)]
for i in range(N):
  D[i][i] = 0
  for j in range(i+1, N):
    if S[i][j] == "1":
      #print(i, j)
      E[i].add(j)
      E[j].add(i)
      D[i][j] = 1
      D[j][i] = 1
ok = True
V = [-1]*N
c = 0
V[0] = 0
q = [0]
while q:
  c = q.pop()
  ns = E[c]
  for n in ns:
    if V[n] == V[c]:
      ok = False
    if not V[n] < 0:
      continue
    V[n] = 1 if V[c] == 0 else 0
    q.append(n)
if not ok:
  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])
#print(D)
r = max([max(Ds) for Ds in D])+1
print(r)

Submission status: Time Limit Exceeded

Solution code:
import sys, collections

def dfs(i, c, col, edge):
    col[i] = c
    for next_node in edge[i]:
        if col[next_node] == c: return False
        if col[next_node] == 0 and dfs(next_node, -c, col, edge) == False: return False

    return True

def solve():
    N = int(input())
    edge = dict()
    col = dict()
    for i in range(N): 
        edge[i] = set()
        col[i] = 0
        s = input()
        for j in range(N):
            if s[j] == "1": edge[i] |= {j}

    is_bipartite = dfs(0, 1, col, edge)
    if not is_bipartite: print(-1)
    else:
        INF = 10 ** 15
        dist = [[INF for j in range(N)] for i in range(N)]
        for i in range(N):
            for j in range(N):
                if i == j: dist[i][j] = 0
                elif j in edge[i]: dist[i][j] = 1

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

        ans = -1
        for i in range(N):
            for j in range(N):
                if dist[i][j] < INF: ans = max(ans, dist[i][j])
        print(ans + 1)

    

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/agc039/submissions/7877660
from collections import deque

INF = float('inf')


def bfs(n, es):
    parity = [-1] * n
    parity[0] = 0

    dq = deque()
    dq.append(0)
    while dq:
        v = dq.popleft()
        nxt_par = parity[v] ^ 1
        for u in es[v]:
            if parity[u] == -1:
                parity[u] = nxt_par
                dq.append(u)
            else:
                if parity[u] != nxt_par:
                    return False
                    # bipartite = False
    return True
    # bipartite = True


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


def solve():
    n = int(input())
    es = tuple(set() for _ in range(n))
    g = []
    for v in range(n):
        s = input()
        for u, is_adj in enumerate(map(int, s)):
            if is_adj:
                es[v].add(u)
                es[u].add(v)
        g.append(list(map(int, s)))
    for r, row in enumerate(g):
        for c, cell in enumerate(row):
            if cell == 0 and r != c:
                g[r][c] = INF
        # 隣接頂点間: 1
        # 同一頂点間: 0
        # その他: INF
    # print(es)
    # print(g)

    # 二部グラフ判定
    bipartite = bfs(n, es)
    if not bipartite:
        return -1

    # 最遠点対間距離を求める
    g = warshall_floyd(n, g)
    d = max(max(row) for row in g)
    return d + 1


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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

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

def main():
    input = sys.stdin.readline
    N = int(input())
    G = []
    for _ in range(N):
        S = [int(c) for c in str(input().strip())]
        T = []
        for i, e in enumerate(S):
            if e == 1:
                T.append(i)
        G.append(T)
    
    def is_binarygraph(v, color):
        colors = [-1] * N
        colors[v] = color
        for n in G[v]:
            if colors[n] == color:
                return False
            colors[n] = (color + 1) % 2
            if not is_binarygraph(n, (color+1)%2):
                return False
        return True
    
    if not is_binarygraph(0, 0):
        return -1

    inf = 10**3
    d = [[inf]*N for _ in range(N)]
    for i in range(N):
        for j in range(G[i]):
            d[i][j] = 1
    
    fw = warshall_floyd(d)
    return max(fw)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
sys.setrecursionlimit(10**7)


def main():
    input = sys.stdin.readline
    N = int(input())
    G = []
    for _ in range(N):
        S = [int(c) for c in str(input().strip())]
        T = []
        for i, e in enumerate(S):
            if e == 1:
                T.append(i)
        G.append(T)
    
    def is_binarygraph(v, color):
        colors = [-1] * N
        colors[v] = color
        for n in G[v]:
            if colors[n] == color:
                return False
            colors[n] = (color + 1) % 2
            if not is_binarygraph(n, (color+1)%2):
                return False
        return True
    
    if not is_binarygraph(0, 0):
        return -1

    fw = floyd_warshall(G)
    return max(fw)

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

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys
sys.setrecursionlimit(10**8)

n=int(input())
arr=[input() for _ in range(n)]
g=[[] for _ in range(n)]
for i in range(n):
  for j in range(n):
    if i==j:
      continue
    if arr[i][j]=='1':
      g[i].append(j)

colors=[0]*n

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

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

if is_bipartite()==False:
  print(-1)
  exit()

ans=0
for v in range(n):
  q=collections.deque()
  q.append((v,1))
  checked=[0]*n
  anss=[]
  while len(q)!=0:
    tmp,depth=q.popleft()
    anss.append(depth)
    checked[tmp]=1
    for v in g[tmp]:
      if checked[v]==0:
        q.append((v,depth+1))
  ans=max(ans,max(anss))
print(ans)

Submission status: Time Limit Exceeded

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


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)

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys
sys.setrecursionlimit(10**8)

n=int(input())
arr=[input() for _ in range(n)]
g=[[] for _ in range(n)]
for i in range(n):
  for j in range(n):
    if i==j:
      continue
    if arr[i][j]=='1':
      g[i].append(j)

colors=[0]*n

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

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

if is_bipartite()==False:
  print(-1)
  exit()

ans=0
for v in range(n):
  q=collections.deque()
  q.append((v,1))
  checked=[0]*n
  while len(q)!=0:
    tmp,depth=q.popleft()
    ans=max(ans,depth)
    checked[tmp]=1
    for v in g[tmp]:
      if checked[v]==0:
        q.append((v,depth+1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
edge = [[] for _ in range(n)]
mat = [[1000] * n for _ in range(n)]
for i in range(n):
    s = input().rstrip()
    for j, ch in enumerate(s):
        if ch == "1":
            mat[i][j] = 1
            if j > i:
                edge[i].append(j)
                edge[j].append(i)
for i in range(n):
    mat[i][i] = 0
for k in range(n):
    for i in range(n):
        for j in range(n):
            mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j])

ans = 0
dq = deque()
dist = [-1] * n
dq.append((i, 0))
ok = True
while dq:
    v, d = dq.popleft()
    if dist[v] == -1:
        dist[v] = d
    elif dist[v] != d:
        ok = False
        break
    for item in edge[v]:
        if dist[item] == -1:
            dq.append((item, d+1))

if ok:
    ans = 0
    for line in mat:
        ans = max(ans, max(line))
    print(ans + 1)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy


def check_not_circle(vs, a):
    l = []
    for v in vs:
        for i, c in enumerate(a[v]):
            # print(a[v], v)
            if c == 1:
                l.append(i)
    # print(list(set(l)))
    # input()
    for v in vs:
        if v in l:
            return True

    return False


def get_adjacent(vs, a):
    ret = []
    for v in vs:
        for i, c in enumerate(a[v]):
            if c == 1:
                ret.append(i)
    # print(ret)
    if check_not_circle(ret, a):
        return -1

    ret = list(set(ret))

    return ret


n = int(input())
a = []
for i in range(n):
    m = input()
    l = []
    for c in m:
        l.append(int(c))
    a.append(l)

max = 1


for i in range(n):
    a_copied = deepcopy(a)
    # print(a_copied)
    # input()
    score = 1
    vs = [i]
    rets = [[i]]
    while (1):
        for c in vs:
            for i2 in range(n):
                a_copied[i2][c] = 0
        vs_next = get_adjacent(vs, a_copied)
        # print(vs_next)
        if vs_next == -1:
            max = -1
            # print(max)
            break
        if vs_next == []:
            break
        score += 1
        vs = vs_next
        rets.append(vs)
    # print(score)
    # print(rets)
    # input()
    if max == -1:
        break
    if max < score:
        max = score

print(max)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
ab = []
edge = [[] for _ in range(n)]
for i in range(n):
    s = input().rstrip()
    for j, ch in enumerate(s):
        if ch == "1":
            if j > i:
                edge[i].append(j)
                edge[j].append(i)
                ab.append((i, j))

ans = 0
for i in range(n):
    dq = deque()
    dist = [-1] * n
    dq.append((i, 0))
    ok = True
    while dq:
        v, d = dq.popleft()
        if dist[v] == -1:
            dist[v] = d
        elif dist[v] != d:
            ok = False
            break
        for item in edge[v]:
            if dist[item] == -1:
                dq.append((item, d+1))
    if ok:
        ans = max(ans, max(dist))

if ans > 0:
    print(ans + 1)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

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

es = [[] for i in range(N)]
for i,row in enumerate(S):
    for j,c in enumerate(row):
        if c=='1':
            es[i].append(j)
            es[j].append(i)

#n個の頂点の色を初期化。0:未着色、1:黒、-1:白
colors = [0 for i in range(N)]

#頂点vをcolor(1 or -1)で塗り、再帰的に矛盾がないか調べる。矛盾があればFalse
def dfs(v,color):
    #今いる点を着色
    colors[v] = color
    #今の頂点から行けるところをチェック
    for to in es[v]:
        #同じ色が隣接してしまったらFalse
        if colors[to] == color:
            return False
        #未着色の頂点があったら反転した色を指定し、再帰的に調べる
        if colors[to] == 0 and not dfs(to, -color):
            return False
    #調べ終わったら矛盾がないのでTrue
    return True

#2部グラフならTrue, そうでなければFalse
def is_bipartite():
    return dfs(0,1) # 頂点0を黒(1)で塗ってDFS開始

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

INF = float('inf')
dists = [[1 if c=='1' else INF for c in row] for row in S]
for i in range(N):
    dists[i][i] = 0

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

print(max(max(row) for row in dists) + 1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

E = []
es = [[] for _ in range(N)]
for j in range(N):
    s = input()
    e = []
    for i, c in enumerate(s):
        e.append(1 if c=="1" else float("inf"))
        if c=="1":
            es[i].append(j)
    E.append(e)

# http://prd-xxx.hateblo.jp/entry/2017/10/13/004256

#n個の頂点の色を初期化。0:未着色、1:黒、-1:白
colors = [0 for i in range(N)]

#頂点vをcolor(1 or -1)で塗り、再帰的に矛盾がないか調べる。矛盾があればFalse
def dfs(v,color):
    #今いる点を着色
    colors[v] = color
    #今の頂点から行けるところをチェック
    for to in es[v]:
        #同じ色が隣接してしまったらFalse
        if colors[to] == color:
            return False
        #未着色の頂点があったら反転した色を指定し、再帰的に調べる
        if colors[to] == 0 and not dfs(to, -color):
            return False
    #調べ終わったら矛盾がないのでTrue
    return True

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

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

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

ans = 0
for e in E:
    ans = max(ans, max(e))
print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
import queue
n = int(input())
class Node:
    def __init__(self):
        self.nextNode = []
        self.checkNgo = -1
        self.group = -1
        
Nodes = [Node() for i in range(n)]
for i in range(n):
    s = input()
    for j in range(len(s)):
        if s[j] == '1':
            Nodes[i].nextNode.append(j)
            
def check(node,ngo):
    if node.checkNgo == -1:
        node.checkNgo = ngo
    elif node.checkNgo != ngo:
        return False
    elif node.checkNgo == ngo:
        return True
    for i in node.nextNode:
        if not check(Nodes[i],(ngo+1)%2):
            return False
    return True
    
if not check(Nodes[0],0):
    print(-1)
    exit(0)
    
def solv(nn):
    q = queue.Queue()
    q.put(Nodes[nn])
    Nodes[nn].group = 0
    while not q.empty():
        node = q.get()
        for i in node.nextNode:
            if Nodes[i].group != -1:
                Nodes[i].group = node.group+1
                q.put(Nodes[i])
    
def saidai():
    maxi = 0
    for i in range(n):
        maxi = max(Nodes[i].group,maxi)
    return maxi
    
kai = 0
for i in range(n):
    for j in range(n):
        Nodes[i].group = -1
    solv(i)
    kai = max(kai,saidai())
print(kai)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
ab = []
edge = [[] for _ in range(n)]
mat = [[1000] * n for _ in range(n)]
for i in range(n):
    s = input().rstrip()
    for j, ch in enumerate(s):
        if ch == "1":
            mat[i][j] = 1
            if j > i:
                edge[i].append(j)
                edge[j].append(i)
                ab.append((i, j))
for i in range(n):
    mat[i][i] = 0
for k in range(n):
    for i in range(n):
        for j in range(n):
            mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j])

ans = 0
dq = deque()
dist = [-1] * n
dq.append((i, 0))
ok = True
while dq:
    v, d = dq.popleft()
    if dist[v] == -1:
        dist[v] = d
    elif dist[v] != d:
        ok = False
        break
    for item in edge[v]:
        if dist[item] == -1:
            dq.append((item, d+1))
if ok:
    ans = 0
    for line in mat:
        ans = max(ans, max(line))
    print(ans + 1)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
def f1(l1):
    ret = []
    for i in l1:
      for n,j in enumerate(li[i]):
        if j:
            if n in used or n in l1:
                return False
            elif n not in tree[nest-1] and n not in ret:
                ret.append(n)
    return ret


N = int(input())
li = []
for _ in range(N):
    li.append(list(map(int,list(input()))))
    
max_nest = 0
for i in range(N):
    tree = [[]]
    used = []
    tree.append([i])
    nest = 1
    while True:
        ret = f1(tree[nest])
        nest += 1
        if ret == False:
            break
        elif ret != []:
            tree.append(ret)
            used.extend(tree[nest-2])
        else:
            if max_nest < nest:
                max_nest = nest
            break
        
print(max_nest-1)

Submission status: Time Limit Exceeded

Solution code:
def f1(l1):
    ret = []
    for i in l1:
      for n,j in enumerate(li[i]):
        if j == 1:
            if n in used or n in l1:
                return False
            elif n not in tree[nest-1]:
                ret.append(n)
    return list(set(ret))


N = int(input())
li = []
for _ in range(N):
    li.append(list(map(int,list(input()))))
    
max_nest = 0
for i in range(N):
    tree = [[]]
    used = []
    tree.append([i])
    nest = 1
    while True:
        ret = f1(tree[nest])
        nest += 1
        if ret == False:
            break
        elif ret != []:
            tree.append(ret)
            used.extend(tree[nest-2])
        else:
            if max_nest < nest:
                max_nest = nest
            break
        
print(max_nest-1)