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:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)

def main():
    N = int(input())
    G = [[] for _ in range(N)]
    dist = []
    for i in range(N):
        route = [int(i) for i in input()]
        for j in range(N):
            if route[j]:
                G[i].append(j)
            elif i != j:
                route[j] = INF
        dist.append(route)
    
    color = [-1]*N
    color[0] = 0
    stack = [0]
    possible = True
    while stack:
        p = stack.pop()
        for e in G[p]:
            if color[e] >= 0:
                if color[e] == color[p]:
                    possible = False
            else:
                color[e] = color[p]^1
                stack.append(e)
        if not possible:
            break
    
    if possible:
        ans = 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])
        for i in range(N):
            for j in range(N):
                ans = max(ans,dist[i][j])
        print(ans + 1)
    else:
        print(-1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
N = int(input())
E = [[] for _ in range(N)]
for j in range(N):
	t = input()
	for i in range(N):
		if t[i] == '1':
			E[j].append(i)

ANS = -1
for start in range(N):		
	cnt = np.zeros(N, dtype = np.int64)
	cnt[start] = 1
	q = [start]
	cond = 0
	while q:
		cp = q.pop(0)
		if cp < 0:
			continue
		cnt[cp] *= -1

		for nep in E[cp]:
			if cnt[nep] < 0:
				continue
			elif cnt[nep] > 0:
				if cnt[nep] == cnt[cp] * (-1) + 1:
					continue
				else:
					cond = 1
					break
			else:
				cnt[nep] = cnt[cp] * (-1) + 1
				q.append(nep)
	
	if cond:
		continue

	ans = min(cnt) * (-1)
	ANS = max(ANS, ans)

print(ANS)

Submission status: Time Limit Exceeded

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

from collections import defaultdict
from queue import deque

def main():
  n = int(input())
  graph = defaultdict(list)
  
  def is_bt():
    def bfs():
      colors = [-1] * len(graph)
      dq = deque()
      dq.append(0)
      colors[0] = 0
      while dq:
        inode = dq.popleft()
        for ichild in graph[inode]:
          if colors[ichild] == -1:
            colors[ichild] = abs(colors[inode]-1)
            dq.append(ichild)
          else:
            if colors[ichild] == colors[inode]:
              return False
      return True
    return bfs()
  
  def wf(edges):
    dp = edges
    for k in range(len(graph)):
      for i in range(len(graph)):
        for j in range(len(graph)):
          dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    return dp
  
  edges = [[n+1] * n for _ in range(n)]  
  for i in range(n):
    for j, c in enumerate(input().strip()):
      if c == '1':
        graph[i].append(j)
        edges[i][j] = 1
    edges[i][i] = 0
  graph = dict(graph)
    
  if not is_bt():
    print(-1)
    return
  print(max([max(x) for x in wf(edges)]) + 1)
  
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

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

from collections import defaultdict
from queue import deque

def main():
  n = int(input())
  graph = defaultdict(list)
  
  def is_bt():
    def bfs():
      colors = [-1] * len(graph)
      visited = [False] * len(graph)
      dq = deque()
      dq.append((0, 0))
      while dq:
        inode, color = dq.popleft()
        for ichild in graph[inode]:
          if colors[ichild] == -1:
            colors[ichild] = abs(color-1)
            dq.append((ichild, abs(color-1)))
          else:
            if colors[ichild] != abs(color-1):
              return False
      return True
    return bfs()
  
  def wf(edges):
    dp = edges
    for k in range(len(graph)):
      for i in range(len(graph)):
        for j in range(len(graph)):
          dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    return dp
  
  edges = [[n+1] * n for _ in range(n)]  
  for i in range(n):
    for j, c in enumerate(input().strip()):
      if c == '1':
        graph[i].append(j)
        edges[i][j] = 1
    edges[i][i] = 0
  graph = dict(graph)
    
  if not is_bt():
    print(-1)
    return
  print(max([max(x) for x in wf(edges)]) + 1)
  
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

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

from collections import defaultdict
from queue import deque

def main():
  n = int(input())
  graph = defaultdict(list)
  
  def is_bt():
    colors = [-1] * len(graph)
    visited = [False] * len(graph)
    def dfs(inode, color):
      visited[inode] = True
      colors[inode] = color
      for ichild in graph[inode]:
        if not visited[ichild]:
          if not dfs(ichild, abs(color - 1)):
            return False
        else:
          if colors[ichild] == color:
            return False
      return True
    return dfs(0, 0)
        
  def wf(edges):
    dp = edges
    for k in range(len(graph)):
      for i in range(len(graph)):
        for j in range(len(graph)):
          dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    return dp
  
  edges = [[n+1] * n for _ in range(n)]  
  for i in range(n):
    for j, c in enumerate(input().strip()):
      if c == '1':
        graph[i].append(j)
        edges[i][j] = 1
    edges[i][i] = 0
  graph = dict(graph)
    
  if not is_bt():
    print(-1)
    return
  print(max([max(x) for x in wf(edges)]) + 1)
  
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

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

from collections import defaultdict
from queue import deque

def main():
  n = int(input())
  graph = defaultdict(list)
  
  def is_bt():
    colors = [-1] * len(graph)
    visited = [False] * len(graph)
    def dfs(inode, color):
      visited[inode] = True
      colors[inode] = color
      for ichild in graph[inode]:
        if not visited[ichild]:
          if not dfs(ichild, abs(color - 1)):
            return False
        else:
          if colors[ichild] == color:
            return False
      return True
    return dfs(0, 0)
        
  def wf(edges):
    dp = edges
    for k in range(len(graph)):
      for i in range(len(graph)):
        for j in range(len(graph)):
          dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    return dp
  
  edges = [[n+1] * n for _ in range(n)]  
  for i in range(n):
    for j, c in enumerate(input().strip()):
      if c == '1':
        graph[i].append(j)
        edges[i][j] = 1
    edges[i][i] = 0
    
  if not is_bt():
    print(-1)
    return
  print(max([max(x) for x in wf(edges)]) + 1)
  
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

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

from collections import defaultdict
from queue import deque

def main():
  n = int(input())
  graph = defaultdict(list)
  
  def is_bt():
    def bfs():
      colors = [-1] * len(graph)
      visited = [False] * len(graph)
      dq = deque()
      dq.append((0, 0))
      while dq:
        inode, color = dq.popleft()
        if visited[inode]:
          continue
        visited[inode] = True
        for ichild in graph[inode]:
          if colors[ichild] == -1:
            colors[ichild] = abs(color-1)
          else:
            if colors[ichild] != abs(color-1):
              return False
          if not visited[ichild]:
            dq.append((ichild, abs(color-1)))
      return True
    return bfs()
  
  def wf(edges):
    dp = edges
    for k in range(len(graph)):
      for i in range(len(graph)):
        for j in range(len(graph)):
          dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    return dp
  
  edges = [[n+1] * n for _ in range(n)]  
  for i in range(n):
    for j, c in enumerate(input().strip()):
      if c == '1':
        graph[i].append(j)
        edges[i][j] = 1
    edges[i][i] = 0
    
  if not is_bt():
    print(-1)
    return
  print(max([max(x) for x in wf(edges)]) + 1)
  
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

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

from collections import defaultdict
from queue import deque

def main():
  n = int(input())
  graph = defaultdict(list)
  
  def is_bt():
    def bfs():
      colors = [-1] * len(graph)
      visited = [False] * len(graph)
      dq = deque()
      dq.append((0, 0))
      while dq:
        inode, color = dq.popleft()
        visited[inode] = True
        for ichild in graph[inode]:
          if colors[ichild] == -1:
            colors[ichild] = abs(color-1)
          else:
            if colors[ichild] != abs(color-1):
              return False
          if not visited[ichild]:
            dq.append((ichild, abs(color-1)))
      return True
    return bfs()
  
  def wf(edges):
    dp = edges
    for k in range(len(graph)):
      for i in range(len(graph)):
        for j in range(len(graph)):
          dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    return dp
  
  edges = [[n+1] * n for _ in range(n)]  
  for i in range(n):
    for j, c in enumerate(input().strip()):
      if c == '1':
        graph[i].append(j)
        edges[i][j] = 1
    edges[i][i] = 0
    
  if not is_bt():
    print(-1)
    return
  print(max([max(x) for x in wf(edges)]) + 1)
  
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

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

from collections import defaultdict
from queue import deque

def main():
  n = int(input())
  graph = defaultdict(list)
  
  def is_bt():
    def bfs():
      colors = [-1] * len(graph)
      visited = [False] * len(graph)
      dq = deque()
      dq.append((0, 0))
      while dq:
        inode, color = dq.popleft()
        visited[inode] = True
        for ichild in graph[inode]:
          if colors[ichild] == -1:
            colors[ichild] = abs(color-1)
          else:
            if colors[ichild] != abs(color-1):
              return False
        if not visited[ichild]:
          dq.append((ichild, abs(color-1)))
      return True
    return bfs()
  
  def wf(edges):
    dp = edges
    for k in range(len(graph)):
      for i in range(len(graph)):
        for j in range(len(graph)):
          dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    return dp
  
  edges = [[n+1] * n for _ in range(n)]  
  for i in range(n):
    for j, c in enumerate(input().strip()):
      if c == '1':
        graph[i].append(j)
        edges[i][j] = 1
    edges[i][i] = 0
    
  if not is_bt():
    print(-1)
    return
  print(max([max(x) for x in wf(edges)]) + 1)
  
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
S = []
for i in range(n):
    S.append(input())
color = [-1]*n #0:黒, 1:白
color[0] = 0
stack = [0]
colored = [0]*n
colored[0] = 1
while len(stack) != 0:
    temp = stack.pop()
    col = color[temp]
    cur = S[temp]
    for j in range(n):
        if cur[j] == '1':
            if colored[j] != 0:
                if color[j] == col:
                    print(-1)
                    exit()
            else:
                if col == 1:
                    color[j] = 0
                else:
                    color[j] = 1
                colored[j] = 1
                stack.append(j)
maxdist = 0
dist = []
for i in range(n):
    d = [float('inf')]*n
    d[i] = 0
    dist.append(d)
for i in range(n):
    for j in range(n):
        if S[i][j] == '1':
            dist[i][j] = 1
for i in range(n):
    for k in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
for i in range(n):
    for j in range(n):
        if dist[i][j] != float('inf'):
            maxdist = max(maxdist, dist[i][j])
print(maxdist+1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque

def solve(N: int, S: "List[str]"):
    matrix = [[] for _ in range(N)]
    d = [[10**9]*N for _ in range(N)]

    for i in range(N):
        d[i][i] = 0
        for j in range(N):
            if S[i][j] == "1":
                matrix[i].append(j)
                d[i][j] = 1
                d[j][i] = 1
    
    # ２部グラフ 判定
    stack = [(0,1)]
    color = [-1]*N

    while stack:
        node,c = stack.pop()
        color[node] = c

        for next in matrix[node]:
            if color[next] == -1:
                stack.append((next,~c))
            else:
                if c^color[next] == 0:
                    print(-1)
                    return


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

    answer = 0
    for i in range(N):
        answer = max(answer,max(d[i]))
    print(answer+1)
    return

def main():
    N = int(input())
    S = [input() for _ in range(N)]
    solve(N, S)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
def solve(N: int, S: "List[str]"):
    matrix = [[] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if S[i][j] == "1":
                matrix[i].append(j)

    answer = -1
    for start_node in range(N):
        group = [0]*N
        queue = deque([(start_node,1)])

        while queue:
            node,count = queue.popleft()

            if not group[node]:
                group[node] = count
    
            for next_node in matrix[node]:
                if not group[next_node]:
                    queue.append((next_node,count+1))
                else:
                    if abs(group[next_node]-group[node]) == 1:
                        continue
                    else:
                        break
            else:
                continue
            break
        else:
            answer = max(answer,max(group))

    print(answer)
    return

def main():
    N = int(input())
    S = [input() for _ in range(N)]
    solve(N, S)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
def solve(N: int, S: "List[str]"):
    matrix = [[] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if S[i][j] == "1":
                matrix[i].append(j)

    answer = -1
    for start_node in range(N):
        group = [0]*N
        queue = deque([(start_node,1)])

        while queue:
            node,count = queue.popleft()

            if not group[node]:
                group[node] = count
    
            for next_node in matrix[node]:
                if not group[next_node]:
                    queue.append((next_node,count+1))
                else:
                    if abs(group[next_node]-group[node]) == 1:
                        continue
                    else:
                        break
            else:
                continue
            break
        else:
            answer = max(answer,max(group))

    print(answer)
    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)] 
    solve(N, S)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
def solve(N: int, S: "List[str]"):
    matrix = [[] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if S[i][j] == "1":
                matrix[i].append(j)

    answer = -1
    for start_node in range(N):
        group = [0]*N
        queue = deque([(start_node,1)])

        while queue:
            node,count = queue.popleft()
            if not group[node]:
                group[node] = count
    

            for next_node in matrix[node]:
                if not group[next_node]:
                    queue.append((next_node,count+1))
                else:
                    if abs(group[next_node]-group[node]) == 1:
                        continue
                    else:
                        break
            else:
                continue
            break
        else:
            answer = max(answer,max(group))

    print(answer)

    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[int]"
    solve(N, S)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
def solve(N: int, S: "List[str]"):
    matrix = [[] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if S[i][j] == "1":
                matrix[i].append(j)

    answer = -1
    for start_node in range(N):
        group = [0]*N
        queue = deque([(start_node,1)])

        while queue:
            node,count = queue.popleft()
            if not group[node]:
                group[node] = count

            for next_node in matrix[node]:
                if not group[next_node]:
                    queue.append((next_node,count+1))
            # print(group)

        # 条件を満たしているか判定
        # print(answer)
        for i in range(N): 
            for j in matrix[i]:
                if abs(group[i]-group[j]) == 1:
                    continue
                else:
                    break
            else:
                continue
            break
        else:
            answer = max(answer,max(group))
    print(answer)

    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[int]"
    solve(N, S)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
def solve(N: int, S: "List[str]"):
    matrix = [[] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if S[i][j] == "1":
                matrix[i].append(j)

    answer = -1
    for start_node in range(N):
        group = [0]*N
        queue = deque([(start_node,1)])

        while queue:
            node,count = queue.popleft()
            if not group[node]:
                group[node] = count

            for next_node in matrix[node]:
                if not group[next_node]:
                    queue.append((next_node,count+1))
            # print(group)

        # 条件を満たしているか判定
        # print(answer)
        for i in range(N):
            for j in range(N):
                if S[i][j] == "1":
                    if abs(group[i]-group[j]) == 1:
                        continue
                    else:
                        break
            else:
                continue
            break
        else:
            answer = max(answer,max(group))
    print(answer)

    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[int]"
    solve(N, S)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

from collections import deque

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

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

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
# input = sys.stdin.buffer.readline
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

INF = 1001001001
from scipy.sparse.csgraph import floyd_warshall
from collections import deque

N = int(input())
S = [input() for _ in range(N)]
G = [[INF]*N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j:
            G[i][j] = 0
        elif S[i][j] == '1':
            G[i][j] = 1
# print(G)

dist = floyd_warshall(G)
# print(dist)

k_1 = 0
for i in range(N):
    for j in range(N):
        if int(dist[i][j]) > k_1:
            k_1 = int(dist[i][j])
            max_i = i
            max_j = j
k = k_1 + 1

dist = [-1] * N
dist[max_i] = 1
q = deque()
q.append([max_i, 1])

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

print(k)

Submission status: Time Limit Exceeded

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

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    S = [list(input().rstrip()) for _ in range(N)]

    color = [-1] * N
    color[0] = 0
    stack = [0]
    while stack:
        v = stack.pop()
        for to in range(N):
            if S[v][to] == '0': continue
            if color[to] >= 0:
                if color[to] == color[v]:
                    print(-1)
                    exit()
                continue
            stack.append(to)
            color[to] = color[v]^1

    D = [[10**9] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if i == j: D[i][j] = 0
            elif S[i][j] == '1': D[i][j] = 1
    for k in range(N):
        for i in range(N):
            for j in range(N):
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])
    print(max(max(d) for d in D) + 1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    S = [list(input().rstrip()) for _ in range(N)]

    uf = UnionFindTree(N*2)
    for i in range(N):
        for j in range(i+1,N):
            if S[i][j] == '1':
                uf.union(i, j+N)
                uf.union(i+N, j)
    
    for i in range(N):
        if uf.same(i, i+N):
            print(-1)
            exit()

    D = [[10**9] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if i == j: D[i][j] = 0
            elif S[i][j] == '1': D[i][j] = 1

    for k in range(N):
        for i in range(N):
            for j in range(N):
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])
    d_max = max(max(s) for s in D)
    print(d_max+1)

class UnionFindTree:
    def __init__(self, n):
        self.parent = [-1] * n

    def find(self, x):
        p = self.parent
        while p[x] >= 0: x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x, y):
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x

    def same(self, x, y): return self.find(x) == self.find(y)
    def size(self, x): return -self.parent[self.find(x)]

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

from collections import deque


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

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


    """
    あるノードを始点として、幅優先的に色塗りをしていく。
    これを、全ノードを始点にして試す
    """
    ans = -1
    for i in range(N):
        color = [0] * N
        
        q = deque()
        q.append((i, 1))
        tmp = 1
        flag = True
        while q and flag:
            node, c = q.popleft()
            color[node] = c
            
            for nxt in es[node]:
                if color[nxt] != 0:
                    if abs(color[node] - color[nxt]) != 1:
                        flag = False
                        break
                else:
                    q.append((nxt, c+1))
                    tmp = max(c+1, tmp)


        if flag:
            ans = max(ans, tmp)

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

from collections import deque

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

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


"""
あるノードを始点として、幅優先的に色塗りをしていく。
これを、全ノードを始点にして試す
"""
ans = -1
for i in range(N):
    color = [0] * N
    
    q = deque()
    q.append((i, 1))
    flag = True
    while q and flag:
        node, c = q.popleft()
        color[node] = c
        for nxt in es[node]:
            if color[nxt] != 0:
                if abs(color[node] - color[nxt]) != 1:
                    flag = False
                    break
            else:
                q.append((nxt, c+1))


    if flag:
        ans = max(ans, max(color))

print(ans)

Submission status: Time Limit Exceeded

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

Solution code:
N=int(input())
S=[input() for i in range(N)]
G=[[] for i in range(N)]
for i in range(N):
    for j in range(N):
        if S[i][j]=="1":
            G[i].append(j)
q=[0]
dist=[-1 for i in range(N)]
dist[0]=0
while(q):
    r=q.pop()
    for p in G[r]:
        if dist[p]==-1:
            dist[p]=1-dist[r]
            q.append(p)
for i in range(N):
    for j in G[i]:
        if dist[i]==dist[j]:
            print(-1)
            exit()
#possible
#print(G)
d=[[10**9 for i in range(N)] for i in range(N)]
for i in range(N):
    for j in G[i]:
        d[i][j]=1
    d[i][i]=0

for k in range(N):
    for i in range(N):
        for j in range(N):
            if d[i][j]>d[i][k]+d[k][j]:
                d[i][j]=d[i][k]+d[k][j]
ans=2
for i in range(N):
    for j in range(N):
        ans=max(ans,d[i][j]+1)
print(ans)

Submission status: Time Limit Exceeded

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