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;
}
Thanks for reading DMITRII’s Substack! Subscribe for free to receive new posts and support my work.
