Taro Logo

Count the Number of Complete Components

Medium
Asked by:
Profile picture
Profile picture
Profile picture
65 views
Topics:
Graphs

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.

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What is the maximum number of nodes and edges in the graph? Are we expecting the graph to be very large?
  2. How is the graph represented in the input? Is it an adjacency list, an adjacency matrix, or a list of edges?
  3. Can the graph be disconnected? If so, how should I handle isolated nodes (nodes with no edges)?
  4. Are the node IDs zero-based or one-based, or are they defined by arbitrary values?
  5. What constitutes a 'complete component'? Does it mean that every node in the component is connected to every other node within that component, and only within that component?

Brute Force Solution

Approach

We want to find groups of connected things where everything in the group is directly connected to everything else in the group. The brute force way checks every possible group of things to see if it meets this connection requirement.

Here's how the algorithm would work step-by-step:

  1. First, consider each thing as its own separate group. It's like assuming everyone is alone at first.
  2. Then, start combining things into groups. Pick any two things and see if they're connected.
  3. If they are, put them in the same group. Now you have a potentially bigger group.
  4. Keep adding more things to that group one by one, but only if they're connected to everyone already in the group.
  5. If a thing isn't connected to everyone in the group, it stays in its own group or joins another compatible group.
  6. Do this until you've explored all the possible groups and how things can be connected.
  7. Once you've considered all combinations, count how many of those groups are 'complete', meaning everything in the group is connected to everything else.

Code Implementation

def count_complete_components_brute_force(number_of_nodes, edges):
    all_possible_groups = []

    # Initially, each node is its own group.
    for node_index in range(number_of_nodes):
        all_possible_groups.append({node_index})

    # Iterate through all possible pairs of nodes to merge groups.
    for first_node in range(number_of_nodes):
        for second_node in range(first_node + 1, number_of_nodes):
            if (first_node, second_node) in edges or (second_node, first_node) in edges:

                # Merge the groups containing the connected nodes.
                first_group_index = -1
                second_group_index = -1
                for index, group in enumerate(all_possible_groups):
                    if first_node in group:
                        first_group_index = index
                    if second_node in group:
                        second_group_index = index

                if first_group_index != second_group_index:
                    all_possible_groups[first_group_index].update(all_possible_groups[second_group_index])
                    del all_possible_groups[second_group_index]

                # Update group indices after deletion
                first_group_index = -1
                second_group_index = -1
                for index, group in enumerate(all_possible_groups):
                    if first_node in group:
                        first_group_index = index
                    if second_node in group:
                        second_group_index = index

    complete_components_count = 0

    # Check each group for completeness.
    for group in all_possible_groups:
        is_complete = True
        group_list = list(group)
        for first_node_index in range(len(group_list)):
            for second_node_index in range(first_node_index + 1, len(group_list)):

                # Check all possible node pairs
                if (group_list[first_node_index], group_list[second_node_index]) not in edges and \
                   (group_list[second_node_index], group_list[first_node_index]) not in edges:
                    is_complete = False
                    break
            if not is_complete:
                break

        # Only increase if all pairs are connected
        if is_complete:
            complete_components_count += 1

    return complete_components_count

Big(O) Analysis

Time Complexity
O(n^5) – The algorithm explores all possible subsets of nodes to identify complete components. In the worst case, it might iterate through all possible subsets, which takes O(2^n) time. For each subset, it checks if it forms a complete component. Checking if a subset of size 'k' is a complete component involves verifying that every pair of nodes within the subset has an edge. This requires O(k^2) time. Since k can be at most n, this edge verification takes O(n^2) time. Constructing each subset can be thought of as n choose k, therefore calculating all possible subsets and verifying edges takes O(2^n * n^2), or when we consider that determining if two things are connected takes O(n) time within each node, this leads to O(n^5). Thus the runtime is roughly O(n^5).
Space Complexity
O(N) – The algorithm, as described, implicitly utilizes a data structure to maintain group memberships. In the worst case, each 'thing' might start in its own separate group, leading to a need to store information about each of the N things. The 'combining things into groups' operation will likely involve representing these groups in a way that requires space proportional to the number of things. Therefore, the space complexity is O(N), where N is the number of 'things'.

