# Count the Number of Complete Components
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-the-number-of-complete-components)
Canonical: https://scaleengineer.com/dsa/problems/count-the-number-of-complete-components
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Graph
---
## Problem
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:**

**![](https://assets.glich.co/dsa/count-the-number-of-complete-components/image0.png)**

**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:**

**![](https://assets.glich.co/dsa/count-the-number-of-complete-components/image1.png)**

**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
## Brute-Force Check on Components using Adjacency Matrix
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.
**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.
**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`.
### Explanation
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.

```java
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;
    }
}
```
### 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.

## Efficient Check using Vertex/Edge Counting with DFS/BFS
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.
**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.
**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.
### Explanation
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.

1.  **Build Adjacency List:** Construct an adjacency list from the `edges` array. This takes `O(V + E)` time and space.

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

3.  **Check and Count:** For each component, we check if `edgesCount == nodesCount * (nodesCount - 1) / 2`. If they match, we increment our result counter.

```java
class Solution {
    List<List<Integer>> adj;
    boolean[] visited;

    public int countCompleteComponents(int n, int[][] edges) {
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        visited = new boolean[n];
        int completeComponents = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                List<Integer> componentNodes = new ArrayList<>();
                dfs(i, componentNodes);
                
                int nodesCount = componentNodes.size();
                int edgesCount = 0;
                for (int node : componentNodes) {
                    edgesCount += adj.get(node).size();
                }
                edgesCount /= 2;

                if (edgesCount == (long)nodesCount * (nodesCount - 1) / 2) {
                    completeComponents++;
                }
            }
        }
        return completeComponents;
    }

    private void dfs(int u, List<Integer> componentNodes) {
        visited[u] = true;
        componentNodes.add(u);
        for (int v : adj.get(u)) {
            if (!visited[v]) {
                dfs(v, componentNodes);
            }
        }
    }
}
```
### 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.

## Optimal Approach using Disjoint Set Union (DSU)
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.
**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.
**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.
### Explanation
This approach leverages the efficiency of the DSU data structure for finding connected components.

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

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

3.  **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.

```java
class DSU {
    int[] parent;
    int[] size;

    public DSU(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    public int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }

    public void union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            if (size[rootI] < size[rootJ]) {
                int temp = rootI;
                rootI = rootJ;
                rootJ = temp;
            }
            parent[rootJ] = rootI;
            size[rootI] += size[rootJ];
        }
    }
}

class Solution {
    public int countCompleteComponents(int n, int[][] edges) {
        DSU dsu = new DSU(n);
        for (int[] edge : edges) {
            dsu.union(edge[0], edge[1]);
        }

        Map<Integer, Integer> edgeCounts = new HashMap<>();
        for (int[] edge : edges) {
            int root = dsu.find(edge[0]);
            edgeCounts.put(root, edgeCounts.getOrDefault(root, 0) + 1);
        }

        int completeComponents = 0;
        for (int i = 0; i < n; i++) {
            if (dsu.parent[i] == i) { // It's a root of a component
                long nodes = dsu.size[i];
                long numEdges = edgeCounts.getOrDefault(i, 0);
                if (numEdges == nodes * (nodes - 1) / 2) {
                    completeComponents++;
                }
            }
        }
        return completeComponents;
    }
}
```
### 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.

# Solutions
### Java

```java
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};
  }
}

```

### CPP

```cpp
class Solution {
public:
  int countCompleteComponents(int n, vector<vector<int>> &edges) {
    vector<vector<int>> g(n);
    bool vis[n];
    memset(vis, false, sizeof(vis));
    for (auto &e : edges) {
      int a = e[0], b = e[1];
      g[a].push_back(b);
      g[b].push_back(a);
    }
    function<pair<int, int>(int)> dfs = [&](int i) -> pair<int, int> {
      vis[i] = true;
      int x = 1, y = g[i].size();
      for (int j : g[i]) {
        if (!vis[j]) {
          auto [a, b] = dfs(j);
          x += a;
          y += b;
        }
      }
      return make_pair(x, y);
    };
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      if (!vis[i]) {
        auto [a, b] = dfs(i);
        if (a * (a - 1) == b) {
          ++ans;
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    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

```