Count the Number of Complete Components

Med

#2434Time: O(n^2) - Building the adjacency matrix takes `O(n^2)`. The traversal over the entire graph takes `O(n^2)` with an adjacency matrix. The completeness check for a component of size `k` takes `O(k^2)`, leading to a total time complexity dominated by `O(n^2)` factors.Space: O(n^2) - The primary space cost is the `n x n` adjacency matrix. The `visited` array and recursion stack take `O(n)` space.

Algorithms

Depth-First Search Breadth-First Search Union Find

Data structures

Graph

Prompt

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 <= n <= 50
0 <= edges.length <= n * (n - 1) / 2
edges[i].length == 2
0 <= a_i, b_i <= n - 1
a_i != b_i
There are no repeated edges.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach first identifies the connected components of the graph using a standard traversal algorithm like Depth-First Search (DFS). For each component found, it then performs a brute-force check to see if it's complete. An adjacency matrix is used to represent the graph, which simplifies checking for an edge between two vertices but requires significant space.

Algorithm

Graph Representation: Create an n x n adjacency matrix adj. For each edge [u, v] in the input, set adj[u][v] and adj[v][u] to true.
Component Identification: Use a visited array to keep track of processed vertices. Iterate from i = 0 to n-1. If i is not visited, it marks the beginning of a new connected component.
Traversal: Start a Depth-First Search (DFS) or Breadth-First Search (BFS) from i. During the traversal, collect all vertices of the component into a list and mark them as visited.
Completeness Check: Once a component is identified, iterate through every pair of distinct vertices (u, v) within that component. Use the adjacency matrix to check if an edge exists between them (adj[u][v]). If any edge is found to be missing, the component is not complete.
Counting: If all pairs of vertices in a component are connected, increment a counter for complete components.
Repeat: Continue this process until all vertices in the graph have been visited.

Walkthrough

The method involves three main steps:

Build Adjacency Matrix: An n x n matrix adj is initialized. We iterate through the edges array, and for each edge [u, v], we set adj[u][v] = true and adj[v][u] = true. This provides O(1) lookup for the existence of an edge.
Find Components and Check Completeness: We iterate through each vertex of the graph. If a vertex hasn't been visited, we start a traversal (like DFS) to find all nodes in its connected component. These nodes are stored in a temporary list. After the traversal for a component is complete, we check if it's a complete graph. This is done by iterating through all unique pairs of nodes in our list and verifying that an edge exists between them using the adjacency matrix.
Count: If a component is verified to be complete, we increment a counter. This process is repeated for all components in the graph.

1class Solution {2    boolean[][] adj;3    boolean[] visited;4 5    public int countCompleteComponents(int n, int[][] edges) {6        adj = new boolean[n][n];7        for (int[] edge : edges) {8            adj[edge[0]][edge[1]] = true;9            adj[edge[1]][edge[0]] = true;10        }11 12        visited = new boolean[n];13        int completeComponents = 0;14 15        for (int i = 0; i < n; i++) {16            if (!visited[i]) {17                List<Integer> component = new ArrayList<>();18                dfs(i, component, n);19                if (isComplete(component)) {20                    completeComponents++;21                }22            }23        }24        return completeComponents;25    }26 27    private void dfs(int u, List<Integer> component, int n) {28        visited[u] = true;29        component.add(u);30        for (int v = 0; v < n; v++) {31            if (adj[u][v] && !visited[v]) {32                dfs(v, component, n);33            }34        }35    }36 37    private boolean isComplete(List<Integer> component) {38        int numNodes = component.size();39        for (int i = 0; i < numNodes; i++) {40            for (int j = i + 1; j < numNodes; j++) {41                int u = component.get(i);42                int v = component.get(j);43                if (!adj[u][v]) {44                    return false;45                }46            }47        }48        return true;49    }50}

Complexity

Time

O(n^2) - Building the adjacency matrix takes `O(n^2)`. The traversal over the entire graph takes `O(n^2)` with an adjacency matrix. The completeness check for a component of size `k` takes `O(k^2)`, leading to a total time complexity dominated by `O(n^2)` factors.

Space

O(n^2) - The primary space cost is the `n x n` adjacency matrix. The `visited` array and recursion stack take `O(n)` space.

