LeetCode Entry

2872. Maximum Number of K-Divisible Components

21.12.2024 hard 2024 kotlin rust

Max connected components divisible by k in graph

2872. Maximum Number of K-Divisible Components hard blog post substack youtube deep-dive

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/839

Problem TLDR

Max connected components divisible by k in graph #hard #toposort

Intuition

Can’t solve without hints. The hints: walk from any node, merge values if sum is not divisible by k.

If we go from each leaf up to the parent, we can compute the sum of this parent.

Approach

• we can walk with DFS
• we can walk with BFS, doing the Topological Sorting algorithm: decrease in-degrees, add in-degrees of 1
• we can use values as a sum results holder

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(n)\)

Code

    fun maxKDivisibleComponents(n: Int, edges: Array<IntArray>, values: IntArray, k: Int): Int {
        val g = Array(n) { ArrayList<Int>() }; for ((a, b) in edges) { g[a] += b; g[b] += a }
        fun dfs(crr: Int, frm: Int): Int =
            g[crr].sumOf { nxt ->
                if (nxt == frm) 0 else dfs(nxt, crr).also { values[crr] += values[nxt] % k }
            } + if (values[crr] % k > 0) 0 else 1
        return dfs(0, 0)
    }

    pub fn max_k_divisible_components(n: i32, edges: Vec<Vec<i32>>, mut values: Vec<i32>, k: i32) -> i32 {
        let (mut cnt, mut g, mut deg) = (0, vec![vec![]; n as usize], vec![0; n as usize]);
        for e in edges {  let (u, v) = (e[0] as usize, e[1] as usize);
            deg[u] += 1; deg[v] += 1; g[u].push(v); g[v].push(u) }
        let mut q = VecDeque::from_iter((0..n as usize).filter(|&u| deg[u] < 2));
        while let Some(u) = q.pop_front() {
            deg[u] -= 1; if values[u] % k == 0 { cnt += 1 }
            for &v in &g[u] {
                if deg[v] < 1 { continue }
                deg[v] -= 1; values[v] += values[u] % k;
                if deg[v] == 1 { q.push_back(v); }
            }
        }; cnt
    }

    int maxKDivisibleComponents(int n, vector<vector<int>>& edges, vector<int>& values, int k) {
        vector<vector<int>> g(n); vector<int> deg(n); int res = 0; queue<int> q;
        for (auto e: edges) g[e[0]].push_back(e[1]), g[e[1]].push_back(e[0]);
        for (int i = 0; i < n; ++i) if ((deg[i] = g[i].size()) < 2) q.push(i);
        while (q.size()) {
            int u = q.front(); q.pop(); --deg[u];
            res += values[u] % k == 0;
            for (int v: g[u]) if (deg[v]) {
                values[v] += values[u] % k;
                if (--deg[v] == 1) q.push(v);
            }
        } return res;
    }