Leetcode 2685. Count the Number of Complete Components

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.

The Core Concept

The solution relies on a fundamental property of graph theory: a complete graph with N nodes always has exactly N*(N-1) // 2 edges.

Instead of checking if every individual node is connected to every other node, the algorithm breaks the problem into two distinct tasks:

1. Isolate each connected component.

2. Count the nodes and edges in that component to see if they perfectly match the formula for a complete graph.

Step-by-Step Breakdown

1. Building the Graph

• Adjacency List Initialization: The code starts by converting the given edges list into an adjacency list (graph) using collections.defaultdict(list).

• Handling Isolated Nodes: It loops through range(n) to explicitly add empty lists for every node. This ensures that even completely isolated nodes (which technically count as a complete component of size 1) are registered in the graph.

• Undirected Edges: For every edge [u, v], it appends v to u's list and u to v's list, establishing the two-way connections.

2. Exploring Components via BFS

• Queue Setup: The nested bfs(s, visited) function uses a double-ended queue (deque) to explore all nodes connected to the starting node s.

• Counting Nodes: Every time a node u is popped from the queue, the nodes counter increments.

• Counting Edges: As it iterates through the neighbors (v) of node u, the edges counter increments. Because this is an undirected graph, an edge between A and B gets counted twice (once when looking at A's neighbors, and once for B's neighbors).

• Returning the Totals: To fix the double-counting, the function returns [nodes, edges // 2], giving the exact number of nodes and unique edges within that specific isolated component.

3. Iterating and Validating

• Global Visited Set: A global visited set tracks which nodes have already been assigned to a component. This prevents processing the same component multiple times.

• Processing Every Node: The main loop goes through every node from 0 to n-1. If a node hasn't been visited, it means we have discovered a brand new disconnected component.

• The Completeness Check: After the BFS returns the nodes and edges for the current component, the code applies the mathematical check: edges == (nodes * (nodes - 1)) // 2.

• Incrementing the Answer: If the condition is met, the component is complete, and the comp counter increases.

4. Time and Space Complexity

• Time Complexity: O(V + E) where V is the number of vertices and E is the number of edges. Every node and edge is processed exactly once during the BFS traversals.

• Space Complexity: O(V + E) to store the adjacency list, plus O(V) for the visited set and BFS queue.

Solution Link:

https://github.com/sanidhya12345/pythoncode/blob/master/countnumberofcompletecomponents.py