Quarantine a Faulty Function

Medium

A project has n functions numbered 0 to n - 1. A pair [a, b] in the list calls means that function a calls function b. A bug was found in function faulty. The suspects are faulty itself and every function it can reach through a chain of calls. The plan is to delete them all from the project. However, the group can only be deleted if no function outside it calls any function inside it; otherwise the project would break. In that case nothing is deleted. Return the numbers of the functions that remain in the project, in any order.

Example 1

n=5, faulty=1, calls=[[0, 1], [1, 2], [2, 3], [4, 0]] → [0, 1, 2, 3, 4]

Functions 1, 2 and 3 are suspect (1 reaches them directly or through 2). But function 0 is not suspect and calls 1, so the group cannot be removed and all functions stay.

Example 2

n=6, faulty=2, calls=[[2, 3], [3, 4], [0, 1], [1, 5]] → [0, 1, 5]

Functions 2, 3 and 4 are suspect and nobody outside calls them. They are removed, leaving 0, 1 and 5.

Example 3

n=2, faulty=0, calls=[[1, 0]] → [0, 1]

Constraints

1 ≤ n ≤ 10⁵
0 ≤ faulty < n
0 ≤ len(calls) ≤ 2·10⁵
calls[i] = [a, b], 0 ≤ a, b < n, a ≠ b
All pairs in calls are distinct

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search Graph

Similar problems

Module Build Order Medium Course Enrollment Queue Medium Do the Links Form a Tree Medium Best Roots for a Tree Medium Isolated Groups in a Network Medium

Input

n=5, faulty=1, calls=[[0, 1], [1, 2], [2, 3], [4, 0]]

Expected

[0, 1, 2, 3, 4]

Run checks the first 3 tests in your browser. Submit checks all 79 tests on the server, hidden ones included.