Union Find | Disjoint Set Union | Clean and Commented code | Video
🔹 Understanding the ProblemWe have an undirected weighted graph with n vertices labeled from 0 to n-1, and edges given as:
edges[i] = [ui, vi, wi]
This represen
## **🔹 Understanding the Problem**
We have an **undirected weighted graph** with `n` vertices labeled from `0` to `n-1`, and edges given as:  
**`edges[i] = [ui, vi, wi]`**  
- This represents an edge between vertices `ui` and `vi` with a **weight `wi`**.

We also have multiple **queries**:  
**`query[i] = [si, ti]`**  
- We need to find the **minimum cost of a walk** from node `si` to node `ti`.

### **💡 Cost Calculation**
- A walk **may visit the same edge or vertex more than once**.
- The **cost** of the walk is defined as the **bitwise AND** of all edge weights encountered.

**Output:**  
For each query, return the **minimum AND-cost** of any possible walk from `si` to `ti`. If no path exists, return `-1`.

---

## **🚀 Approach: Using Union-Find (Disjoint Set Union, DSU)** 
https://youtu.be/AJIPS-ZauVA 
### **1️⃣ Key Observations**
1. **All nodes in a connected component will have the same AND-cost.**  
   - We **merge nodes** into components using **Union-Find**.
   - The **cost for a component** is the **bitwise AND** of all edge weights in that component.

2. **Use Path Compression in DSU**  
   - This speeds up the `find` operation.

---

### **2️⃣ Steps to Solve**
1. **Initialize Union-Find (`pt`)**:
   - `pt[i]`: Parent of node `i`.
   - `pt_wt[i]`: **Minimum AND-cost** of any path in this component.

2. **Build Connected Components**:
   - **Merge (`union_`) two nodes `a` and `b`** with an edge `wt`.
   - Update `pt_wt[parent] = (pt_wt[a] & pt_wt[b] & wt)`, ensuring the minimum AND-cost.

3. **Answer Queries**:
   - If `si` and `ti` are in different components → return `-1`.
   - Otherwise, return `pt_wt[find(si)]`.

---

## **⏳ Code Implementation**
```cpp
class Solution {
public:
    int pt[100001];   // Parent array for Union-Find
    int pt_wt[100001]; // AND-cost for each component

    // Find function with path compression
    int find(int a) {
        if (pt[a] != a) {
            pt[a] = find(pt[a]);
        }
        return pt[a];
    }

    // Union function to merge components
    void union_(int a, int b, int wt) {
        pt_wt[find(a)] = wt & pt_wt[find(a)] & pt_wt[find(b)];
        pt[find(b)] = find(a);  // Merge `b` into `a`
    }

    vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& query) {
        // Step 1: Initialize DSU
        for (int i = 0; i <= 100000; i++) {
            pt[i] = i;
            pt_wt[i] = ~0;  // Initialize with all bits set to 1 (binary: 111111...111)
        }

        // Step 2: Process edges to create connected components
        for (auto &edge : edges) {
            int a = edge[0], b = edge[1], wt = edge[2];
            union_(a, b, wt);
        }

        // Step 3: Answer queries
        vector<int> ans(query.size());
        for (int i = 0; i < query.size(); i++) {
            int a = query[i][0], b = query[i][1];

            if (find(a) != find(b)) {
                ans[i] = -1;  // No path exists
            } else {
                ans[i] = pt_wt[find(a)];  // Return AND-cost of the component
            }
        }
        return ans;
    }
};
```

---

## **🛠 Complexity Analysis**
| Operation | Complexity |
|------------|------------|
| **DSU Initialization** | `O(n)` |
| **Processing `m` edges (Union-Find)** | `O(m * α(n))` (α is the inverse Ackermann function, nearly constant) |
| **Processing `q` queries** | `O(q * α(n))` |
| **Total Complexity** | **`O((m + q) * α(n)) ≈ O(m + q)`** |

Since `α(n)` is **almost constant**, the solution is **very efficient**.

---

## **✅ Key Takeaways**
- **Union-Find (DSU) with Path Compression** efficiently groups connected components.
- **Bitwise AND updates in `union_`** track the minimum AND-cost within a component.
- **Querying is O(1) per query** since we just check `find(si) == find(ti)`.
- **Scales efficiently for large inputs (`n ≤ 10^5`)**.

This approach ensures we **minimize unnecessary DFS/BFS traversals** while efficiently computing results! 🚀
['Union Find', 'Python', 'C++', 'Java']