Efficiently Counting Connected Components in a Graph Using DFS (Adjacency List)
IntuitionThe problem requires us to construct a graph where each node represents a list of properties. An edge exists between two nodes if the number of common
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem requires us to construct a graph where each node represents a list of properties. An edge exists between two nodes if the number of common elements in their respective lists is at least k. Our goal is to determine the number of connected components in this graph.

# Approach
<!-- Describe your approach to solving the problem. -->
1. **Graph Construction**:
   - Iterate through all pairs of indices \((i, j)\) and check if they share at least \(k\) common elements.
   - If they do, add an edge between them in the adjacency list.

2. **Finding Connected Components**:
   - Use Depth-First Search (DFS) to count the number of connected components.

3. **Intersection Calculation**:
   - Convert each list into a set and count the number of common elements between two sets.

# Complexity
- **Time Complexity**:
  - Constructing the adjacency list takes \(O(n^2), where \(n\) is the number of nodes, and \(m\) is the average size of each property list.
  - DFS traversal takes \(O(n + E)\), where \(E\) is the number of edges.
  - Overall complexity is approximately (O(n^2).

- **Space Complexity**:
  - The adjacency list takes \(O(n^2)\) in the worst case.
  - The visited array takes \(O(n)\).
  - The set operations require \(O(m)\) space per function call.
  - Overall space complexity is approximately \(O(n^2 + m)\).

# Code
```java
class Solution {
    public int numberOfComponents(int[][] properties, int k) {
          int n=properties.length;
          List<List<Integer>> adj=new ArrayList();
          for(int i=0;i<n;i++)
           adj.add(new ArrayList());
          for(int i=0;i<n;i++)
          {
            for(int j=i+1;j<n;j++)
            {
                 if(possible(properties[i],properties[j],k))
                 {
                     adj.get(i).add(j);
                     adj.get(j).add(i);
                 }
            }
          }
          boolean vis[]=new boolean[n+1];
          int cnt=0;
          for(int i=0;i<n;i++)
          {
             if(!vis[i])
             {
                 dfs(i,vis,adj);
                 cnt++;
             }
          }
          return cnt;
    }
    public static void dfs(int node,boolean vis[],List<List<Integer>> adj)
    {
         vis[node]=true;
         for(int it:adj.get(node))
         {
             if(!vis[it])
              dfs(it,vis,adj);
         }
    }
    public static boolean possible(int a[],int b[],int k)
    {
        Set<Integer> set1=new HashSet();
        for(int ele:a)
         set1.add(ele);
        Set<Integer> set2=new HashSet();
        for(int ele:b)
        {
            if(set1.contains(ele))
             set2.add(ele);
        }
        return set2.size()>=k;
    }
}
```

This solution efficiently constructs the graph and determines the number of connected components using DFS traversal.


['Java']