Problem statement

https://leetcode.com/problems/process-restricted-friend-requests/

Solution

The idea is that given problem constraints, we can allow to use union find. The idea is to traverse x, y in requests and check if we can make these persons friends or not. We can make them if we do not have restrictions: we go through all restrictions and check that we do not have restriction for two given connected components.

Complexity

It is O(n * m * log(n)) for time and O(n) for space, where m = len(requests).

class DSU:
    def __init__(self, N):
        self.p = list(range(N))

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, x, y):
        xr = self.find(x)
        yr = self.find(y)
        self.p[xr] = yr

class Solution:
    def friendRequests(self, n, restr, requests):
        dsu, ans = DSU(n), []
        ans = []
        for x, y in requests:
            x_p, y_p = dsu.find(x), dsu.find(y)
            bad = True
            for a, b in restr:
                a_p, b_p = dsu.find(a), dsu.find(b)
                if set([a_p, b_p]) == set([x_p, y_p]):
                    bad = False
                    break
                    
            ans += [bad]
            if bad: dsu.union(x, y)
                
        return ans