2685. Count the Number of Complete Components


Problem Description

You are tasked with finding the number of complete connected components in an undirected graph. The graph has n vertices, each identified by a unique number from 0 to n - 1. An array edges contains pairs of integer indices representing the edges that connect vertices in the graph.

A connected component is a set of vertices in which each pair of vertices is connected by some path. Importantly, no vertex in a connected component connects to any vertex outside that component in the graph.

A complete connected component (also known as a clique) is a special kind of connected component where there is a direct edge between every pair of nodes within the component.

So, the objective is to count how many complete connected components there are in the given graph.

Intuition

To solve this problem, we can use Depth-First Search (DFS). DFS allows us to explore each vertex and its neighbors recursively. The solution employs DFS to count vertices (x) and edges (y) in each connected component. Since a complete graph with n vertices should have exactly n * (n - 1) / 2 edges, this fact can be used to verify if a connected component is complete.

Here's how the algorithm works step by step:

  1. Create a graph representation using a list where each index represents a node and the values are lists of connected nodes.
  2. Initialize a list of boolean values to track visited nodes during DFS to ensure nodes are not counted more than once.
  3. Iterate through each node. If a node is unvisited, perform DFS starting from that node to determine the size of the connected component.
  4. During DFS, count the number of nodes (x) and the number of edges (y). Note that since the graph is undirected, each edge will be counted twice - once for each endpoint.
  5. After each DFS call, check if the number of edges matches the formula x * (x - 1) (which is double x * (x - 1) / 2 since each edge is counted twice). If it does, then we have found a complete connected component.
  6. Increment a counter for complete connected components any time the check in step 5 passes.
  7. After completing the iteration through all nodes, return the counter value.

This solution is efficient because it only requires a single pass through the graph, using DFS to explore the connected components and immediately checking which ones are complete.

Learn more about Depth-First Search, Breadth-First Search and Graph patterns.

Solution Approach

The solution uses the following algorithms, data structures, and patterns:

Depth-First Search (DFS): This algorithm allows us to explore all nodes in a connected component of the graph. We define a recursive dfs function that takes a starting vertex i and explores every connected vertex, returning the total count of vertices and edges in the connected component.

Adjacency List: The graph is represented as an adjacency list using a defaultdict(list) from Python's collections library. This data structure is efficient for storing sparse graphs and allows us to quickly access all neighbors of a graph node.

Visited List: To keep track of which nodes have been visited during the DFS exploration, we maintain a list vis of boolean values. this avoids counting the same node more than once and ensures we don't enter into an infinite loop by revisiting the same nodes.

Here's how the implementation follows the algorithm:

  1. Initialize the graph as an adjacency list (g) from the edges array, where for each edge [a, b] we add b to the list of adjacent vertices of a and vice versa since the graph is undirected.

  2. Create a visited list vis of boolean values, initialized to False, to mark vertices as visited.

  3. For each vertex i from 0 to n-1, check if it has not been visited:

    • If not visited, call the dfs function on vertex i. This will traverse all vertices in the same connected component as i, marking them as visited and counting the vertices and edges.
    • The dfs function works as follows:
      • Mark the current vertex i as visited.
      • Initialize local variables x (vertex count) to 1 and y (edge count) to the length of the adjacency list at i since every adjacent vertex represents an edge.
      • Iterate over each neighbor j of vertex i. If j is not visited, call dfs recursively and update x and y with the counts from the component connected through j.
      • Return the count of vertices x and the double count of edges y.
  4. After the recursive DFS, compare the number of vertices a and the double count of edges b using the formula a * (a - 1). A complete component must have exactly a * (a - 1) / 2 edges, but since each edge is counted twice, we check for a * (a - 1) without dividing by 2. If the component is complete, increment the ans.

  5. Finally, when all vertices are processed, return ans, which represents the count of complete connected components.

The solution effectively utilizes the dfs function for graph traversal and the combinatorial property of complete graphs to detect complete connected components in a single scan.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's assume we have n = 5 vertices, and we are given the following edges array, which defines an undirected graph:

1edges = [[0, 1], [1, 2], [3, 4]]

The graph can be visualized as two separate connected components:

10 -- 1 -- 2
2
33 -- 4

Here's a step-by-step illustration of applying the solution approach:

  1. First, we create an adjacency list g for the given graph. This list will look like:
1g = {
2  0: [1],
3  1: [0, 2],
4  2: [1],
5  3: [4],
6  4: [3]
7}
  1. We initialize a visited list vis = [False, False, False, False, False] to keep track of visited nodes.

  2. We start iterating through each vertex. When iterating over vertex 0, since it's not visited, we call the dfs function.

  3. The dfs function now starts on 0, marking it as visited (vis[0] = True) and setting x = 1 and y = len(g[0]) = 1.

  4. Within DFS on vertex 0, we move to its neighbor 1 which is unvisited, and call DFS on 1, marking it visited and adding its own vertices and edges. We get x = 2 and y = 3 (since it's connected to 0 and 2).

  5. Continuing the DFS, we visit vertex 2. No new vertices are discovered, but this adds to the edge count: y += len(g[2]) = 1.

  6. The DFS call on vertex 0 ends, returning x = 3 and y = 4.

  7. We then check if x * (x - 1) == y which would mean it's a complete connected component. 3 * (3 - 1) = 6 which does not equal 4, so this component is not complete.

  8. We update the visited list for all vertices in the connected component containing 0, 1, and 2.

  9. We continue the iteration to vertex 3, calling DFS since it's not visited.

  10. Similar to the previous DFS, we mark 3 as visited, setting x = 1 and y = len(g[3]) = 1 since it's connected to 4.

  11. On visiting neighbor 4, we update x = 2 and y = 2.

  12. After the DFS on 3, we check if x * (x - 1) == y. 2 * (2 - 1) = 2 which equals y, so this is indeed a complete connected component.

  13. We add 1 to our complete connected component count ans.

  14. Finally, after checking all vertices, we find that there is 1 complete connected component in the graph.

In conclusion, after traversing this example graph, our algorithm would correctly report that there is 1 complete connected component.

Solution Implementation

1from collections import defaultdict
2
3class Solution:
4    def countCompleteComponents(self, n: int, edges: List[List[int]]) -> int:
5        # dfs function to traverse the graph and return the number
6        # of nodes (vertex_count) and number of edges (edge_count) in the component.
7        def dfs(vertex: int) -> (int, int):
8            visited[vertex] = True
9            vertex_count, edge_count = 1, len(graph[vertex])  # Initialize counts with current node counts
10            for neighbor in graph[vertex]:
11                if not visited[neighbor]:
12                    additional_vertices, additional_edges = dfs(neighbor)
13                    vertex_count += additional_vertices
14                    edge_count += additional_edges
15            return vertex_count, edge_count
16
17        # build the graph from the edges list
18        graph = defaultdict(list)
19        for a, b in edges:
20            graph[a].append(b)
21            graph[b].append(a)
22          
23        visited = [False] * n  # keep track of visited nodes
24        complete_components_count = 0  # counter for complete components
25      
26        # check each node; if it's not visited, perform dfs from that node
27        for i in range(n):
28            if not visited[i]:
29                vertex_count, edge_count = dfs(i)
30                # In a complete graph AKA clique, the number of edges is vertex_count * (vertex_count - 1) / 2
31                # We multiply by 2 to compare with the undirected edge count (each edge counted twice)
32                if vertex_count * (vertex_count - 1) == edge_count:
33                    complete_components_count += 1
34                  
35        return complete_components_count
36
1class Solution {
2    // Graph represented as an adjacency list and a visited array.
3    private List<Integer>[] graph;
4    private boolean[] visited;
5
6    // Method to count the number of complete components in the graph.
7    public int countCompleteComponents(int n, int[][] edges) {
8        // Initialize the graph with empty lists for each node.
9        graph = new List[n];
10        visited = new boolean[n];
11        Arrays.setAll(graph, k -> new ArrayList<>());
12      
13        // Populate the adjacency list with the edges.
14        for (int[] edge : edges) {
15            int a = edge[0], b = edge[1];
16            graph[a].add(b);
17            graph[b].add(a);
18        }
19      
20        int count = 0;  // Counter for complete components.
21
22        // Traverse each node to check if it forms a complete component.
23        for (int i = 0; i < n; ++i) {
24            // If the node has not been visited, perform DFS.
25            if (!visited[i]) {
26                int[] result = dfs(i);
27                // A complete component has (n*(n-1))/2 edges. Here, result[0] is the number of nodes (n)
28                // and result[1] is the number of edges in this component.
29                if (result[0] * (result[0] - 1) == result[1]) {
30                    count++;
31                }
32            }
33        }
34        return count; // Return the total count of complete components.
35    }
36
37    // Depth First Search (DFS) helper method to compute the total number of nodes and edges in a component.
38    private int[] dfs(int index) {
39        visited[index] = true;
40        int nodesCount = 1;  // Start with one node, the one we are currently at.
41        int edgesCount = graph[index].size();  // Counts edges connected to the current node.
42
43        // Recursively visit all the neighbors that have not been visited.
44        for (int neighbor : graph[index]) {
45            if (!visited[neighbor]) {
46                int[] result = dfs(neighbor);
47                // Increment the count of nodes and edges with the counts from the neighbor.
48                nodesCount += result[0];
49                edgesCount += result[1];
50            }
51        }
52
53        // Return the total count of nodes and edges in this component.
54        return new int[] {nodesCount, edgesCount};
55    }
56}
57
1#include <vector>
2#include <cstring>
3#include <functional>
4
5using namespace std;
6
7class Solution {
8public:
9    int countCompleteComponents(int n, vector<vector<int>>& edges) {
10        vector<vector<int>> graph(n); // Using 'graph' for clarity.
11        vector<bool> visited(n, false);// Using vector of bool for visited to replace the C-style array. 
12
13        // Building the undirected graph
14        for (auto& edge : edges) {
15            int a = edge[0], b = edge[1];
16            graph[a].push_back(b);
17            graph[b].push_back(a);
18        }
19
20        // Declaration of Depth-First Search (DFS) lambda function
21        function<pair<int, int>(int)> dfs = [&](int node) -> pair<int, int> {
22            visited[node] = true;
23            int verticesCount = 1;  // 'x' has been replaced with 'verticesCount'
24            int edgesCount = graph[node].size();  // 'y' has been replaced with 'edgesCount'
25
26            // Recursive DFS calls
27            for (int neighbor : graph[node]) {
28                if (!visited[neighbor]) {
29                    auto [subtreeVertices, subtreeEdges] = dfs(neighbor);
30                    verticesCount += subtreeVertices;
31                    edgesCount += subtreeEdges;
32                }
33            }
34            return make_pair(verticesCount, edgesCount);
35        };
36
37        int completeComponents = 0;  // Using 'completeComponents' instead of 'ans' for clarity
38
39        // Checking each connected component of the graph
40        for (int i = 0; i < n; ++i) {
41            if (!visited[i]) {
42                auto [componentVertices, componentEdges] = dfs(i);
43                // Check if the connected component is a complete graph
44                // A complete graph with 'n' vertices has 'n*(n-1)/2' edges
45                if (componentVertices * (componentVertices - 1) == componentEdges) {
46                    completeComponents++;
47                }
48            }
49        }
50        return completeComponents;  // Return the count of complete components
51    }
52};
53
1type Graph = number[][];
2let graph: Graph;
3let visited: boolean[];
4
5// Builds the undirected graph from the edges
6const buildGraph = (n: number, edges: number[][]): void => {
7  graph = Array.from({ length: n }, () => []);
8  visited = new Array(n).fill(false);
9
10  edges.forEach(edge => {
11    const [a, b] = edge;
12    graph[a].push(b);
13    graph[b].push(a);
14  });
15};
16
17// Defines a Depth-First Search (DFS) function to explore the graph
18const depthFirstSearch = (node: number): [number, number] => {
19  visited[node] = true;
20  let verticesCount = 1;
21  let edgesCount = graph[node].length;
22
23  graph[node].forEach(neighbor => {
24    if (!visited[neighbor]) {
25      const [subtreeVertices, subtreeEdges] = depthFirstSearch(neighbor);
26      verticesCount += subtreeVertices;
27      edgesCount += subtreeEdges;
28    }
29  });
30
31  return [verticesCount, edgesCount];
32};
33
34// Counts the number of complete components in the graph
35const countCompleteComponents = (n: number, edges: number[][]): number => {
36  buildGraph(n, edges);
37  let completeComponents = 0;
38
39  for (let i = 0; i < n; i++) {
40    if (!visited[i]) {
41      const [componentVertices, componentEdges] = depthFirstSearch(i);
42
43      // Checks if the connected component is a complete graph
44      // A complete graph with 'n' vertices has 'n*(n-1)/2' edges
45      if (componentVertices * (componentVertices - 1) / 2 === componentEdges) {
46        completeComponents++;
47      }
48    }
49  }
50
51  return completeComponents;
52};
53

Time and Space Complexity

Time Complexity

The time complexity of the provided code is O(N + E), where N represents the number of nodes and E represents the number of edges in the graph. The reasoning behind this assessment is as follows:

  • Iterating over all edges to create the graph g yields O(E), as it is directly proportional to the number of edges.

  • The dfs function visits each node exactly once due to the guard condition if not vis[i]:, which prevents revisiting. Each call to dfs also iterates over all neighbors of the node, which results in a total of O(E) for all dfs calls across all nodes because each edge will be considered exactly twice (once from each incident node).

  • The for loop over n nodes is O(N), as it will attempt a dfs from each unvisited node.

The combination of creating the adjacency list and the DFS traversal then constitutes O(N + E).

Space Complexity

The space complexity of the code is O(N + E) as well. This assessment considers the following components that utilize memory:

  • The adjacency list g can potentially hold all the edges, which has a space requirement of O(E).

  • The visited list vis has a space requirement of O(N), since it stores a boolean for each node.

  • The recursion stack for DFS can also grow up to O(N) in the case of a deep or unbalanced tree.

  • The edges list itself occupies O(E).

Taking all these factors into account, the upper bound on space utilized by the algorithm is O(N + E), which accounts for all nodes and edges stored and processed.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which of the following shows the order of node visit in a Breadth-first Search?


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