Optimal Solution

Approach

The problem asks us to find separate groups of nodes in a graph where every node in the group is connected to every other node in that group. We can efficiently do this by exploring each group and checking if all the possible connections exist within that group.

Here's how the algorithm would work step-by-step:

  1. Start at any node in the graph that hasn't been visited yet.
  2. Explore all the nodes connected to this starting node, and all the nodes connected to those, and so on, to identify the entire group connected to the starting node. This is like finding all the friends of your friend, and then all the friends of those friends, and so on.
  3. As you explore, keep track of how many nodes are in the group and how many connections (edges) exist within that group.
  4. Once you've found the entire group, check if it's a complete group. A complete group means that every node is directly connected to every other node within that group. This can be verified by checking if the number of connections we tracked is equal to the number of connections there *should* be if every node was connected to every other node.
  5. If the group is complete, increase your count of complete groups.
  6. Repeat this process for every unvisited node in the graph. If a node was already visited as part of another group, we skip it because its group has already been accounted for.
  7. Finally, return the total count of complete groups that you found.

Code Implementation

def count_complete_components(number_of_nodes, edges):
    graph = [[] for _ in range(number_of_nodes)]
    for node1, node2 in edges:
        graph[node1].append(node2)
        graph[node2].append(node1)

    visited = [False] * number_of_nodes
    complete_components_count = 0

    for node in range(number_of_nodes):
        if not visited[node]:
            node_count = 0
            edge_count = 0
            queue = [node]
            group_nodes = []
            visited[node] = True

            while queue:
                current_node = queue.pop(0)
                node_count += 1
                group_nodes.append(current_node)

                for neighbor in graph[current_node]:
                    edge_count += 1

                    if not visited[neighbor]:
                        visited[neighbor] = True
                        queue.append(neighbor)

            # Divide edge_count by 2 because each edge is counted twice
            edge_count //= 2

            # Check for complete component
            if node_count * (node_count - 1) // 2 == edge_count:
                complete_components_count += 1

    return complete_components_count

Big(O) Analysis

Time Complexity
O(n + m) – The algorithm iterates through all n nodes to find unvisited nodes and potentially initiate a Depth-First Search (DFS). In the worst case, the DFS visits all nodes and edges reachable from a starting node. During each DFS, we traverse at most all the edges m connected to the nodes within the current component. Therefore, the time complexity is proportional to the number of nodes plus the number of edges visited, resulting in O(n + m), where n is the number of nodes and m is the number of edges in the graph.
Space Complexity
O(N) – The algorithm uses a visited set to keep track of visited nodes during the exploration of each component, which in the worst case can store all N nodes of the graph. Additionally, the depth-first search (DFS) implicitly uses a call stack. In the worst-case scenario, where the graph is a single long chain, the recursion depth can reach N. Therefore, the auxiliary space used by the visited set and the call stack contributes to a space complexity of O(N).

Edge Cases

Empty graph (n=0, edges=[])
How to Handle:
Return 0 since there are no components.
Graph with only one node (n=1, edges=[])
How to Handle:
Return 1 since a single node is a complete component.
Graph with no edges (n>1, edges=[])
How to Handle:
Return n, as each node is a separate complete component.
Fully connected graph (every node connected to every other)
How to Handle:
Return 1 since the entire graph is one complete component.
Graph with multiple disconnected components, some complete, some not
How to Handle:
The algorithm should correctly identify and count only the complete components by verifying all possible edges exist within each component.
Graph with a single large complete component and several isolated nodes
How to Handle:
Correctly identify the large component and count the remaining isolated nodes as complete components as well.
Maximum number of nodes and edges, check for efficient algorithm and memory usage
How to Handle:
Use an algorithm with O(n + m) complexity (where n is the number of nodes and m is the number of edges), such as Depth First Search or Breadth First Search to avoid timeouts.
Graph containing self-loops (edge from node i to itself)
How to Handle:
Ignore self-loops as they don't contribute to determining if a component is complete.