Modified DSU with Restrictions - Friend Request Management [TC: O(α(N)) | SC: O(N)]
IntuitionThe problem is a unique modification of the classic Disjoint Set Union (DSU) data structure, where we need to track not just connections between elemen
# Intuition
The problem is a unique modification of the classic Disjoint Set Union (DSU) data structure, where we need to track not just connections between elements but also maintain restrictions on which elements cannot be connected. The core challenge is managing these restrictions efficiently while performing unions.

The key insight is that restrictions between elements can be propagated through unions - if A cannot connect with B, and we unite B with C, then A also cannot connect with C. This leads to the idea of maintaining a set of restrictions for each parent node.

# Approach
1. **Enhanced DSU Structure**:
   - Traditional DSU implementation with parent array (`p`) and size array for union by size
   - Additional `restrictions` array where each element maintains a set of parent nodes it cannot unite with

2. **Restriction Management**:
   - When adding a restriction between elements A and B:
     - Find their parents (pA, pB)
     - Add each parent to the other's restriction set
   - During union, merge restriction sets and update all affected nodes

3. **Union Operation Enhancement**:
   - Before uniting elements:
     - Check if their parents are already in each other's restriction sets
     - If not restricted, perform union and merge restrictions
   - Union by size optimization to keep tree height minimal

4. **Main Algorithm Flow**:
   - Initialize DSU with N elements
   - Process all restrictions first
   - Handle each friend request by attempting to unite the elements

# Key Implementation Details
1. **Restriction Propagation**:
   ```python
   self.restrictions[pa].update(self.restrictions[pb])
   for other_parent in self.restrictions[pb]:
       self.restrictions[other_parent].remove(pb)
       self.restrictions[other_parent].add(pa)
   ```
   This ensures all restrictions are properly maintained after union.

2. **Union Safety Check**:
   ```python
   def can_unite(self, a, b):
       pa, pb = self.find(a), self.find(b)
       if pa == pb:
           return True
       return pb not in self.restrictions[pa]
   ```
   Verifies if union is allowed before performing it.

# Complexity
- Time complexity: **O(α(N))** per operation
  - Find operation with path compression: O(α(N))
  - Union operation: O(α(N)) amortized
  - Restriction management: O(R) where R is number of restrictions
  - α(N) is the inverse Ackermann function, which grows extremely slowly

- Space complexity: **O(N + R)**
  - Parent array: O(N)
  - Size array: O(N)
  - Restrictions sets: O(N + R) where R is total number of restrictions


# Code
```python3 []
class DSU:
    def __init__(self, n):
        self.n = n
        self.p = list(range(n+1))
        self.size = [1]*(n+1)
        self.restrictions = [set() for _ in range(n+1)]
        
    def find(self, u):
        if self.p[u] == u:
            return u
        self.p[u] = self.find(self.p[u])
        return self.p[u]
    
    def add_restriction(self, a, b):
        pa, pb = self.find(a), self.find(b)
        if pa != pb:
            self.restrictions[pa].add(pb)
            self.restrictions[pb].add(pa)
    
    def can_unite(self, a, b):
        pa, pb = self.find(a), self.find(b)
        if pa == pb:
            return True

        return pb not in self.restrictions[pa]
    
    def unite(self, a, b):
        if not self.can_unite(a, b):
            return False
            
        pa, pb = self.find(a), self.find(b)
        if pa != pb:
            if self.size[pa] < self.size[pb]: pa, pb = pb, pa
            
            self.restrictions[pa].update(self.restrictions[pb])
            for other_parent in self.restrictions[pb]:
                self.restrictions[other_parent].remove(pb)
                self.restrictions[other_parent].add(pa)
            
            self.size[pa] += self.size[pb]
            self.p[pb] = pa
        return True


class Solution:
    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:
        dsu = DSU(n)
        
        for u, v in restrictions:
            dsu.add_restriction(u, v)
        
        return [dsu.unite(u, v) for u, v in requests]
```
['Union Find', 'Ordered Set', 'Python3']