FunctionRacerProblemsRace

Rumour Days

EasyGraphsPython, JavaScript, TypeScript, Java, C++

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

n 6
friendships [[0,1],[1,2],[2,3],[4,5]]
knowers [0,4]
returns 3

Student 5 hears it from 4 on day 1; the rumour reaches 3 through 1 and 2 on day 3.

Example 2

n 4
friendships [[0,1],[2,3]]
knowers [0]
returns -1

Students 2 and 3 have no friend who will ever know, so the answer is -1.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Graphs problems