Leetcode 2685. Count the Number of Complete Components

Jimmy   Mar 22, 2025   1245 words   ~30 mins
#Depth-First Search #Breadth-First Search #Union Find #Graph

Table of Contents

Problem Informations

Problem Description

You are given an integer $n$. There is an undirected graph with $n$ vertices, numbered from $0$ to $n - 1$. You are given a 2D integer array edges where $edges[i] = [a_i, b_i]$ denotes that there exists an undirected edge connecting vertices $a_i$ and $b_i$.

Return the number of complete connected components of the graph.

A connected component is a subgraph of a graph in which there exists a path between any two vertices, and no vertex of the subgraph shares an edge with a vertex outside of the subgraph.

A connected component is said to be complete if there exists an edge between every pair of its vertices.

Example 1:

Input: n = 6, edges = [[0,1],[0,2],[1,2],[3,4]]
Output: 3
Explanation: From the picture above, one can see that all of the components of this graph are complete.

Example 2:

Input: n = 6, edges = [[0,1],[0,2],[1,2],[3,4],[3,5]]
Output: 1
Explanation: The component containing vertices 0, 1, and 2 is complete since there is an edge between every pair of two vertices. On the other hand, the component containing vertices 3, 4, and 5 is not complete since there is no edge between vertices 4 and 5. Thus, the number of complete components in this graph is 1.

Constraints:

  • $1 \leq n \leq 50$
  • $0 \leq edges.length \leq n \times (n - 1) / 2$
  • $edges[i].length == 2$
  • $0 \leq a_i, b_i \leq n - 1$
  • $a_i \neq b_i$
  • There are no repeated edges.

Intuition

The problem requires identifying the number of complete connected components in an undirected graph. A complete connected component is a subgraph where each pair of distinct vertices is connected by a unique edge, forming a clique. Initially, we need to determine connected components in the graph, and then validate if each connected component forms a complete subgraph.

Approach

To solve the problem, we utilize the Union-Find data structure, also known as Disjoint Set Union (DSU), which efficiently handles the union and find operations needed to group vertices into connected components.

  1. Initialization:

    • Create three arrays: group, edgeCount, and nodeCount.
      • group[i] represents the group leader or the “parent node” of node i.
      • edgeCount[i] stores the count of edges within the connected component whose leader is i.
      • nodeCount[i] keeps track of the number of nodes within the connected component whose leader is i.

  2. Setup:

    • Initialize each node as its own separate group: group[i] = i.
    • Initialize edgeCount[i] = 0 for all i.
    • Initialize nodeCount[i] = 1 for all i as each node initially is its own component.

  3. Union-Find Operations:

    • For every edge [a_i, b_i], perform union operations to group connected nodes.
    • Use the findGroup function for path compression to find the root of each node, improving efficiency.
    • In unionGroup, if two nodes i and j are in different groups, unite them under one leader and merge their edge counts and node counts.
    • Increment the edge count for each union operation since we’ve added an edge between nodes.

  4. Path Compression:

    • For all nodes, apply findGroup to update each node directly pointing to its root leader, helping avoid redundant checks with respect to component connectivity.

  5. Component Count and Verification:

    • Remove duplicate entries in the group array to find all unique connected components.
    • For each unique component, verify if it is complete by checking the formula: $\text{nodeCount}[el] \times (\text{nodeCount}[el] - 1) / 2 = \text{edgeCount}[el]$. If true, this indicates a complete subgraph.

  6. Return Count:

    • Return the number of complete connected components, which is the count of groups satisfying the completeness condition stipulated by the formula.

This approach effectively identifies all connected components in the graph and uses combinatorial logic to determine if they form complete subgraphs, leveraging the power of Union-Find for efficient connectivity checks.

Code

C++

class Solution {
public:
    // Function to find the root of the group to which 'i' belongs
    int findGroup(vector<int>& group, int i) {
        if (group[i] == i) 
            return i;
        else
            // Path compression for efficiency
            return group[i] = findGroup(group, group[i]);
    }

