All problems

Needed-By Manifest

Medium · graph traversal

A workshop builds gadgets out of n parts, numbered 0 to n - 1. Each entry of needs is [a, b], meaning part a needs part b directly. The order of the entries is the order in which they were written in the catalogue.

The kit for a part root is the part itself together with every part it needs, directly or through other parts. For example, if root needs x and x needs y, then x and y are both in the kit.

The stockroom wants the kit's catalogue turned the other way round, as a "needed by" list. For every entry [a, b] of needs whose first part a is in the kit, write the flipped pair [b, a] ("b is needed by a").

Return these flipped pairs in the same order as the entries appear in needs. If root needs nothing, return an empty list [].

Parts may need each other in a circle. No entry has the same part twice, and no entry is written twice.

Examples

Example 1

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

Output: [[2, 1]]

The kit for part 1 is parts 1 and 2. Only the entry [1, 2] starts at a part of the kit, so the list has just its flipped pair.

Example 2

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

Output: [[1, 0], [2, 1], [2, 0]]

The kit is parts 0, 1 and 2. Entries [3, 2] and [4, 0] start outside it, so they are left out.

Example 3

Input: n = 3, needs = [[0, 1], [1, 2], [2, 1]], root = 0

Output: [[1, 0], [2, 1], [1, 2]]

Parts 1 and 2 need each other, so they form a circle. Every entry starts inside the kit and is flipped.

Constraints