Kidney Exchange Cycle Length

Problem

Find the length of the shortest directed cycle through a given start node in a donor graph.

Solve the shortest cycle by BFS from every out-neighbor of start back to start. Return the cycle length, or -1 when start lies on no cycle. edges is a list of directed [u, v] pairs.

Hint

Short cycles let more donor pairs be transplanted simultaneously.

Test cases

case 1

in: [[[0,1],[1,2],[2,0],[2,3],[3,2]],0]

expected: 3

case 2

in: [[[0,1],[1,2],[2,3]],0]

expected: -1

case 3

in: [[[0,1],[1,0]],0]

expected: 2

case 4

in: [[[0,1],[1,0],[0,2],[2,1]],0]

expected: 2

Starter codePython

def kidney_cycle_length(edges, start):
    # Your code here
    pass

4 test cases · run your code against them in the editor