    // Function to union two groups identified by i and j
    void unionGroup(vector<int>& group, vector<int>& edgeCount, vector<int>& nodeCount, int i, int j) {
        int groupI = findGroup(group, i);
        int groupJ = findGroup(group, j);

        // If they belong to different groups, merge them
        if (groupI != groupJ) {
            group[groupJ] = groupI;
            edgeCount[groupI] += edgeCount[groupJ];
            nodeCount[groupI] += nodeCount[groupJ];
        }
        // Increment edge count for the unified group
        edgeCount[groupI]++;
    }

    // Function to count the number of complete connected components
    int countCompleteComponents(int n, vector<vector<int>>& edges) {
        vector<int> group(n), edgeCount(n, 0), nodeCount(n, 1);

        // Initialize each node as its own group
        for (int i = 0; i < n; i++) 
            group[i] = i;

        // Union operation for each edge
        for (vector<int>& edge : edges) 
            unionGroup(group, edgeCount, nodeCount, edge[0], edge[1]);

        // Ensure all nodes point directly to their root group (compress paths)
        for (int i = 0; i < n; i++) 
            findGroup(group, i);

        // Remove duplicates to count unique groups
        sort(group.begin(), group.end());
        auto lastUnique = unique(group.begin(), group.end());
        group.erase(lastUnique, group.end());

        int completeComponentsCount = 0;
        // Check each group if it forms a complete component
        for (int el : group) {
            // A component is complete if it has the full complement of edges
            if (nodeCount[el] * (nodeCount[el] - 1) / 2 == edgeCount[el]) 
                completeComponentsCount++;
        }

        return completeComponentsCount;
    }
};

Python

class Solution:
    # Function to find the root of the group to which 'i' belongs
    def findGroup(self, group, i):
        if group[i] == i:
            return i
        else:
            # Path compression for efficiency
            group[i] = self.findGroup(group, group[i])
            return group[i]

    # Function to union two groups identified by i and j
    def unionGroup(self, group, edgeCount, nodeCount, i, j):
        groupI = self.findGroup(group, i)
        groupJ = self.findGroup(group, j)

        # If they belong to different groups, merge them
        if groupI != groupJ:
            group[groupJ] = groupI
            edgeCount[groupI] += edgeCount[groupJ]
            nodeCount[groupI] += nodeCount[groupJ]
        # Increment edge count for the unified group
        edgeCount[groupI] += 1

    # Function to count the number of complete connected components
    def countCompleteComponents(self, n, edges):
        group = list(range(n))
        edgeCount = [0] * n
        nodeCount = [1] * n

        # Initialize each node as its own group
        for i in range(n):
            group[i] = i

        # Union operation for each edge
        for edge in edges:
            self.unionGroup(group, edgeCount, nodeCount, edge[0], edge[1])

        # Ensure all nodes point directly to their root group (compress paths)
        for i in range(n):
            self.findGroup(group, i)

        # Remove duplicates to count unique groups
        group.sort()
        group = list(dict.fromkeys(group))

        completeComponentsCount = 0
        # Check each group if it forms a complete component
        for el in group:
            # A component is complete if it has the full complement of edges
            if nodeCount[el] * (nodeCount[el] - 1) // 2 == edgeCount[el]:
                completeComponentsCount += 1

        return completeComponentsCount

Complexity

  • Time complexity: The algorithm consists of multiple distinct phases which collectively determine the time complexity. First, initializing the group, edgeCount, and nodeCount arrays each take $O(n)$. The union operations for the edges also take $O(n)$ in total due to path compression and union by rank optimizations. The path compression loop ensures each node is pointing to the correct representative, taking $O(n)$ as well. Sorting the group array takes $O(n \log n)$. Finally, scanning through the groups to count complete components takes $O(n)$. Hence, the overall time complexity is $O(n \log n)$ due to the sorting of the group array.

  • Space complexity: The space complexity is determined by the arrays group, edgeCount, and nodeCount, each requiring $O(n)$ space. Therefore, the space complexity is $O(n)$.

Disclaimer: All reference materials on this website are sourced from the internet and are intended for learning purposes only. If you believe any content infringes upon your rights, please contact me at csnote.cc@gmail.com, and I will remove the relevant content promptly.


Feedback Welcome: If you notice any errors or areas for improvement in the articles, I warmly welcome your feedback and corrections. Your input will help this blog provide better learning resources. This is an ongoing process of learning and improvement, and your suggestions are valuable to me. You can reach me at csnote.cc@gmail.com.