Trade-offs

Pros

The logic is straightforward, especially the completeness check with an adjacency matrix.

Cons

Inefficient in both time and space, with complexities of O(n^2).
Particularly slow for sparse graphs where the number of edges E is much less than n^2.

This approach improves upon the previous one by using an adjacency list for graph representation and a more clever method for the completeness check. Instead of checking every pair of vertices, it simply counts the number of vertices and edges in each component. A component is complete if its edge count matches the expected number of edges in a complete graph of its size.

Algorithm

Graph Representation: Build an adjacency list, which is a more space-efficient representation for graphs, especially sparse ones. Each vertex maps to a list of its neighbors.
Component Identification: Use a visited array and iterate through all vertices. If a vertex i is unvisited, start a traversal (DFS or BFS) to find its connected component.
Vertex and Edge Counting: During the traversal of a single component, keep track of the nodes belonging to it. After the traversal identifies all V_c nodes in the component, calculate the number of edges E_c within it. This can be done by summing the degrees (size of adjacency lists) of all nodes in the component and dividing by 2.
Completeness Formula: A component is complete if the number of its edges E_c is equal to V_c * (V_c - 1) / 2.
Counting: If the formula holds true, increment the count of complete components.

Walkthrough

The core idea is to efficiently verify the completeness of a component. A complete graph with V vertices must have exactly E = V * (V - 1) / 2 edges.

Build Adjacency List: Construct an adjacency list from the edges array. This takes O(V + E) time and space.
Traverse and Count: Iterate through each vertex. If a vertex is unvisited, perform a traversal (DFS or BFS) to find all nodes in its connected component. During this process, we can count the number of vertices (nodesCount). After identifying all nodes in the component, we can find the number of edges (edgesCount) by summing their degrees (the size of their adjacency lists) and dividing by two, since each edge contributes to the degree of two vertices.
Check and Count: For each component, we check if edgesCount == nodesCount * (nodesCount - 1) / 2. If they match, we increment our result counter.

1class Solution {2    List<List<Integer>> adj;3    boolean[] visited;4 5    public int countCompleteComponents(int n, int[][] edges) {6        adj = new ArrayList<>();7        for (int i = 0; i < n; i++) {8            adj.add(new ArrayList<>());9        }10        for (int[] edge : edges) {11            adj.get(edge[0]).add(edge[1]);12            adj.get(edge[1]).add(edge[0]);13        }14 15        visited = new boolean[n];16        int completeComponents = 0;17 18        for (int i = 0; i < n; i++) {19            if (!visited[i]) {20                List<Integer> componentNodes = new ArrayList<>();21                dfs(i, componentNodes);22                23                int nodesCount = componentNodes.size();24                int edgesCount = 0;25                for (int node : componentNodes) {26                    edgesCount += adj.get(node).size();27                }28                edgesCount /= 2;29 30                if (edgesCount == (long)nodesCount * (nodesCount - 1) / 2) {31                    completeComponents++;32                }33            }34        }35        return completeComponents;36    }37 38    private void dfs(int u, List<Integer> componentNodes) {39        visited[u] = true;40        componentNodes.add(u);41        for (int v : adj.get(u)) {42            if (!visited[v]) {43                dfs(v, componentNodes);44            }45        }46    }47}

Complexity

Time

O(V + E) - Building the adjacency list is `O(V + E)`. The traversals and calculations visit each vertex and edge a constant number of times in total, resulting in `O(V + E)` complexity.

Space

O(V + E) - The adjacency list requires `O(V + E)` space. The `visited` array and recursion stack require `O(V)` space.

Trade-offs

Pros

Efficient time complexity of O(V + E).
Much better space complexity than the adjacency matrix approach for sparse graphs.

Cons

The space complexity of O(V + E) can be suboptimal if the number of edges E is large.

This is the most optimized approach, particularly in terms of space. It uses a Disjoint Set Union (DSU) data structure, also known as Union-Find, to efficiently determine the connected components. By augmenting the DSU to also track the number of vertices and edges within each set, we can check for completeness with optimal space usage.

Algorithm

