Show problems as
Classic problem #3310MediumDepth-First SearchBreadth-First SearchGraph Theory

Remove Methods From Project

Real-world version: Pruning a Faulty Module and Its Imports
Tracked in this browser only
Read Remove Methods From Project on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A codebase has count modules, numbered 0 through count - 1. The import graph is given as a list of directed pairs: imports[i] = [a, b] means module a imports module b. A module never imports itself and no pair is listed twice.

Module faulty has been found broken. A cleanup marks faulty together with every module that can be reached from it by following one or more imports, since those are only pulled in on its account.

The cleanup is only safe if nothing outside the marked group depends on it. So if any module that is not marked imports a module that is marked, the cleanup is called off and every module stays. Otherwise all the marked modules are deleted.

Return the numbers of the modules still in the codebase afterwards, in increasing order.

Examples

Example 1

Input
count = 5, faulty = 0, imports = [[0, 1], [1, 2], [3, 4]]
Output
[3, 4]

Following imports from module 0 reaches modules 1 and 2, so the marked group is 0, 1 and 2. The only other pair is [3, 4], whose importer and target are both unmarked, so the cleanup goes ahead and modules 3 and 4 remain.

Example 2

Input
count = 5, faulty = 1, imports = [[0, 1], [1, 2], [2, 3]]
Output
[0, 1, 2, 3, 4]

The marked group is 1, 2 and 3. Module 0 is not marked and it imports module 1, which is, so the cleanup is called off and all five modules stay.

Example 3

Input
count = 3, faulty = 2, imports = []
Output
[0, 1]

With no imports at all the marked group is just module 2, and nothing depends on it, so modules 0 and 1 remain.

Constraints

  • 1 <= count <= 10^5
  • 0 <= faulty <= count - 1
  • 0 <= imports.length <= 2 * 10^5
  • imports[i].length == 2
  • 0 <= imports[i][0], imports[i][1] <= count - 1
  • imports[i][0] != imports[i][1]
  • No two entries of imports are the same pair.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def surviving_modules(count: int, faulty: int, imports: list[list[int]]) -> list[int]:
Java
public List<Integer> survivingModules(int count, int faulty, int[][] imports)

More on the same topics