We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count the Number of Complete Components

Difficulty: Medium

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] = [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 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.

Key Insights

  • A complete connected component with k vertices must have exactly k * (k - 1) / 2 edges.
  • We can utilize Depth-First Search (DFS) or Breadth-First Search (BFS) to explore each component of the graph.
  • By tracking the number of vertices and edges in each component, we can determine if a component is complete.
  • The graph can be represented using an adjacency list for efficient traversal.

Space and Time Complexity

Time Complexity: O(n + e), where n is the number of vertices and e is the number of edges, due to the need to traverse the graph. Space Complexity: O(n), for storing the adjacency list and visited nodes.

Solution

To solve this problem, we can use a graph traversal algorithm such as Depth-First Search (DFS) to explore each connected component of the graph. We will:

  1. Construct an adjacency list from the edges.
  2. Use a visited set to keep track of which vertices have been explored.
  3. For each unvisited vertex, initiate a DFS to explore the entire connected component, counting the vertices and edges.
  4. After traversing a component, check if it is complete by verifying if the number of edges matches the required number for a complete component (k * (k - 1) / 2).
  5. Count and return the number of complete components found.

Code Solutions

def count_complete_components(n, edges):
    from collections import defaultdict
    
    # Build the adjacency list
    graph = defaultdict(list)
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)
    
    visited = set()
    complete_count = 0

    def dfs(node):
        stack = [node]
        vertices = 0
        edge_count = 0
        while stack:
            current = stack.pop()
            if current not in visited:
                visited.add(current)
                vertices += 1
                for neighbor in graph[current]:
                    edge_count += 1  # Count edge for both directions
                    if neighbor not in visited:
                        stack.append(neighbor)
        return vertices, edge_count // 2  # Each edge is counted twice
    
    for vertex in range(n):
        if vertex not in visited:
            vertices, edge_count = dfs(vertex)
            # Check for complete component
            if edge_count == vertices * (vertices - 1) // 2:
                complete_count += 1
                
    return complete_count
← Back to All Questions