Naive Solution (Brute Force)

The brute force approach would be to simulate each friend request and, after each request, check if any of the restrictions are violated. This involves creating a graph representing the friendships and, for each restriction, performing a graph traversal (e.g., DFS or BFS) to see if a path exists between the restricted individuals.

Algorithm

1. Initialize a boolean array result of the same length as requests to store the success status of each friend request.
2. For each request [u, v] in requests:
   • Assume the request is successful (initially set result[i] = true).
   • Create a temporary graph representing the friendships after adding the current request.
   • For each restriction [x, y] in restrictions:
     • Check if there is a path between x and y in the temporary graph using DFS or BFS.
     • If a path exists, set result[i] = false and break the inner loop (checking restrictions).
   • If result[i] is still true, add the friendship [u, v] to the graph.

Code (Python)

def solve():
    def check_path(graph, start, end, visited):
        if start == end:
            return True
        visited[start] = True
        for neighbor in graph[start]:
            if not visited[neighbor]:
                if check_path(graph, neighbor, end, visited):
                    return True
        return False

    def friend_requests(n, restrictions, requests):
        result = [False] * len(requests)
        friends = {i: {i} for i in range(n)}

        for i, (u, v) in enumerate(requests):
            successful = True

            # Simulate adding the edge and check restrictions
            temp_friends = {node: set(neighbors) for node, neighbors in friends.items()}
            temp_friends[u] = set(friends[u])
            temp_friends[v] = set(friends[v])

            # Union
            u_group = temp_friends[u]
v_group = temp_friends[v]


            group = u_group.union(v_group)
            for person in group:
                temp_friends[person] = group

            for x, y in restrictions:

                visited = [False] * n
                if x in group and y in group:
                    successful = False
                    break

            if successful:
                friends[u] = set(friends[u])
                friends[v] = set(friends[v])

                # Union
                u_group = friends[u]
                v_group = friends[v]

                group = u_group.union(v_group)
                for person in group:
                    friends[person] = group

                result[i] = True

        return result

    n = 3
    restrictions = [[0, 1]]
    requests = [[0, 2], [2, 1]]
    print(friend_requests(n, restrictions, requests))

    n = 3
    restrictions = [[0, 1]]
    requests = [[1, 2], [0, 2]]
    print(friend_requests(n, restrictions, requests))

    n = 5
    restrictions = [[0, 1], [1, 2], [2, 3]]
    requests = [[0, 4], [1, 2], [3, 1], [3, 4]]
    print(friend_requests(n, restrictions, requests))

solve()

Time Complexity

• O(m * r * n^2) where m is the number of requests, r is the number of restrictions, and n is the number of people. The n^2 comes from checking for a path using DFS/BFS in the worst case.

Space Complexity

• O(n^2) to store the graph representing friendships in the worst case.

Optimal Solution (Disjoint Set Union)

A more efficient approach is to use the Disjoint Set Union (DSU) data structure (also known as Union-Find). DSU allows us to keep track of connected components (friend groups) and efficiently determine if two people belong to the same group. We can use path compression and union by rank for further optimization.

Algorithm

1. Initialize a parent array where parent[i] = i for all i from 0 to n-1. This means initially each person is in their own group.
2. Define find(x) function to find the representative (root) of the group that x belongs to, with path compression.
3. Define union(x, y) function to merge the groups of x and y.
4. For each request [u, v] in requests:
   • Find the representative of u and v using the find function: rootU = find(u) and rootV = find(v).
   • Check if making u and v friends would violate any restrictions. For each restriction [x, y], find the representatives of x and y. If (find(x) == rootU and find(y) == rootV) or (find(x) == rootV and find(y) == rootU), then making u and v friends would indirectly connect x and y, violating the restriction. If any restriction is violated, the request fails.
   • If no restrictions are violated, perform union(u, v) to merge the groups of u and v and set result[i] = true. Otherwise, set result[i] = false.

Code (Python)

def solve():
    def find(parent, i):
        if parent[i] == i:
            return i
        parent[i] = find(parent, parent[i])
        return parent[i]

    def union(parent, x, y):
        root_x = find(parent, x)
        root_y = find(parent, y)
        parent[root_x] = root_y

    def friend_requests(n, restrictions, requests):
        parent = list(range(n))
        result = [False] * len(requests)

        for i, (u, v) in enumerate(requests):
            root_u = find(parent, u)
            root_v = find(parent, v)

            valid = True
            for x, y in restrictions:
                root_x = find(parent, x)
                root_y = find(parent, y)
                if (root_x == root_u and root_y == root_v) or (root_x == root_v and root_y == root_u):
                    valid = False
                    break

            if valid:
                union(parent, u, v)
                result[i] = True

        return result

    n = 3
    restrictions = [[0, 1]]
    requests = [[0, 2], [2, 1]]
    print(friend_requests(n, restrictions, requests))

    n = 3
    restrictions = [[0, 1]]
    requests = [[1, 2], [0, 2]]
    print(friend_requests(n, restrictions, requests))

    n = 5
    restrictions = [[0, 1], [1, 2], [2, 3]]
    requests = [[0, 4], [1, 2], [3, 1], [3, 4]]
    print(friend_requests(n, restrictions, requests))

solve()

Time Complexity

• O(m * (r + α(n))), where m is the number of requests, r is the number of restrictions, and α(n) is the inverse Ackermann function, which grows very slowly and can be considered almost constant for practical input sizes. The m comes from iterating through the requests. For each request, we iterate through the restrictions (r) and perform find operations (α(n)).

Space Complexity

• O(n), where n is the number of people, to store the parent array for the DSU data structure.

Edge Cases

• Empty restrictions: If there are no restrictions, all requests should be successful.
• Already friends: If u and v are already friends (belong to the same connected component), the request is still considered successful.
• Invalid input: u or v are out of range [0, n-1]. The code assumes the input is valid as per the constraints.
• Large number of restrictions: The algorithm's performance depends on the number of restrictions. If there are a very large number of restrictions, it can affect performance, but DSU still provides a significant improvement over the brute force approach.