DSU Initialization: Initialize a Disjoint Set Union (DSU) data structure with n elements, one for each vertex. Each vertex starts in its own set.
Component Formation: Iterate through the edges array. For each edge (u, v), perform a union(u, v) operation. This merges the sets containing u and v, effectively grouping all connected vertices into the same set.
Count Vertices and Edges: After all edges are processed, the DSU structure represents the connected components. We need to find the number of vertices and edges in each.
- The number of vertices in each component can be tracked during the union operations (union-by-size) or found by iterating through all nodes and grouping them by their root.
- The number of edges in each component can be found by iterating through the edges array again and, for each edge, incrementing a counter associated with the component's root.
Final Check: Iterate through each component (represented by its root in the DSU). Use the pre-calculated vertex and edge counts to check if edges == nodes * (nodes - 1) / 2. If so, increment the result.

Walkthrough

This approach leverages the efficiency of the DSU data structure for finding connected components.

Union-Find: We first use the DSU to group all vertices into components. We initialize a DSU structure with n sets. For every edge [u, v], we call union(u, v). We use the union-by-size optimization to keep track of the number of nodes in each component.
Edge Counting: After forming the components, we need to count the edges within each. We can use a hash map where keys are the root of each component and values are the edge counts. We iterate through the edges array one more time. For each edge, we find the root of its component using find() and increment the corresponding counter in the map.
Completeness Check: Finally, we iterate from 0 to n-1. If a vertex i is the root of its component (parent[i] == i), we retrieve its size (number of nodes) from the DSU and its edge count from our map. We then apply the completeness formula edges == nodes * (nodes - 1) / 2 to check if it's a complete component and update our final count.

