Rumour Days
A school has n students numbered 0 to n - 1. friendships is a list of pairs [a, b] with a != b, each a friendship that works both ways; the same pair may appear more than once. On day 0 the students listed in knowers (at least one, all different) know a rumour. On each following day every student who knows the rumour tells all of their friends, so after day 1 every friend of a day-0 knower knows it, after day 2 their friends know it, and so on.
Return the number of days until every student knows the rumour. Return 0 when knowers already lists every student, and -1 when some student will never hear it.
Example 1
Student 5 hears it from 4 on day 1; the rumour reaches 3 through 1 and 2 on day 3.
Example 2
Students 2 and 3 have no friend who will ever know, so the answer is -1.
Constraints
1 <= n <= 500 <= len(friendships) <= 1000 <= a, b <= n - 1anda != b1 <= len(knowers) <= n, all different, each in0..n - 1
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Graphs problems
- Same Network QueriesEasy
- Tunnels to Every StationEasy
- Blocks to the Nearest ShopMedium
- Build Order ExistsMedium
- Calm SquaresMedium
- Cheapest Toll TripMedium
- Connect All OfficesMedium
- Count the Shortest RoutesMedium