Maximum Number of K-Divisible Components

Leetcode Problem:

• Maximum Number of K-Divisible Components

Summary

• Given an undirected tree with n nodes, edges, values, and k, find the maximum number of components in any valid split of the tree such that the value of each connected component is divisible by k.

Approach

• This solution uses a depth-first search (DFS) traversal to explore the tree and find the maximum number of components
• It maintains two arrays, undirectAdj and directAdj, to store the adjacency list of the tree
• The solution also uses two flags, visited and visited2, to keep track of visited nodes during the traversal
• The traversal function is called recursively to explore the tree, and the solution updates the values of the nodes based on the divisibility of their sum by k.

Complexity

• O(n log n) due to the sorting of the leaf nodes in the leafs array.

Explanation

• The solution starts by building the adjacency list of the tree using the undirectAdj and directAdj arrays
• Then, it calls the traversal function to explore the tree and find the leaf nodes
• The traversal function uses a recursive approach to explore the tree, and it updates the values of the nodes based on the divisibility of their sum by k
• The solution maintains two arrays, leafs, to store the leaf nodes of the tree
• The solution iterates over the leaf nodes and updates their values based on the divisibility of their sum by k
• Finally, the solution returns the maximum number of components in any valid split of the tree.

Solution Code:

class Solution {
public:
    vector undirectAdj[30000];
    vector directAdj[30000];
    vector leafs[2];
    bool visited[30000];
    bool visited2[30000];
    int in[30000];
    int succeed = 0;
    void traversal(int root){
        visited[root] = true;
        int nextCnt = 0;
        for(int i = 0 ; i < undirectAdj[root].size(); i++){
            int next = undirectAdj[root][i];
            if(visited[next]){
                continue;
            }
            nextCnt++;
            directAdj[next].push_back(root);
            in[root]++;
            traversal(next);
        }
        if(nextCnt == 0){
            leafs[0].push_back(root);
        }
    }
    int maxKDivisibleComponents(int n, vector>& edges, vector& values, int k) {
        
        for(int i = 0 ; i < edges.size(); i++){
            int a = edges[i][0];
            int b = edges[i][1];
            undirectAdj[a].push_back(b);
            undirectAdj[b].push_back(a);
        }
        int root = 0;
        traversal(root);
        int leafIdx = 0;
        int ans = 0;
        bool end = false;
        while(true){
            leafs[leafIdx^1].clear();
            for(int i = 0 ; i < leafs[leafIdx].size(); i++){
                int cur = leafs[leafIdx][i];
                if(succeed >= n-1 && cur == root){
                    end = true;
                    break;
                }
                if(cur == root){
                    continue;
                }
                int next = directAdj[cur][0];
                if(visited2[cur]) continue;
                visited2[cur] = true;
                succeed++;
                if(values[cur] % k){ 
                    values[next] = (values[next] + values[cur]) % k;
                } else{
                    ans++;
                }
                in[next]--;
                if(in[next] == 0){
                    leafs[leafIdx^1].push_back(next);
                }
            }
            if(end) break;
            leafIdx ^= 1;
        }
        
        if(values[root] % k){
            return 1;
        } else{
            return ans + 1;
        }
    }
};