Easy C++ Union Find | Beats 88.95%
IntuitionWhen Quesion asks about no. of components and edges are supposed to be formed based on some condition , Think once along the line of Union FindApproach
# Intuition
When Quesion asks about no. of components and edges are supposed to be formed based on some condition , Think once along the line of **Union Find** 

# Approach
1. Write the code of Union Find , cnt is to maintain no. of comoponents. Initially there ar en components as there are no edges formed
2. Take every pair of i and j and check the `intersect(a[i] ,a[j])`. If it has more than k elements, then form an edge between i and j.
3. intersect function - The "v" array is maintained for the elements seens in first array and then iterate over second array to find common elements.



# Similar Problems
[Number of Operations to Make Network Connected](https://leetcode.com/problems/number-of-operations-to-make-network-connected/description/)
[Redundant Connection](https://leetcode.com/problems/redundant-connection/description/)


---



# Code
```cpp []
class Solution {
public:
vector<int> parent, rank;
int cnt;
/* code for union find */
   int find(int node)
    {
        if(node==parent[node])
            return node;
        return parent[node] = find(parent[node]);
    }
    
    void makeset(int u , int v)
    {
        u =find(u);
        v=find(v);
        if(u==v)
            return ;
        if(rank[u] < rank[v])
            parent[u] = v;
        else if(rank[v] < rank[u])
            parent[v] = u;
        else if(rank[v]==rank[u])
        {parent[v]=u;
        rank[u]++;
        }
        cnt--; // when a connection is made we reduce it because no. of components dec. by 1
    }

    int intersect(vector<int> &a1 , vector<int> &a2)
    {
        vector<int> v(101 , 0);
        for(auto x:a1)
        v[x]++;

        int cnt =0; 
        for(auto x:a2)
        {
            if(v[x]!=0)
            {
                cnt++;
                v[x] =0 ;// count only once
            }
        }
        return cnt;
    }

    int numberOfComponents(vector<vector<int>>& a, int k) {
       
        int n= a.size();
        parent.resize(n);
        rank.resize(n);
        cnt = n; // right now n components
        for(int i=0; i<n; i++)
        parent[i]=i , rank[i]=0;

        for(int i=0; i<n ; i++)
        {
            for(int j= i+1; j<n; j++)
            {
                if(find(i)!= find(j))// if i and j are already not connected
                {
                    if(intersect(a[i] , a[j]) >= k)
                    {
                        cout<<i<<" "<<j<<'\n'; 
                        makeset(i, j);
                    }
                }
            }
        }

        return cnt;
        
    }
};
```
![image.png](https://assets.leetcode.com/users/images/54230fda-3867-4343-a3f1-4f9562062c9e_1743099009.5535846.png)





['Union Find', 'Graph', 'C++']