UnionFind with rank + bitset|C++ beats 100%
IntuitionSolveed by Union find with optimation by rank.
To implement the interesection by using bitsetApproach[LC1971 uses this UnionFind class with rank. Pleas
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Solveed by Union find with optimation by rank.
To implement the interesection by using bitset
# Approach
<!-- Describe your approach to solving the problem. -->
[LC1971 uses this UnionFind class with rank. Please turn English subtitles if necessary]
[https://youtu.be/B1GQlUN08lk?si=DpfxrPBWc-t5eSPi](https://youtu.be/B1GQlUN08lk?si=DpfxrPBWc-t5eSPi)
1. UnionFind has 2 versions; 1 has `components` as member variable which is computed during performing `Union` action; other is the normal UnionFind with `rank`
2. 2 different versions for  function `intersect` which computes the number of elements in $A\cap B$ by using `bitset`
# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
$O(n^2m)$ where $m=average_{x\in nums}(|x|)$
- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$O(101)$
# Code 0~4ms||beats 100%
```cpp []
class UnionFind {
public:
    char root[100], rank[100], components;
    UnionFind(int N): components(N){
        iota(root, root+N, 0);
        fill(rank, rank+N, 1);    
    }
    
    int Find(int x) {
        return (x==root[x]) ? x : root[x] = Find(root[x]);
    }

    bool Union(int x, int y) {//Union by rank
        int rX = Find(x), rY = Find(y);
        if (rX == rY)
            return 0;
        if (rank[rX] > rank[rY])
            swap(rX, rY);
        root[rX] = rY;
        if (rank[rX] == rank[rY])
            rank[rY]++;
        components--;
        return 1;
    }
};

class Solution {
public:
    static int intersect(const auto& A, const auto& B){
       return (A&B).count();
    }
    static int numberOfComponents(vector<vector<int>>& properties, int k) {
        const int n=properties.size(), m=properties[0].size();
        vector<bitset<101>> A(n, 0);
        int i=0;
        for(auto& a: properties){
            for(int x: a) A[i][x]=1;
            i++;
        } 

        UnionFind G(n);
        int components=n;
        for(int i=0; i<n-1; i++){
            for(int j=i+1; j<n; j++){
                const auto& X=A[i];
                const auto& Y=A[j];
                if (intersect(X, Y)>=k){
                    G.Union(i, j);
                }
            }
        }
        return G.components;
    }
};
```
```cpp [C++ 2nd ver]
class UnionFind {
public:
    int root[100], rank[100];
    UnionFind(int N){
        iota(root, root+N, 0);
        fill(rank, rank+N, 1);    
    }
    
    int Find(int x) {
        return (x==root[x]) ? x : root[x] = Find(root[x]);
    }

    bool Union(int x, int y) {//Union by rank
        int rX = Find(x), rY = Find(y);
        if (rX == rY)
            return 0;
        if (rank[rX] > rank[rY])
            swap(rX, rY);
        root[rX] = rY;
        if (rank[rX] == rank[rY])
            rank[rY]++;
        return 1;
    }
    bool connected(int x, int y) {
        return Find(x) == Find(y);
    }
};

class Solution {
public:
    static int intersect(const vector<int>& A, const vector<int>& B){
        bitset<101> a=0, b=0;
        for(int x: A) a[x]=1;
        for(int x: B) b[x]=1;
        return (a&b).count();
    }
    static int numberOfComponents(vector<vector<int>>& properties, int k) {
        const int n=properties.size(), m=properties[0].size();
        UnionFind G(n);
        int components=n;
        for(int i=0; i<n-1; i++){
            for(int j=i+1; j<n; j++){
                const auto& A=properties[i];
                const auto& B=properties[j];
                if (intersect(A, B)>=k){
                    components-=G.Union(i, j);
                //    cout<<"i="<<i<<", j="<<j<<" inter="<<intersect(A, B)<<"  Union="<<u<<endl;
                }
            }
        }
        return components;
    }
};
```
['Bit Manipulation', 'Union Find', 'C++']