Maximum Number of K-Divisible Components

class Solution {
public:
    int maxDivisibleGroups(int nodes, vector<vector<int>>& connections,
                           vector<int>& nodeValues, int divisor) {
        if (nodes < 2) return 1;

        int divisibleCount = 0;
        vector<vector<int>> adjacencyList(nodes);
        vector<int> incomingEdges(nodes, 0);

        // Construct adjacency list and track incoming edge count for each node
        for (const auto& connection : connections) {
            int u = connection[0], v = connection[1];
            adjacencyList[u].push_back(v);
            adjacencyList[v].push_back(u);
            incomingEdges[u]++;
            incomingEdges[v]++;
        }

        // Use 64-bit integers to avoid overflow issues
        vector<long long> extendedValues(nodeValues.begin(), nodeValues.end());

        // Queue for BFS, starting with leaf nodes
        queue<int> processingQueue;
        for (int i = 0; i < nodes; i++) {
            if (incomingEdges[i] == 1) {
                processingQueue.push(i);
            }
        }

        // BFS with processing of values and in-degrees
        while (!processingQueue.empty()) {
            int current = processingQueue.front();
            processingQueue.pop();
            incomingEdges[current]--;

            long long contribution = 0;

            // Check divisibility condition for the current node
            if (extendedValues[current] % divisor == 0) {
                divisibleCount++;
            } else {
                contribution = extendedValues[current];
            }

            // Update neighboring nodes
            for (int neighbor : adjacencyList[current]) {
                if (incomingEdges[neighbor] == 0) {
                    continue;
                }

                incomingEdges[neighbor]--;
                extendedValues[neighbor] += contribution;

                if (incomingEdges[neighbor] == 1) {
                    processingQueue.push(neighbor);
                }
            }
        }

        return divisibleCount;
    }
};

class Solution {

    public int countValidComponents(
        int vertices,
        int[][] connections,
        int[] nodeValues,
        int divisor
    ) {
        if (vertices < 2) return 1; // Early exit for very small graphs

        int validCount = 0;
        List<List<Integer>> adjacencyList = new ArrayList<>();
        int[] degrees = new int[vertices];

        // Construct the graph structure
        for (int i = 0; i < vertices; i++) {
            adjacencyList.add(new ArrayList<>()); // Initialize adjacency list for each vertex
        }
        for (int[] connection : connections) {
            int from = connection[0], to = connection[1];
            adjacencyList.get(from).add(to);
            adjacencyList.get(to).add(from);
            degrees[from]++;
            degrees[to]++;
        }

        // Convert node integers to long to handle large sums
        long[] extendedValues = new long[vertices];
        for (int i = 0; i < vertices; i++) {
            extendedValues[i] = nodeValues[i];
        }

        // Begin with leaf nodes which have exactly one connection
        Queue<Integer> leafQueue = new LinkedList<>();
        for (int vertex = 0; vertex < vertices; vertex++) {
            if (degrees[vertex] == 1) {
                leafQueue.offer(vertex);
            }
        }

        while (!leafQueue.isEmpty()) {
            int currentVertex = leafQueue.poll();
            degrees[currentVertex]--;

            long accumulatedValue = 0;

            // Check divisibility condition
            if (extendedValues[currentVertex] % divisor == 0) {
                validCount++;
            } else {
                accumulatedValue = extendedValues[currentVertex];
            }

            // Update neighboring vertices
            for (int neighbor : adjacencyList.get(currentVertex)) {
                if (degrees[neighbor] == 0) {
                    continue;
                }

                degrees[neighbor]--;
                extendedValues[neighbor] += accumulatedValue;

                // Enqueue the new leaf nodes
                if (degrees[neighbor] == 1) {
                    leafQueue.offer(neighbor);
                }
            }
        }

        return validCount;
    }
}

class Solution:
    def countComponentsDivisibleByK(
        self, num_nodes: int, connections: List[List[int]], node_values: List[int], divisor: int
    ) -> int:
        if num_nodes < 2:
            return 1
        total_count = 0
        connectivity = defaultdict(list)
        node_degrees = [0] * num_nodes

        # Construct the graph and tally node degrees
        for start, end in connections:
            connectivity[start].append(end)
            connectivity[end].append(start)
            node_degrees[start] += 1
            node_degrees[end] += 1

        # Use deque to handle nodes with a single connection
        leaf_nodes = deque(i for i in range(num_nodes) if node_degrees[i] == 1)

        while leaf_nodes:
            current = leaf_nodes.popleft()
            node_degrees[current] -= 1
            temp_value = 0

            # Check divisibility by divisor
            if node_values[current] % divisor == 0:
                total_count += 1
            else:
                temp_value = node_values[current]

            # Adjust values for adjacent nodes
            for adjacent in connectivity[current]:
                if node_degrees[adjacent] == 0:
                    continue
                node_degrees[adjacent] -= 1
                node_values[adjacent] += temp_value

                # Enqueue nodes with updated degree of one
                if node_degrees[adjacent] == 1:
                    leaf_nodes.append(adjacent)

        return total_count