Easy & Detailed Explanation✅ | DSU | Union - Find | C++ | Java | Python | Js 
🧠 IntuitionThe problem requires finding the number of connected components in a graph where each node represents a list of elements.
Two nodes are connected if
# 🧠 Intuition  
The problem requires finding the number of connected components in a graph where each node represents a list of elements.  
Two nodes are connected if they share **at least k common elements**.  
A **union-find (disjoint set)** data structure is well-suited for this task as it efficiently merges components and finds their representatives.

# 🚀 Approach  
1️⃣ **Initialize Union-Find:**  
   - Create two arrays:  
     - `v1`: Parent array (stores the representative of each node).  
     - `v2`: Rank array (used for union by rank).  
   - Each node is initially its own parent.  

2️⃣ **Build Adjacency Map:**  
   - Use a **hash map** (`unordered_map`) for each node to store its elements.  
   - Helps in quickly checking common elements between nodes.  

3️⃣ **Compare Node Pairs:**  
   - Iterate over all node pairs `(i, j)`.  
   - Count the **common elements** between them.  
   - If the count is **≥ k**, merge the nodes using **union-find**.  

4️⃣ **Count Unique Components:**  
   - Use a **set** to store unique root representatives.  
   - The size of this set is the number of connected components.  

# ⏳ Complexity  
- **Time Complexity:**  
  - Constructing the adjacency map: $$O(n \cdot m)$$ (where `m` is the average list size).  
  - Checking common elements: $$O(n^2 \cdot m)$$ in the worst case.  
  - Union-Find operations (amortized): $$O(\alpha(n))$$ per operation.  
  - Overall, **approximately** $$O(n^2 \cdot m)$$.  

- **Space Complexity:**  
  - **Adjacency map:** $$O(n \cdot m)$$.  
  - **Union-Find arrays:** $$O(n)$$.  
  - **Set for unique components:** $$O(n)$$.  
  - **Total:** **$$O(n \cdot m)$$**. 
  
### **Step-by-Step Explanation**
```plaintext
properties = [[1,2], [2,3], [4,5]], k = 1
```
### Step 1: Initialize Each Node as Its Own Parent  
Initially, each node is its own parent:  

| Index (i) | Properties | Parent (v1[i]) | Rank (v2[i]) |
|-----------|------------|----------------|--------------|
| 0         | [1,2]      | 0              | 0            |
| 1         | [2,3]      | 1              | 0            |
| 2         | [4,5]      | 2              | 0            |

 
### Step 2: Create an Adjacency Map  
Each node stores its properties in a map:  

| Index (i) | Properties | Frequency Map  |
|-----------|------------|---------------|
| 0         | [1,2]      | {1:1, 2:1}    |
| 1         | [2,3]      | {2:1, 3:1}    |
| 2         | [4,5]      | {4:1, 5:1}    |

### Step 3: Compare Nodes and Merge  
We check each pair to see if they share at least k = 1 common element.  

| Pair (i, j) | Common Elements | Merge?           |
|-------------|----------------|------------------|
| (0,1)       | {2}            | ✅ Yes (Union 0,1) |
| (0,2)       | {}             | ❌ No           |
| (1,2)       | {}             | ❌ No           |

### Step 4: Find Connected Components  
After merging, we check the unique root parents:  

| Index (i) | Final Parent (find(i)) |
|-----------|------------------------|
| 0         | 0                      |
| 1         | 0                      |
| 2         | 2                      |

### Unique components are `{0, 2}`, so the final answer is **2**. 🎯  


