Count the Number of Complete Components

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.

• 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.

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.

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