# 27.01.2025 [1462. Course Schedule IV]

All innodes for each query in graph #medium #dfs #toposort #floyd_warshall

27.01.2025

1462. Course Schedule IV medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/877

Problem TLDR

All innodes for each query in graph #medium #dfs #toposort #floyd_warshall

Intuition

For each node, we should know all the incoming nodes. Several ways:

• Depth-First Search and cache the results (Kotlin)

• Floyd-Warshall: if i->k and j->k then i->j (Rust)

• Topological Sorting: put zero-incoming nodes into queue, connect siblings (c++)

Approach

• the hardest to grasp is the toposort one: if node i->q then i->q.sibling

Complexity

• Time complexity: $$O(n^2 + q + p)$$, O(n^3 + q + p) for Floyd-Warshall

• Space complexity: $$O(n^2 + q)$$

Code

    fun checkIfPrerequisite(n: Int, pre: Array<IntArray>, q: Array<IntArray>) = {
        val g = pre.groupBy { it[1] }; val dp = HashMap<Int, Set<Int>>()
        fun dfs(i: Int): Set<Int> = dp.getOrPut(i) {
            ((g[i]?.map { dfs(it[0]) }?.flatten() ?: setOf()) + i).toSet()
        }
        q.map { (a, b) -> a in dfs(b) }
    }()

    pub fn check_if_prerequisite(n: i32, pre: Vec<Vec<i32>>, q: Vec<Vec<i32>>) -> Vec<bool> {
        let n = n as usize; let mut p = vec![vec![0; n]; n];
        for e in pre { p[e[1] as usize][e[0] as usize] = 1 }
        for k in 0..n { for i in 0..n { for j in 0..n { 
          if p[i][k] * p[k][j] > 0 { p[i][j] = 1 }}}}
        q.iter().map(|e| p[e[1] as usize][e[0] as usize] > 0).collect()
    }

    vector<bool> checkIfPrerequisite(int n, vector<vector<int>>& pre, vector<vector<int>>& qw) {
        vector<vector<int>> g(n); vector<int> ind(n); bool dp[100][100] = {}; queue<int> q;
        for (auto& p: pre) g[p[0]].push_back(p[1]), ind[p[1]]++, dp[p[0]][p[1]] = 1;
        for (int i = 0; i < n; ++i) if (!ind[i]) q.push(i);
        while (size(q)) { for (int v: g[q.front()]) {
            for (int i = 0; i < n; ++i) if (dp[i][q.front()]) dp[i][v] = 1;
            if (!--ind[v]) q.push(v);
        } q.pop(); }
        vector<bool> r; for (auto& x: qw) r.push_back(dp[x[0]][x[1]]); return r;
    }