🧩🤙🏻 Count Connected Components Based on Shared Properties (Using DSU / Union Find)💦🚀
IntuitionTo determine the number of connected components where each component is formed by groups of items sharing at least k common properties, we can treat th
# Intuition
To determine the number of connected components where each component is formed by groups of items sharing at least k common properties, we can treat this as a graph problem. Each item is a node, and there is an edge between two nodes if they share k or more properties. This leads to the formation of disjoint sets of nodes, which we can track using a Disjoint Set Union (DSU) data structure.


# Approach
Disjoint Set (Union-Find):
- We implement a Disjoint Set data structure supporting both union by rank and union by size. Here, unionBySize is used to merge groups.

Preprocessing:
- Convert each list of properties into a set for faster intersection checks.

Pairwise Comparison:
- For each pair of elements (i, j), compute how many properties they have in common using a helper function intersect().
- If the number of common properties is ≥ k, unite them in the DSU.

Component Counting:
- Finally, count how many unique parents exist in the DSU, which gives the number of components.


# Complexity
- Time complexity:
    - Let n be the number of items and m be the average number of properties per item.
    - Constructing the sets: O(n * m)
    - Pairwise comparisons: O(n^2 * m) in the worst case (due to intersect() doing set lookups)
    - DSU operations (with path compression and union by size): nearly constant time (amortized O(α(n)))
    - Overall: O(n^2 * m)
- Space complexity:
    - O(n * m) to store the property sets.
    - Additional O(n) for DSU structures (parent, rank, size).
    - Overall: O(n * m)

# Code
```cpp []
class DisjointSet {
public: 
    vector<int> rank, parent, size; 
    DisjointSet(int n) {
        rank.resize(n+1, 0); 
        parent.resize(n+1);
        size.resize(n+1); 
        for(int i = 0;i<=n;i++) {
            parent[i] = i; 
            size[i] = 1; 
        }
    }

    int findUPar(int node) {
        if(node == parent[node])
            return node; 
        return parent[node] = findUPar(parent[node]); 
    }

    void unionByRank(int u, int v) {
        int ulp_u = findUPar(u); 
        int ulp_v = findUPar(v); 
        if(ulp_u == ulp_v) return; 
        if(rank[ulp_u] < rank[ulp_v]) {
            parent[ulp_u] = ulp_v; 
        }
        else if(rank[ulp_v] < rank[ulp_u]) {
            parent[ulp_v] = ulp_u; 
        }
        else {
            parent[ulp_v] = ulp_u; 
            rank[ulp_u]++; 
        }
    }

    void unionBySize(int u, int v) {
        int ulp_u = findUPar(u); 
        int ulp_v = findUPar(v); 
        if(ulp_u == ulp_v) return; 
        if(size[ulp_u] < size[ulp_v]) {
            parent[ulp_u] = ulp_v; 
            size[ulp_v] += size[ulp_u]; 
        }
        else {
            parent[ulp_v] = ulp_u;
            size[ulp_u] += size[ulp_v]; 
        }
    }
}; 

class Solution {
public:
    int intersect(const unordered_set<int>& s1, const unordered_set<int>& s2){
        int common = 0;
        if (s1.size() > s2.size()) {return intersect(s2, s1);}
        for(int x : s1){ {if(s2.count(x)) common++;}
        }
        return common;
    }
    int numberOfComponents(vector<vector<int>>& properties, int k) {
        int ans = 0, n = properties.size();
        DisjointSet ds(n);
        vector<unordered_set<int>> sets(n);
        for(int i = 0; i < n; i++){
            sets[i] = unordered_set<int>(properties[i].begin(), properties[i].end());
        }
        for(int i=0; i<n; i++){
            for(int j=i+1; j<properties.size(); j++){
                if(intersect(sets[i], sets[j]) >= k){
                    ds.unionBySize(i, j);
                }
            }
        }
        for(int i=0; i<n; i++){
            if(ds.findUPar(i) == i) ans++;
        }
        return ans;
    }
};
```
['Array', 'Union Find', 'Graph', 'Ordered Set', 'C++']