Use union find
IntuitionWhen we look at the description carefully, we can find some hints.
First, it is an undirected graph.
Second, it requires the number of connected compon
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
When we look at the description carefully, we can find some hints.
First, it is an undirected graph.
Second, it requires the number of connected components in the resulting graph.

From the second hint, we can image we only need root for every connected graph, then union find is a good choice.

And through the intersect function, we could know if they were connected, we can union them together.

Then how we find all combinations? 
We need nested loop to find them.

How we implement the intersect function?
Based on the constraint, we could use two limited array(max size 101 for 1 to 100) for counting.
Then we could check at every index again to count intersections by && operator, then return true if the result were larger than or equal to k.

Finally, counting the parent array to find roots, and it is answer!


# Approach
<!-- Describe your approach to solving the problem. -->
Using union find to find roots!

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
Let m means rows, and n means columns.
we need to loop for all combinations, it takes O(m^2), and we need to do the intersect function will take O(n), so we need O(m^2 * n).
Also, we need to find roots from parent array, it takes O(m). 
In sum, the time complexity is O(m^2 * n + m).

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
O(m) for storing rank and parent.

# Code
```cpp []
class Solution {
private:
    std::vector<int> parent;
    std::vector<int> rank;
    int find(int x) {
        if (parent[x] == -1) {
            return x;
        }
        
        return parent[x] = find(parent[x]);
    }
    
    void union_set(int x, int y) {
        int rx = find(x);
        int ry = find(y);
        
        if (rx == ry) {
            return;
        }
        
        if (rank[rx] > rank[ry]) {
            parent[ry] = rx;
            rank[rx] += rank[ry];
        } else {
            parent[rx] = ry;
            rank[ry] += rank[rx];
        }
    }
    
    bool intersect(int& k, std::vector<int>& v1, std::vector<int>& v2) {
        int cnt = 0;
        int cnt1[101]{ 0 };
        int cnt2[101]{ 0 };
        for (auto& v : v1) {
            ++cnt1[v];
        }

        for (auto& v : v2) {
            ++cnt2[v];
        }

        for (int i = 1; i <= 100; ++i) {
            if (cnt1[i] && cnt2[i]) {
                ++cnt;
            }
        }
        
        return cnt >= k;
    }
    
public:
    int numberOfComponents(vector<vector<int>>& properties, int k) {
        int rows = properties.size();
        int cols = properties[0].size();
        parent.resize(rows, -1);
        rank.resize(rows, 1);
        
        for (int r = 0; r < rows; ++r) {
            for (int n = r + 1; n < rows; ++n) {
                if (intersect(k, properties[r], properties[n])) {
                    union_set(r, n);
                }
            }
        }
        
        int ans = 0;
        for (int i = 0; i < rows; ++i) {
            if (parent[i] == -1) {
                ++ans;
            }
        }
        
        return ans;
    }
};
```
```java []
class Solution {
    private int[] parent;
    private int[] rank;

    private int find(int x) {
        if (parent[x] == -1) {
            return x;
        }

        return parent[x] = find(parent[x]);
    }

    private void unionSet(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY) {
            return;
        }

        if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
            rank[rootX] += rank[rootY];
        } else {
            parent[rootX] = rootY;
            rank[rootY] += rank[rootX];
        }
    }

    private boolean intersect(int k, int[] v1, int[] v2) {
        int[] count1 = new int[101];
        int[] count2 = new int[101];

        for (int v : v1) {
            count1[v]++;
        }

        for (int v : v2) {
            count2[v]++;
        }

        int commonCount = 0;
        for (int i = 1; i <= 100; i++) {
            if (count1[i] > 0 && count2[i] > 0) {
                commonCount++;
            }
        }

        return commonCount >= k;
    }
    public int numberOfComponents(int[][] properties, int k) {
        int rows = properties.length;
        parent = new int[rows];
        rank = new int[rows];

        Arrays.fill(parent, -1);
        Arrays.fill(rank, 1);

        for (int r = 0; r < rows; r++) {
            for (int n = r + 1; n < rows; n++) {
                if (intersect(k, properties[r], properties[n])) {
                    unionSet(r, n);
                }
            }
        }

        int components = 0;
        for (int i = 0; i < rows; i++) {
            if (parent[i] == -1) {
                components++;
            }
        }

        return components;
    }
}
```
```python3 []
class Solution:
    def __init__(self):
        self.parent = []
        self.rank = []

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # Path compression
        return self.parent[x]

    def union_set(self, x: int, y: int) -> None:
        root_x = self.find(x)
        root_y = self.find(y)

        if root_x != root_y:
            if self.rank[root_x] > self.rank[root_y]:
                self.parent[root_y] = root_x
            elif self.rank[root_x] < self.rank[root_y]:
                self.parent[root_x] = root_y
            else:
                self.parent[root_y] = root_x
                self.rank[root_x] += 1

    def intersect(self, k: int, v1: List[int], v2: List[int]) -> bool:
        counter1 = Counter(v1)
        counter2 = Counter(v2)

        common_count = sum(1 for item in counter1 if item in counter2)
        return common_count >= k

    def numberOfComponents(self, properties: List[List[int]], k: int) -> int:
        rows = len(properties)
        self.parent = list(range(rows))  # Initialize to itself
        self.rank = [0] * rows

        for r in range(rows):
            for n in range(r + 1, rows):
                if self.intersect(k, properties[r], properties[n]):
                    self.union_set(r, n)

        return sum(1 for i in range(rows) if self.find(i) == i)
```
['Union Find', 'C++', 'Java', 'Python3']