1class DSU {2    int[] parent;3    int[] size;4 5    public DSU(int n) {6        parent = new int[n];7        size = new int[n];8        for (int i = 0; i < n; i++) {9            parent[i] = i;10            size[i] = 1;11        }12    }13 14    public int find(int i) {15        if (parent[i] == i) return i;16        return parent[i] = find(parent[i]);17    }18 19    public void union(int i, int j) {20        int rootI = find(i);21        int rootJ = find(j);22        if (rootI != rootJ) {23            if (size[rootI] < size[rootJ]) {24                int temp = rootI;25                rootI = rootJ;26                rootJ = temp;27            }28            parent[rootJ] = rootI;29            size[rootI] += size[rootJ];30        }31    }32}33 34class Solution {35    public int countCompleteComponents(int n, int[][] edges) {36        DSU dsu = new DSU(n);37        for (int[] edge : edges) {38            dsu.union(edge[0], edge[1]);39        }40 41        Map<Integer, Integer> edgeCounts = new HashMap<>();42        for (int[] edge : edges) {43            int root = dsu.find(edge[0]);44            edgeCounts.put(root, edgeCounts.getOrDefault(root, 0) + 1);45        }46 47        int completeComponents = 0;48        for (int i = 0; i < n; i++) {49            if (dsu.parent[i] == i) { // It's a root of a component50                long nodes = dsu.size[i];51                long numEdges = edgeCounts.getOrDefault(i, 0);52                if (numEdges == nodes * (nodes - 1) / 2) {53                    completeComponents++;54                }55            }56        }57        return completeComponents;58    }59}

Complexity

Time

O(V + E * α(V)) - where `α(V)` is the extremely slow-growing inverse Ackermann function, making the complexity nearly linear in `V + E`. This comes from the DSU operations.

Space

O(V) - The DSU structure requires `O(V)` space for its parent and size arrays. The map for edge counts also uses at most `O(V)` space.

Trade-offs

Pros

Most optimal space complexity at O(V).
Excellent time complexity, nearly linear.
Very efficient for problems involving connected components.

Cons

The implementation can be slightly more complex than a standard DFS/BFS approach.

Solutions

Solution

1class Solution {2private3  List<Integer>[] g;4private5  boolean[] vis;6public7  int countCompleteComponents(int n, int[][] edges) {8    g = new List[n];9    vis = new boolean[n];10    Arrays.setAll(g, k->new ArrayList<>());11    for (int[] e : edges) {12      int a = e[0], b = e[1];13      g[a].add(b);14      g[b].add(a);15    }16    int ans = 0;17    for (int i = 0; i < n; ++i) {18      if (!vis[i]) {19        int[] t = dfs(i);20        if (t[0] * (t[0] - 1) == t[1]) {21          ++ans;22        }23      }24    }25    return ans;26  }27private28  int[] dfs(int i) {29    vis[i] = true;30    int x = 1, y = g[i].size();31    for (int j : g[i]) {32      if (!vis[j]) {33        int[] t = dfs(j);34        x += t[0];35        y += t[1];36      }37    }38    return new int[]{x, y};39  }40}

1class Solution {2public:3  int countCompleteComponents(int n, vector<vector<int>> &edges) {4    vector<vector<int>> g(n);5    bool vis[n];6    memset(vis, false, sizeof(vis));7    for (auto &e : edges) {8      int a = e[0], b = e[1];9      g[a].push_back(b);10      g[b].push_back(a);11    }12    function<pair<int, int>(int)> dfs = [&](int i) -> pair<int, int> {13      vis[i] = true;14      int x = 1, y = g[i].size();15      for (int j : g[i]) {16        if (!vis[j]) {17          auto [a, b] = dfs(j);18          x += a;19          y += b;20        }21      }22      return make_pair(x, y);23    };24    int ans = 0;25    for (int i = 0; i < n; ++i) {26      if (!vis[i]) {27        auto [a, b] = dfs(i);28        if (a * (a - 1) == b) {29          ++ans;30        }31      }32    }33    return ans;34  }35};

1class Solution:2    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int: def dfs(i: int) -> (int, int): vis[i] = True x, y = 1, len(g[i]) for j in g[i]: if not vis[j]: a, b = dfs(j) x += a y += b return x, y g = defaultdict(list) for a, b in edges: g[a]. append(b) g[b]. append(a) vis = [False] * n ans = 0 for i in range(n): if not vis[i]: a, b = dfs(i) ans += a * (a - 1) == b return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution {2private3  List<Integer>[] g;4private5  boolean[] vis;6public7  int countCompleteComponents(int n, int[][] edges) {8    g = new List[n];9    vis = new boolean[n];10    Arrays.setAll(g, k->new ArrayList<>());11    for (int[] e : edges) {12      int a = e[0], b = e[1];13      g[a].add(b);14      g[b].add(a);15    }16    int ans = 0;17    for (int i = 0; i < n; ++i) {18      if (!vis[i]) {19        int[] t = dfs(i);20        if (t[0] * (t[0] - 1) == t[1]) {21          ++ans;22        }23      }24    }25    return ans;26  }27private28  int[] dfs(int i) {29    vis[i] = true;30    int x = 1, y = g[i].size();31    for (int j : g[i]) {32      if (!vis[j]) {33        int[] t = dfs(j);34        x += t[0];35        y += t[1];36      }37    }38    return new int[]{x, y};39  }40}

1class Solution {2public:3  int countCompleteComponents(int n, vector<vector<int>> &edges) {4    vector<vector<int>> g(n);5    bool vis[n];6    memset(vis, false, sizeof(vis));7    for (auto &e : edges) {8      int a = e[0], b = e[1];9      g[a].push_back(b);10      g[b].push_back(a);11    }12    function<pair<int, int>(int)> dfs = [&](int i) -> pair<int, int> {13      vis[i] = true;14      int x = 1, y = g[i].size();15      for (int j : g[i]) {16        if (!vis[j]) {17          auto [a, b] = dfs(j);18          x += a;19          y += b;20        }21      }22      return make_pair(x, y);23    };24    int ans = 0;25    for (int i = 0; i < n; ++i) {26      if (!vis[i]) {27        auto [a, b] = dfs(i);28        if (a * (a - 1) == b) {29          ++ans;30        }31      }32    }33    return ans;34  }35};

1class Solution:2    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int: def dfs(i: int) -> (int, int): vis[i] = True x, y = 1, len(g[i]) for j in g[i]: if not vis[j]: a, b = dfs(j) x += a y += b return x, y g = defaultdict(list) for a, b in edges: g[a]. append(b) g[b]. append(a) vis = [False] * n ans = 0 for i in range(n): if not vis[i]: a, b = dfs(i) ans += a * (a - 1) == b return ans

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.