# Code
```cpp []
class Solution {
public:
    // Arrays to store parent references and rank for union-find (disjoint set)
    vector<int> v1, v2;

    // Function to find the representative (root) of a set using path compression
    int find(int i) 
    {
        if (v1[i] != i)  // If i is not its own parent
        {
            v1[i] = find(v1[i]);  // Recursively find the root and apply path compression
        }
        return v1[i];  // Return the root of i
    }

    // Function to unite (merge) two sets using union by rank
    void unite(int i, int k) 
    {
        int a = find(i);  // Find root of i
        int b = find(k);  // Find root of k

        if (a != b)  // If they belong to different sets, merge them
        {
            if (v2[a] > v2[b]) 
            {
                v1[b] = a;  // Attach the smaller tree (b) to the larger tree (a)
            } 
            else if (v2[a] < v2[b]) 
            {
                v1[a] = b;  // Attach the smaller tree (a) to the larger tree (b)
            } 
            else 
            {
                v1[b] = a;  // Merge b into a and increase rank of a
                v2[a]++;    
            }
        }
    }

    // Function to count the number of connected components
    int numberOfComponents(vector<vector<int>>& p, int k) 
    {
        int n = p.size();  // Number of elements (nodes)

        // Initialize disjoint set
        v1.resize(n);  // Parent array
        v2.resize(n, 0);  // Rank array (initially all 0)

        for (int i = 0; i < n; i++) 
        {
            v1[i] = i;  // Each node is its own parent initially
        }

        // Create an adjacency map to store element frequency for each node
        vector<unordered_map<int, int>> mp(n);
        for (int i = 0; i < n; i++) 
        {
            for (int j : p[i]) 
            {
                mp[i][j] = mp[i][j] + 1;  // Count occurrences of each element in node i
            }
        }

        // Compare each pair of nodes to check common elements
        for (int i = 0; i < n; i++) 
        {
            for (int j = i + 1; j < n; j++) 
            {
                int cmn = 0;  // Count of common elements between node i and node j
                
                // Check for common elements between node i and j
                for (auto it = mp[i].begin(); it != mp[i].end(); it++) 
                {
                    int num = it->first;  
                    if (mp[j].find(num) != mp[j].end())  // If element exists in both nodes
                    {
                        cmn++;
                    }
                }

                // If the count of common elements is greater than or equal to k, merge them
                if (cmn >= k) {
                    unite(i, j);
                }
            }
        }

        // Count the number of unique connected components
        unordered_set<int> st;
        for (int i = 0; i < n; i++) 
        {
            st.insert(find(i));  // Insert unique root representatives into the set
        }

        return st.size();  // The number of unique roots gives the number of components
    }
};

```
```javascript []
class Solution {
    constructor() {
        this.parent = new Map();  // Parent reference map
        this.rank = new Map();  // Rank map
    }

    // Find function with path compression
    find(i) {
        if (this.parent.get(i) !== i) {
            this.parent.set(i, this.find(this.parent.get(i)));  // Path compression
        }
        return this.parent.get(i);
    }

    // Union function with union by rank
    unite(i, k) {
        let a = this.find(i);
        let b = this.find(k);

        if (a !== b) {
            if (this.rank.get(a) > this.rank.get(b)) {
                this.parent.set(b, a);
            } else if (this.rank.get(a) < this.rank.get(b)) {
                this.parent.set(a, b);
            } else {
                this.parent.set(b, a);
                this.rank.set(a, this.rank.get(a) + 1);
            }
        }
    }

    // Function to count the number of connected components
    numberOfComponents(p, k) {
        let n = p.length;

        // Initialize union-find structure
        for (let i = 0; i < n; i++) {
            this.parent.set(i, i);
            this.rank.set(i, 0);
        }

        // Create a map to store element frequency for each node
        let mp = new Array(n).fill(0).map(() => new Map());
        for (let i = 0; i < n; i++) {
            for (let num of p[i]) {
                mp[i].set(num, (mp[i].get(num) || 0) + 1);
            }
        }

        // Compare each pair of nodes to check common elements
        for (let i = 0; i < n; i++) {
            for (let j = i + 1; j < n; j++) {
                let cmn = 0;  // Count of common elements
                
                // Count common elements
                for (let num of mp[i].keys()) {
                    if (mp[j].has(num)) {
                        cmn++;
                    }
                }

                // If the count of common elements is >= k, merge the sets
                if (cmn >= k) {
                    this.unite(i, j);
                }
            }
        }

        // Count the number of unique connected components
        let st = new Set();
        for (let i = 0; i < n; i++) {
            st.add(this.find(i));
        }

        return st.size;  // The number of unique roots gives the number of components
    }
}

```
```python []
from collections import defaultdict

class Solution:
    def __init__(self):
        self.parent = {}  # Dictionary for parent references in union-find
        self.rank = {}  # Dictionary for rank of sets

    def find(self, i):
        """Find the root of node i with path compression."""
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])  # Path compression
        return self.parent[i]

    def unite(self, i, k):
        """Union by rank of two sets."""
        a = self.find(i)
        b = self.find(k)

        if a != b:  # Merge only if they are in different sets
            if self.rank[a] > self.rank[b]:
                self.parent[b] = a
            elif self.rank[a] < self.rank[b]:
                self.parent[a] = b
            else:
                self.parent[b] = a
                self.rank[a] += 1

    def numberOfComponents(self, p, k):
        n = len(p)  # Number of nodes

        # Initialize union-find structure
        for i in range(n):
            self.parent[i] = i
            self.rank[i] = 0

        # Create a dictionary to store element occurrences per node
        mp = [defaultdict(int) for _ in range(n)]
        for i in range(n):
            for num in p[i]:
                mp[i][num] += 1

        # Compare each pair of nodes to check common elements
        for i in range(n):
            for j in range(i + 1, n):
                cmn = sum(1 for num in mp[i] if num in mp[j])

                # If the count of common elements is >= k, merge the sets
                if cmn >= k:
                    self.unite(i, j)

        # Count the number of unique connected components
        return len(set(self.find(i) for i in range(n)))

```
```java []
import java.util.*;

class Solution {
    // Arrays for storing parent references and rank in union-find
    int[] parent, rank;

    // Function to find the representative (root) of a set using path compression
    private int find(int i) {
        if (parent[i] != i) {  // If i is not its own parent
            parent[i] = find(parent[i]);  // Recursively find the root and apply path compression
        }
        return parent[i];  // Return the root of i
    }

    // Function to unite (merge) two sets using union by rank
    private void unite(int i, int k) {
        int a = find(i);  // Find root of i
        int b = find(k);  // Find root of k

        if (a != b) {  // If they belong to different sets, merge them
            if (rank[a] > rank[b]) {
                parent[b] = a;  // Attach the smaller tree (b) to the larger tree (a)
            } else if (rank[a] < rank[b]) {
                parent[a] = b;  // Attach the smaller tree (a) to the larger tree (b)
            } else {
                parent[b] = a;  // Merge b into a and increase rank of a
                rank[a]++;
            }
        }
    }

    // Function to count the number of connected components
    public int numberOfComponents(List<List<Integer>> p, int k) {
        int n = p.size();  // Number of nodes

        // Initialize union-find structure
        parent = new int[n];
        rank = new int[n];

        for (int i = 0; i < n; i++) {
            parent[i] = i;  // Each node is its own parent initially
        }

        // Create an adjacency map to store element frequency for each node
        List<Map<Integer, Integer>> mp = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            mp.add(new HashMap<>());
            for (int num : p.get(i)) {
                mp.get(i).put(num, mp.get(i).getOrDefault(num, 0) + 1);
            }
        }

        // Compare each pair of nodes to check common elements
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int cmn = 0;  // Count of common elements between node i and node j
                
                // Check for common elements between node i and j
                for (int num : mp.get(i).keySet()) {
                    if (mp.get(j).containsKey(num)) {
                        cmn++;
                    }
                }

                // If the count of common elements is >= k, merge the sets
                if (cmn >= k) {
                    unite(i, j);
                }
            }
        }

        // Count the number of unique connected components
        Set<Integer> st = new HashSet<>();
        for (int i = 0; i < n; i++) {
            st.add(find(i));  // Insert unique root representatives into the set
        }

        return st.size();  // The number of unique roots gives the number of components
    }
}

```

['Hash Table', 'Union Find', 'C++', 'Java', 'Python3', 'JavaScript']