Cascade Depth Seeded

Problem

Simulate an independent cascade and return the number of spreading rounds.

In each round, every newly active node tries to activate each inactive sorted neighbor independently with probability probabilities[v] using the seeded generator. Stop when no new nodes activate or after max_steps; return the number of completed rounds.

Hint

Cascade depth measures how many generations an outbreak survives.

Test cases

case 1

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

expected: 3

case 2

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

expected: 1

case 3

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

expected: 0

case 4

in: [4,[[0,1],[0,2],[0,3]],[0],[0.5,1,1,1],42,10]

expected: 1

Starter codePython

import random
def cascade_depth(n, edges, seeds, probabilities, seed, max_steps):
    # Your code here
    pass

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