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 = []
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 = []
                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
    
    # DP
    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: Accepted

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

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

def wf(d):
    n=len(d)
    for k in range(n):#       // 経由する頂点
        for i in range(n):#    // 始点
            for j in range(n):#  // 終点
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

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

v=[-1]*(n)

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

bfs(bg)

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

print(diam+1)
exit()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return [int(i) for i in input().rstrip()]
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    s = S()
    k = II()
    ans = 0
    lis = []
    i = 0
    tmp = 1
    while len(s) > i + 1:
        if s[i] == s[i + 1]:
            tmp += 1
        else:
            lis.append((s[i], tmp))
            tmp = 1
        i += 1
    lis.append((s[i], tmp))
    if lis[0][0] == lis[-1][0]:
        if len(lis) == 1:
            ans += k * lis[0][1] // 2
            print(ans)
            return
        ans -= (lis[0][1] // 2 + lis[-1][1] // 2) * (k - 1)
        ans += (lis[0][1] + lis[-1][1]) // 2 * (k - 1)
    for _, b in lis:
        ans += b // 2 * k
    print(ans)
    return

#B
def B():
    n = II()
    s = SR(n)
    edg = [[] for i in range(n)]
    check = [0] * n
    for i in range(n):
        for k in range(n):
            if i == k:
                continue
            if s[i][k]:
                edg[i].append(k)
                edg[k].append(i)
            else:
                s[i][k] = inf
    for i in range(n):
        q = deque([i])
        if check[i] == 0:
            check[i] += 1
        while q:
            p = q.pop()
            for k in edg[p]:
                if check[k]:
                    if (check[k] ^ check[p]) & 1:
                        continue
                    print(-1)
                    return
                else:
                    check[k] = check[p] + 1
                    q.appendleft(k)

    for x in range(n):
        for i in range(n):
            for k in range(n):
                s[i][k] = min(s[i][k], s[i][x] + s[x][k])
    ans = 0
    for i in range(n):
        for k in range(n):
            if s[i][k] == inf:
                continue
            ans = max(s[i][k], ans)
    print(ans+1)
# C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    B()

Submission status: Accepted

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
    for i in range(n):
        if col[i] >= 0: continue
        que = deque([[i, 0]])
        while que:
            v, c = que.popleft()
            if col[v] == -1:
                col[v] = c
            elif col[v] == c:
                continue
            else:
                return 0
            for ne in E[v]:
                if col[ne] == c:
                    return 0
                if col[ne] < 0:
                    que.append([ne, 1-c])
    return 1

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: Accepted

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()
            if col[v] == -1:
                col[v] = c
            elif col[v] == c:
                continue
            else:
                f = 1
                break
            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: Accepted

Solution code:
N=int(input())
S=[[int(s) for s in input()] for i in range(N)]
c=[[] for i in range(N)]
for i in range(N):
    for j in range(N):
        if S[i][j]:
            c[i].append(j)
def bfs(p,g,d):
    r=0
    q=[]
    for e in p:
        if x[e]==g^1:
            return -1
        elif x[e]==-1:
            x[e]=g
            for f in c[e]:
                q.append(f)
    if len(q)==0:
        return d
    return bfs(q,g^1,d+1)
r=0
for i in range(N):
    x=[-1]*N
    d=bfs([i],0,0)
    if d==-1:
        break
    r=max(r,d)
print(r if d!=-1 else d)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
# from copy import deepcopy, copy

import queue
from collections import deque




def main():
    node_num = int(input())
    data = [list(map(int, list(input()))) for i in range(node_num)]

    graph_data = defaultdict(set)
    dist_data = [[200 for i in range(node_num)] for j in range(node_num)]
    for i in range(node_num):
        dist_data[i][i] = 0
        for j in range(node_num):
            if data[i][j]:
                dist_data[i][j] = 1
                graph_data[i].add(j)

    which_graph = [-1 for i in range(node_num)]
    now_set = set()
    next_set = set()
    now_set.add(0)
    which_graph[0] = 0
    flg = 0
    while len(now_set) > 0:
        for now_ele in now_set:
            for next_ele in graph_data[now_ele]:
                if which_graph[next_ele] == -1:
                    which_graph[next_ele] = 1 ^ which_graph[now_ele]
                    next_set.add(next_ele)
                else:
                    if which_graph[now_ele] ^ which_graph[next_ele] == 0:
                        flg = 1
                        break
        now_set = next_set
        next_set = set()


    if flg:
        print(-1)
        sys.exit()



    for k in range(node_num):
        for i in range(node_num):
            for j in range(node_num):
                dist_data[i][j] = min(dist_data[i][j], dist_data[i][k] + dist_data[k][j])

    ans = 0
    for i in range(node_num):
        ans = max(ans, max(dist_data[i]))

    print(ans + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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 longest(i, edge, N):
    q = collections.deque()
    q.append((i, 1))
    dist = dict()
    ans = 1
    for j in range(N): dist[j] = -1
    flag = True
    while q:
        nn, nd = q.popleft()
        if dist[nn] == -1:
            ans = max(nd, ans)
            dist[nn] = nd
            for next_node in edge[nn]:
                if dist[next_node] == -1: q.append((next_node, nd + 1))
                elif abs(dist[next_node] - nd) != 1: flag = False
        elif dist[nn] != nd:
            ans = -1
            break
    #print(i, dist)
    return (ans if flag else -1)

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:
        ans = -1
        for i in range(N):
            ans = max(ans, longest(i, edge, N))
        print(ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
from scipy.sparse.csgraph import floyd_warshall as wf
from collections import deque
input = sys.stdin.readline

def main():
    N = int(input())
    link = [[0 if c == "0" else 1 for c in list(input().strip())] for i in range(N)]
    # print(link)
    check = [False] * N
    colors = [True] * N

    q = deque()
    q.append((0, True, 1))
    ok = True
    check[0] = True
    while len(q) > 0:
        i, color, step = q.popleft()
        # print(i, color, step)
        for nex, c in enumerate(link[i]):
            if c == 1:
                if check[nex]:
                    if colors[nex] == color:
                        ok = False
                        break
                else:
                    check[nex] = True
                    colors[nex] = not(color)
                    q.append((nex, not(color), step+1))
        if not ok:
            break
    
    if ok:
        ans = 0
        link = wf(link)
        for i in range(N):
            ans = max(ans, int(max(link[i])))
        print(ans + 1)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007



n = I()
graph = SR(n)


def bfs(i):
    cost = [INF] * n
    cost[i] = 0
    que = deque([i])
    while que:
        cur = que.popleft()
        for nxt in range(n):
            if int(graph[cur][nxt]):
                c1 = cost[cur]
                if cost[nxt] != INF and cost[nxt] % 2 != (c1 + 1) % 2:
                    return -1
                else:
                    if cost[nxt] > c1 + 1:
                        cost[nxt] = c1 + 1
                        que += [nxt]
    return max(cost)



ret = 0
for j in range(n):
    if bfs(j) < 0:
        print(-1)
        break
    else:
        ret = max(ret, bfs(j))
else:
    print(ret + 1)

Submission status: Accepted

Solution code:
import collections

n = int(input())
s = []
for _ in range(n):
    ch = input()
    s.append([int(c) for c in ch])


def graph(i, n, s):
    flag = [-2 for _ in range(n)]
    flag[i] = 1
    que = collections.deque([i])
    while que:
        target = que.popleft()
        for j in range(n):
            if s[target][j] == 1:
                if flag[j] == -2:
                    flag[j] = flag[target] + 1
                    que.append(j)
                elif flag[j] != flag[target] + 1 and flag[j] != flag[target] - 1:
                    return [-1, -1]
    mf = max(flag)
    return [flag.index(mf), mf]


r1 = graph(0, n, s)
if r1[0] == -1:
    print(-1)
else:
    res = r1[1]
    for i in range(1, n):
        r = graph(i, n, s)
        res = max(res, r[1])
    print(res)

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
V = []
for i in range(N):
    V.append(list(map(int, input()[:-1])))

INF = float('inf')

def is_bipartite_graph():
    team = [0] * N
    valid = True
    q = deque()
    q.append(0)
    team[0] = 1
    while valid and len(q):
        u = q.popleft()
        for v, e in enumerate(V[u]):
            if e:
                if not team[v]:
                    team[v] = team[u]%2 + 1
                    q.append(v)
                else:
                    if (team[v] - team[u])%2 == 0:
                        valid = False
                        break
    return valid


def get_distances(s):
    q = deque()
    q.append(s)
    d = [INF] * N
    d[s] = 0
    while len(q):
        u = q.popleft()
        for v, e in enumerate(V[u]):
            if e:
                if d[v] > d[u] + 1:
                    d[v] = d[u] + 1
                    q.append(v)
    return d


def get_diameter():
    dmax = 0
    for i in range(N):
        d = get_distances(i)
        dmax = max(max(d), dmax)
    return dmax


if is_bipartite_graph():
    print(get_diameter()+1)
else:
    print(-1)

Submission status: Accepted

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)
    
    colors = [-1] * N
    visited = [False] * N
    def is_binarygraph(v, color):
        visited[v] = True
        for n in G[v]:
            if colors[n] == color:
                return False
            if visited[n]:
                continue
            colors[n] = (color + 1) % 2
            if not is_binarygraph(n, colors[n]):
                return False
        return True
    
    colors[0] = 0
    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 G[i]:
            d[i][j] = 1
    for i in range(N):
        d[i][i] = 0
    
    fw = floyd_warshall(d)
    return np.max(fw) + 1

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    n = len(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

def solve():
    N = II()
    edge_list = {}
    # i, j は 0 origin で入れる
    for i in range(N):
        edge_list[i] = []
        ei = SI()
        for j, e in enumerate(ei):
            if e == '1':
                edge_list[i].append(j)

    # 二部グラフチェック
    # -1, 1 をアサインしていく
    bip = [0 for i in range(N)]

    # キュー
    from collections import deque
    qu = deque()
    qu.append((-1, 0)) # 親のbip, nodeid。0はおやを-1と仮定する

    # 既読
    seen = set()
    is_bip = True


    while qu:
        parent_bip, n = qu.popleft()

        # 親と同じ側にアサインされているなら、bipではないので終了
        if parent_bip * bip[n] == 1:
            is_bip = False
            print(-1)
            return

        # 親と反対側にアサイン
        bip[n] = parent_bip * -1

        if n not in seen:
            for neib in edge_list[n]:
                qu.append((bip[n], neib))
        dprint('parent_bip:',parent_bip, 'n:', n, 'edge:', edge_list[n], 'q:', qu, seen)
        seen.add(n)

    dprint(bip)

    # bipなら直径
    mx = N + 1
    d = [[mx for i in range(N)] for i in range(N)]
    for i in range(N):
        for e in edge_list[i]:
            d[i][e] = 1
        d[i][i] = 0
    d = warshall_floyd(d)

    ans = 0
    for i in range(N):
        for j in range(N):
            ans = max(ans, d[i][j])

    dprint(d)

    print(ans+1)

solve()

Submission status: Accepted

Solution code:
from collections import deque

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

# 二部グラフ判定
memo = [-1] * n
memo[0] = 0
q = deque([(0, -1)])
while q:
    v, p = q.popleft()
    for nv in range(n):
        if s[v][nv] == '1':
            if nv == p:
                continue
            if memo[nv] == -1:
                memo[nv] = (memo[v] + 1) % 2
                q.append((nv, v))
            else:
                if memo[nv] == memo[v]:
                    print(-1)
                    exit()

# ワーシャルフロイドでグラフの直径を求めてもよし
INF = float('inf')
dp = [[1 if c == '1' else INF for c in row] for row in s]

for i in range(n):
    dp[i][i] = 0

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

dist = 0
for i in range(n):
    d = 0
    for j in range(n):
        d = max(d, dp[i][j])
    dist = max(d, dist)

print(dist+1)

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**7)
N = int(input())
S = [input().strip() for _ in range(N)]

flg = False
max_cnt = 1
for sp, row in enumerate(S):
    # start BFS
    C = [0]*N
    C[sp] = 1
    q = deque([])
    for i, v in enumerate(row):
        if v == '1':
            q.append(int(i))

    cnt = 1 # length
    c = -1 # color
    while q:
        for i in range(len(q)):
            np_ind = q.popleft()
            if C[np_ind] == -c:
                print(-1)
                exit()
            elif C[np_ind] == c:
                pass
            else:
                C[np_ind] = c
                for i, v in enumerate(S[np_ind]):
                    if v == '1' and C[i] == 0:
                        q.append(int(i))
        cnt += 1
        c *= -1
    if max_cnt < cnt:
        max_cnt = cnt

print(max_cnt)

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
graph=[[False for j in range(n)] for i in range(n)]
for i in range(n):
    s=input()
    for j in range(n):
        if s[j]=="1":
            graph[i][j]=True
L=0
def bfs(i):
    longest=0
    global dist
    dist=[-1]*n
    dist[i]=0
    D=deque([i])
    while D:
        v=D.popleft()
        for j in range(n):
            if graph[v][j]==False:continue
            if dist[j]!=-1:
                if abs(dist[v]-dist[j])==1:continue
                else:return -1
            else:
                D.append(j)
                dist[j]=dist[v]+1
                if dist[j]>longest:longest=dist[j]
    return longest
for i in range(n):
    A=bfs(i)
    
    if A==-1:print(-1);exit()
    if A>L:L=A
print(L+1)

Submission status: Accepted

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


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

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall
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)
g2=[[0]*n for _ in range(n)]
for i in range(n):
  for j in range(n):
    g2[i][j]=int(arr[i][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
d=floyd_warshall(g2)
for i in range(n):
  ans=max(ans,int(max(d[i])+1))
print(ans)

Submission status: Accepted

Solution code:
import queue
import numpy as np
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
    
def ngoCheck():
    stack = [Nodes[0]]
    Nodes[0].checkNgo = 0
    while stack:
        node = stack.pop()
        for i in node.nextNode:
            if Nodes[i].checkNgo != -1 and Nodes[i].checkNgo == node.checkNgo:
                return False
            if Nodes[i].checkNgo == -1:
                Nodes[i].checkNgo = (node.checkNgo+1)%2
                stack.append(Nodes[i])
    return True
    
if not check(Nodes[0],0):
    print(-1)
    exit(0)
    
def solv():
    d = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        for j in range(n):
            if j in Nodes[i].nextNode:
                d[i][j] = 1
            else:
                d[i][j] = np.inf
    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]
    return d
    
def saidai(d):
    maxi = 0
    for i in range(n):
        for j in range(n):
            if i==j:
                continue
            maxi = max(maxi,d[i][j])
    return maxi
    
d = solv()
print(saidai(d)+1)

Submission status: Accepted

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((0, 0))
ok = True
while dq:
    v, d = dq.popleft()
    if dist[v] == d:
        continue
    if dist[v] == -1:
        dist[v] = d
    else:
        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: Accepted

Solution code:

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

import sys
import copy

ans = 0
adj_list = [[]for _ in range(N)]
for i in range(N):
    for j in range(i+1,N):
        if int(S[i][j]):
            adj_list[i].append(j)
            adj_list[j].append(i)


for kk in range(N):
    q = []
    visited = [False] * N
    cnt = 1
    visited[kk] = True
    q.append(kk)
    VC = 1
    while VC < N:
        nextv = copy.copy(q)
        q = []
        nextv = list(set(nextv))
        #子の要素同士の連結チェック
        L = len(nextv)
        for i in range(L):
            if not(visited[nextv[i]]):
                visited[nextv[i]] = True
                VC += 1
            for j in range(i+1,L):
                if (int(S[nextv[i]][nextv[j]])):
                    print(-1)
                    sys.exit()
        
        for nv in nextv:
            for v in adj_list[nv]:
                if not(visited[v]):
                    q.append(v)
    
        cnt += 1
    
    ans = max(ans,cnt-1)
        
#
print(ans)

Submission status: Accepted

Solution code:
N=int(input())

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

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

Submission status: Accepted

Solution code:
from collections import deque

def solve(init):
  groups = [-1 for i in range(N)]
  groups[init] = 1
  q = deque()
  q.append(init)
  while len(q) > 0:
    u = q.popleft()
    for v in range(N):
      if M[u][v] == 0:
        continue
      if groups[v] != -1:
        if groups[v] == groups[u]-1 or groups[v] == groups[u]+1:
          continue
        else:
          return -1
      groups[v] = groups[u] + 1
      q.append(v)
  return max(groups)


N = int(input())
M = [list(map(int, list(input()))) for i in range(N)]

res = -1
for u in range(N):
  res = max(res, solve(u))

print(res)