Module Dependency Queries

EasyAdvanced Graphs

Problem

A build system has n modules. Each imports[i] = [a, b] means module a imports module b directly. A module depends on another if it imports it directly or through a chain of imports. Every module depends on itself.

For each query [x, y] in queries, answer whether module x depends on module y. Return the answers in order.

Example 1

Input:
n = 4, imports = [[0,1],[1,2],[3,2]], queries = [[0,2],[2,0],[3,1],[3,2]]
Output:
[true, false, false, true]

0 → 1 → 2, so 0 depends on 2. Imports are one-way, so 2 does not depend on 0.

Example 2

Input:
n = 2, imports = [], queries = [[0,1],[1,1]]
Output:
[false, true]

Constraints

  • 1 ≤ n ≤ 100
  • 0 ≤ imports.length ≤ n·(n - 1)
  • 1 ≤ queries.length ≤ 10^4

Hint

Show the first hint

With up to 10^4 queries, a DFS per query repeats a lot of work.

Walkthrough

How to approach it

01Clarify before coding

  • Is the relation directed? Yes, a imports b says nothing about b importing a.
  • Does a module depend on itself? Yes, always.
  • Can imports form a cycle? Yes; then every module on the cycle depends on every other.

02Brute force

Run a DFS from x for every query.

Cost: O(Q · (n + E)) ≈ 10^4 · 10^4 = 10^8 in the worst case.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.