Rumor Source Detection Lite

Problem

Guess the rumor source as the node minimizing the sum of shortest-path distances to the infected set.

Run a BFS from every node, keep only nodes that can reach all infected nodes, and return the node with the smallest distance sum (ties by smallest index). Return -1 when no node can reach the whole infected set. edges is a list of [u, v] pairs.

Hint

The rumor center is a robust maximum-likelihood estimate under distance-based models.

Test cases

case 1

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

expected: 1

case 2

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

expected: 0

case 3

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

expected: 2

Starter codePython

def rumor_source_detection(n, edges, infected):
    # Your code here
    pass

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