Count-the-number-of-complete-components

Question:

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] = [$a_i$ $,$ $b_i$] 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 ⇐ $a_i$ $,$ $b_i$ ⇐ n - 1
• $a_i$ $!=$ $b_i$
• There are no repeated edges.

Solution:

1. First get all the components.
2. With the help of the function isCompleteComponent(ArrayList<Integer> component, ArrayList<ArrayList<Integer>> graph){} check if the component is completely connected.
   1. For each node of component there should be neighbors(in graph) == component.size() - 1.
   2. component.size() - 1(neighbors excluding the node itself) kyuki graph mei node k index pe bs neighbors pade hote but component mei src khud bhi pada hai.

class Solution {
    public int countCompleteComponents(int n, int[][] edges) {
        ArrayList<ArrayList<Integer>> graph = buildGraph(n, edges);
        boolean[] visited = new boolean[n];
        int count = 0;
 
        for (int src = 0; src < n; i++) {
            if (!visited[src]) {
                ArrayList<Integer> component = new ArrayList<>();
                getComponent(src, graph, visited, component);
                if (isCompleteComponent(component, graph)) {
                    count++;
                }
            }
        }
 
        return count;
    }
 
    private ArrayList<ArrayList<Integer>> buildGraph(int n, int[][] edges) {
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
 
        for (int[] edge : edges) {
            int src = edge[0];
            int nbr = edge[1];
            graph.get(src).add(nbr);
            graph.get(nbr).add(src);
        }
 
        return graph;
    }
 
    private void getComponent(int sourceNode, ArrayList<ArrayList<Integer>> graph, boolean[] visited, ArrayList<Integer> component) {
        visited[sourceNode] = true;
        component.add(sourceNode);
 
        for (int neighbor : graph.get(sourceNode)) {
            if (!visited[neighbor]) {
                getComponent(neighbor, graph, visited, component);
            }
        }
    }
 
	private boolean isCompleteComponent(ArrayList<Integer> component, ArrayList<ArrayList<Integer>> graph) {
	
	    for (int node : component) {
	    /**
		    Comparison with component.size() - 1: The size of the ArrayList returned by `graph.get(node)` is compared
			with `component.size() - 1`. If they are equal, it means that each node in this subgraph has connections to all
			other nodes (except itself), indicating a complete subgraph
		**/
	        if (graph.get(node).size() != component.size() - 1) {
	            return false;
	        }
	    }
	    
	    return true;
	}
}