Scale Engineer

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 SearchBreadth-First SearchUnion 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] = [ai, bi] denotes that there exists an undirected edge connecting vertices ai and bi.

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 <= ai, bi <= n - 1
  • ai != bi
  • 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:

  1. 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.

  2. 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.

  3. Count: If a component is verified to be complete, we increment a counter. This process is repeated for all components in the graph.

class Solution {    boolean[][] adj;    boolean[] visited;     public int countCompleteComponents(int n, int[][] edges) {        adj = new boolean[n][n];        for (int[] edge : edges) {            adj[edge[0]][edge[1]] = true;            adj[edge[1]][edge[0]] = true;        }         visited = new boolean[n];        int completeComponents = 0;         for (int i = 0; i < n; i++) {            if (!visited[i]) {                List<Integer> component = new ArrayList<>();                dfs(i, component, n);                if (isComplete(component)) {                    completeComponents++;                }            }        }        return completeComponents;    }     private void dfs(int u, List<Integer> component, int n) {        visited[u] = true;        component.add(u);        for (int v = 0; v < n; v++) {            if (adj[u][v] && !visited[v]) {                dfs(v, component, n);            }        }    }     private boolean isComplete(List<Integer> component) {        int numNodes = component.size();        for (int i = 0; i < numNodes; i++) {            for (int j = i + 1; j < numNodes; j++) {                int u = component.get(i);                int v = component.get(j);                if (!adj[u][v]) {                    return false;                }            }        }        return true;    }}

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.

Solutions

class Solution {private  List<Integer>[] g;private  boolean[] vis;public  int countCompleteComponents(int n, int[][] edges) {    g = new List[n];    vis = new boolean[n];    Arrays.setAll(g, k->new ArrayList<>());    for (int[] e : edges) {      int a = e[0], b = e[1];      g[a].add(b);      g[b].add(a);    }    int ans = 0;    for (int i = 0; i < n; ++i) {      if (!vis[i]) {        int[] t = dfs(i);        if (t[0] * (t[0] - 1) == t[1]) {          ++ans;        }      }    }    return ans;  }private  int[] dfs(int i) {    vis[i] = true;    int x = 1, y = g[i].size();    for (int j : g[i]) {      if (!vis[j]) {        int[] t = dfs(j);        x += t[0];        y += t[1];      }    }    return new int[]{x, y};  }}

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 →

Next problem