All problems

Lantern Relay Times

Medium · topological sort

A festival has n paper lanterns, numbered 0 to n - 1. Light travels between them along one-way beams. Each entry [a, b, delay] in links is a beam from lantern a to lantern b that takes delay seconds to arrive.

A lantern with no beam pointing at it is lit by hand at second 0. Any other lantern lights up at the moment the last of the beams pointing at it has arrived, where a beam leaves its lantern the moment that lantern lights up.

Return a list with the second at which each lantern lights up, so that position i holds the time of lantern i. If some lantern can never light up because the beams run in a loop, return an empty list.

Several beams may join the same two lanterns, and a lantern may even have a beam pointing at itself.

Examples

Example 1

Input: n = 3, links = [[0, 1, 2], [1, 2, 3]]

Output: [0, 2, 5]

Lantern 0 is lit by hand. Its beam reaches lantern 1 at second 2, and that beam reaches lantern 2 at second 5.

Example 2

Input: n = 4, links = [[0, 2, 5], [1, 2, 2], [2, 3, 1]]

Output: [0, 0, 5, 6]

Lanterns 0 and 1 are lit by hand. Lantern 2 waits for the slower beam, which arrives at second 5, and then lantern 3 lights one second later.

Example 3

Input: n = 2, links = [[0, 1, 1], [1, 0, 1]]

Output: []

Each lantern waits for the other's beam, so neither ever lights.

Constraints