What signals in a problem statement indicate the DFS order / DAG DP sub-pattern?

"all ancestors" / "everyone richer than"; "longest increasing path" in a matrix (edges go from smaller to larger); the graph is promised to be acyclic, or the rule (strictly increasing) makes cycles impossible

DFS order / DAG DP (Topological Sort Sub-pattern)

Q: What makes DFS order / DAG DP different from other sub-patterns?

**All Ancestors** runs a DFS from each node and adds it to everything it reaches. **Loud and Rich** is memoised DFS: the quietest among me and the answers of those richer than me. **Longest Increasing Path** is the same memo on grid cells; strictly increasing moves can't loop, so no visited set is needed.

Compute a value for every node that depends on the nodes after it (or before it) in a DAG.

Signals in the problem statement

›
"all ancestors" / "everyone richer than"
›
"longest increasing path" in a matrix (edges go from smaller to larger)
›
the graph is promised to be acyclic, or the rule (strictly increasing) makes cycles impossible

What makes it different

All Ancestors runs a DFS from each node and adds it to everything it reaches. Loud and Rich is memoised DFS: the quietest among me and the answers of those richer than me. Longest Increasing Path is the same memo on grid cells; strictly increasing moves can't loop, so no visited set is needed.

Questions

ordered from “learn the idea” to “recognise it without help”

1
All Ancestors of a Node in a DAG
Basic Anchor·LeetCode #2192
WalkthroughMedium
2
Loud and Rich
Slight Variation·LeetCode #851
WalkthroughMedium
3
Longest Increasing Path in a Matrix
Medium·LeetCode #329
WalkthroughHard

Template

dag-dp-template.cpp

// DP on a DAG with a memoised DFS: a node's answer is built from its successors' answers.
// Here: the longest path (in nodes) that starts at each node.
int longestFrom(int u, const vector<vector<int>>& adj, vector<int>& memo) {
    if (memo[u] != 0) return memo[u];             // already solved: each node is solved once
    int best = 1;
    for (int v : adj[u]) best = max(best, 1 + longestFrom(v, adj, memo));
    return memo[u] = best;
}

int longestPath(int n, const vector<vector<int>>& edges) {   // the graph must be a DAG
    vector<vector<int>> adj(n);
    for (auto& e : edges) adj[e[0]].push_back(e[1]);
    vector<int> memo(n, 0);
    int ans = 0;
    for (int u = 0; u < n; u++) ans = max(ans, longestFrom(u, adj, memo));
    return ans;
}

Remember this · Topological Sort

Trigger

Prerequisites, dependencies, build order, "can all courses be finished?", ordering letters from sorted words.

Think

Is this a directed graph where some things must happen before others?

Key question

Which nodes currently have in-degree 0?

Cycle detection / feasibility Build the graph, then sort