Temporal Reachability Check

Problem

Decide whether dst is temporally reachable from src in an evolving graph.

Process snapshots in order; at each step, edges of the current snapshot may be traversed by nodes reached so far. Return True as soon as dst is reached, and check the start node before any step. snapshots is a list of edge lists.

Hint

A temporal path must respect the chronological order of contacts.

Test cases

case 1

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

expected: true

case 2

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

expected: false

case 3

in: [3,[],1,1]

expected: true

case 4

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

expected: false

Starter codePython

def temporal_reachability(n, snapshots, src, dst):
    # Your code here
    pass

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