Interview Question 1 - Graphs

#1

This question was asked in one interview and i am still hunting for the best solution.

You are given a maze with N cells. Each cell may have multiple entry points but not more than one exit (ie. entry/exit points are unidirectional doors like valves).

The cells are named with an integer value from 0 to N-1.

You need to find the the length of the largest cycle in the maze. Return -1 if there are no cycles.

INPUT FORMAT

First line has the number of cells N
Second line has list of N values of the edge[] array. edge[i] contains the cell number that can be reached from of cell ‘i’ in one step. edge[i] is -1 if the ‘i’th cell doesn’t have an exit.
OUTPUT FORMAT

length of the largest cycle.
Sample input:

23

4 4 1 4 13 8 8 8 0 8 14 9 15 11 -1 10 15 22 22 22 22 22 21

Sample output

6

#2

check whatsapp PM. I solved it there .:slight_smile:

#3

Answer for this question?

#5 
def main():
size = int(input())
cell = input().split()

for i in range(0, len(cell)):
    cell[i] = int(cell[i])
m = -1
for i in range(0, 23):
    if m < check_cycle(cell, i):
        m = check_cycle(cell, i)
print("Largest cycle is made of", m, "nodes")


def check_cycle(cell, start):
i = start
if i in cell:
    cycle = [i]
    j = i
    while 1:
        for k in cycle:
            if cycle.count(k) >= 2:
                if cycle[0] == cycle[-1]:
                    return len(cycle)-1
                else:
                    return 0
        else:
            cycle.append(cell[j])
            j = cell[j]
else:
    return 0


main()