Problem: 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.

Submission attempts (in order):
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product

import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
from numba import jit

INF = 1 << 50
EPS = 1e-8

@jit
def solve(S):
    N = S.shape[0]
    ans = 0
    for k in range(N):
        #print(k, '-------------------')
        seen = set()
        seen.add(k)
        merged = np.ones(N, dtype=np.int32) * (-1)
        merged[0] = k
        count = 0
        while merged[0] > -1:
            #print(merged)
            count += 1
            nexts = np.ones(N, dtype=np.int32) * (-1)
            p = 0
            for i in merged:
                if i == -1:break
                for j, e in enumerate(S[i]):
                    if e and not j in seen:
                        #print(j)
                        nexts[p] = j
                        p += 1
                        seen.add(j)
            
            for i in range(N):
                if nexts[i] == -1:break
            checks = S[nexts[:i],:][:, nexts[:i]]
            #print(checks)
            if checks.sum() != 0:
                seen = set()
                break
            merged = nexts
        if len(seen) == N:
            ans = max(ans, count)
    if ans:
        print(ans)
    else:
        print(-1)


def run():
    N = int(sysread())
    S = []
    for i in range(N):
        S.append(list(map(int, list(input()))))
    S = np.array(S, dtype = np.int8)

    solve(S)


if __name__ == "__main__":
    run()


# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product

import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8

def check_merge(merged,S):
    merged = np.array(merged)
    check = S[merged][:, merged]
    if check.sum():
        return False
    return True

def run():
    N = int(sysread())
    S = []
    for i in range(N):
        S.append(list(map(int, list(input()))))
    S = np.array(S, dtype=np.int8)

    ans = 0

    #for s in S:
    #    print(s)
    for k in range(N):
        #print(k, '-------------------')
        seen = set()
        seen.add(k)
        merged = [k]
        count = 0
        while merged:
            #print(merged)
            count += 1
            nexts = []
            for i in merged:
                for j, e in enumerate(S[i]):
                    if int(e) and not j in seen:
                        nexts.append(j)
                        seen.add(j)
            if not check_merge(merged, S):
                seen = set()
                break
            merged = nexts
        if len(seen) == N:
            ans = max(ans, count)
    if ans:
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    run()


Verdicts: Time Limit Exceeded

Accepted