C++ | Easy To Understand | DFS Must Learn For Interviews
Intuition
The problem involves determining the number of connected components in a graph where nodes represent elements with certain properties. Two nodes are c
**Intuition**
The problem involves determining the number of connected components in a graph where nodes represent elements with certain properties. Two nodes are connected if they share at least k properties. Our goal is to construct this graph and then count the number of connected components.

**Approach**
- Build the Graph:

- Each element is represented as a node.

- We compare every pair of nodes to check if they have at least k common properties.

- If they do, we add an edge between them, forming an adjacency list representation of the graph.

- Perform DFS to Count Components:

- We traverse the graph using Depth-First Search (DFS) to find all connected components.

- A visited array keeps track of which nodes have been explored.

- Every time we find an unvisited node, we start a new DFS traversal, counting it as a new component.

**Complexity**
**Time Complexity:**  

- Constructing the graph involves comparing all pairs of nodes, leading to **O(n² ⋅ m)**, where **n** is the number of nodes and **m** is the maximum number of properties per node.  
- DFS traversal runs in **O(n + e)**, where **e** is the number of edges.  
- Overall, the time complexity is **O(n² ⋅ m)**.  

**Space Complexity:**  

- The adjacency list requires **O(n + e)**.  
- The visited array takes **O(n)**.  
- The set representation of properties uses **O(n ⋅ m)**.  
- Overall, the space complexity is **O(n² + n ⋅ m)** in the worst case.

Explanation of the Code
1. build_graph function:
2. Converts the properties into sets for fast lookup.
3. Iterates through all pairs of nodes and checks if they share at least k properties.
4. If they do, an edge is added to the adjacency list.
5. dfs function:
Recursively explores all connected nodes starting from a given node.

6. numberOfComponents function:
Builds the graph using build_graph.
Uses DFS to count the number of connected components.

Code
```
class Solution {
public:
    vector<vector<int>> build_graph(const vector<vector<int>>& p, int k) {
        int n = p.size();
        vector<vector<int>> adj_list(n);
        vector<unordered_set<int>> s(n);
        
        // Convert properties to sets for fast lookup
        for (int i = 0; i < n; i++) {
            for (auto &x: p[i])
                s[i].insert(x);
        }

        // Check all pairs of nodes for at least k common properties
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int common = 0;
                for (auto &x: s[j]) {
                    if (s[i].count(x)) common++;
                    if (common >= k) break;
                }
                if (common >= k) {
                    adj_list[i].push_back(j);
                    adj_list[j].push_back(i);
                }
            }
        }
        return adj_list;
    }
    
    void dfs(int node, const vector<vector<int>>& adj_list, vector<bool>& visited) {
        visited[node] = true;
        
        for (int neigh: adj_list[node]) {
            if (!visited[neigh]) {
                dfs(neigh, adj_list, visited);
            }
        }
    }
    
    int numberOfComponents(vector<vector<int>>& properties, int k) {
        vector<vector<int>> adj = build_graph(properties, k);
        int n = properties.size();
        vector<bool> visited(n, false);
       
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                count++;
                dfs(i, adj, visited);
            }
        }
        return count;
    }
};
```

![A cute cat.webp](https://assets.leetcode.com/users/images/cc2c0fe5-2608-42d3-b1b5-726cfbe0a443_1742716906.9073727.webp)

['Depth-First Search', 'C++']