Using BFS
IntuitionThe question is the algorithm! We have to follow the steps given:
Write intersect(a, b), which counts common elements of both.
For every array where i
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The question is the algorithm! We have to follow the steps given:
1. Write `intersect(a, b)`, which counts common elements of both.
2. For every array where `i != j`, check if `count >= k`. If true, create an edge between `i` and `j`. You can generate an adjacency list or matrix.
3. Count the connected components in the graph you just generated. You can use BFS/DFS/Disjoint Set. I used BFS in my solution.

# Approach
<!-- Describe your approach to solving the problem. -->
- Construct a graph where an edge exists between two nodes if their intersection size is at least `k`.
- Use BFS to count the number of connected components.

# Complexity
- **Time complexity:**  
  - Constructing the graph: $$O(n^2 \cdot m)$$ (where $$m$$ is the max size of each array).  
  - BFS traversal: $$O(n + E)$$, where $$E$$ is the number of edges.  
  - Overall: $$O(n^2 \cdot m)$$ in the worst case.  

- **Space complexity:**  
  - $$O(n^2)$$ for the adjacency list in the worst case.  
  - $$O(n)$$ for the visited array.  
  - Overall: $$O(n^2)$$ in the worst case.  

# Code
```cpp
class Solution {
    int intersect(vector<int>& a, vector<int>& b) {
        set<int> st;
        for (int i : a)
            st.insert(i);
        int cnt = 0;
        for (int i : b) {
            if (st.find(i) != st.end()) {
                cnt++;
                st.erase(i);
            }
        }
        return cnt;
    }

public:
    int numberOfComponents(vector<vector<int>>& prop, int k) {
        int n = prop.size();
        int m = prop[0].size();
        vector<vector<int>> adj(n);
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (intersect(prop[i], prop[j]) >= k) {
                    adj[i].push_back(j);
                    adj[j].push_back(i);
                }
            }
        }

        int ans = 0;
        vector<int> vis(n, 0);
        
        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                ans++;
                queue<int> q;
                q.push(i);
                
                while (!q.empty()) {
                    int node = q.front();
                    q.pop();
                    vis[node] = 1;
                    
                    for (int x : adj[node]) {
                        if (!vis[x]) {
                            q.push(x);
                            vis[x] = 1;
                        }
                    }
                }
            }
        }
        return ans;
    }
};

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