2198. Process Restricted Friend Requests¶

Difficulty: Hard

2198. Process Restricted Friend Requests

Hard

You are given an integer n indicating the number of people in a network. Each person is labeled from 0 to n - 1.

You are also given a 0-indexed 2D integer array restrictions, where restrictions[i] = [x_i, y_i] means that person x_i and person y_i cannot become friends, either directly or indirectly through other people.

Initially, no one is friends with each other. You are given a list of friend requests as a 0-indexed 2D integer array requests, where requests[j] = [u_j, v_j] is a friend request between person u_j and person v_j.

A friend request is successful if u_j and v_j can be friends. Each friend request is processed in the given order (i.e., requests[j] occurs before requests[j + 1]), and upon a successful request, u_j and v_j become direct friends for all future friend requests.

Return a boolean array result, where each result[j] is true if the j^th friend request is successful or false if it is not.

Note: If u_j and v_j are already direct friends, the request is still successful.

Example 1:

Input: n = 3, restrictions = [[0,1]], requests = [[0,2],[2,1]]
Output: [true,false]
Explanation:
Request 0: Person 0 and person 2 can be friends, so they become direct friends. 
Request 1: Person 2 and person 1 cannot be friends since person 0 and person 1 would be indirect friends (1--2--0).

Example 2:

Input: n = 3, restrictions = [[0,1]], requests = [[1,2],[0,2]]
Output: [true,false]
Explanation:
Request 0: Person 1 and person 2 can be friends, so they become direct friends.
Request 1: Person 0 and person 2 cannot be friends since person 0 and person 1 would be indirect friends (0--2--1).

Example 3:

Input: n = 5, restrictions = [[0,1],[1,2],[2,3]], requests = [[0,4],[1,2],[3,1],[3,4]]
Output: [true,false,true,false]
Explanation:
Request 0: Person 0 and person 4 can be friends, so they become direct friends.
Request 1: Person 1 and person 2 cannot be friends since they are directly restricted.
Request 2: Person 3 and person 1 can be friends, so they become direct friends.
Request 3: Person 3 and person 4 cannot be friends since person 0 and person 1 would be indirect friends (0--4--3--1).

Constraints:

2 <= n <= 1000
0 <= restrictions.length <= 1000
restrictions[i].length == 2
0 <= x_i, y_i <= n - 1
x_i != y_i
1 <= requests.length <= 1000
requests[j].length == 2
0 <= u_j, v_j <= n - 1
u_j != v_j

Solution¶

class Solution {
    static class DSU {
        int parent[], size[];
        public DSU(int n) {
            parent = new int[n + 1];
            size = new int[n + 1];
            for (int i = 0; i <= n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }
        public DSU(DSU other) {
            this.parent = other.parent.clone();
            this.size = other.size.clone();
        }
        public void merge(int u, int v) {
            u = Leader(u);
            v = Leader(v);
            if (u == v)
                return;
            if (size[v] > size[u]) {
                int temp = u;
                u = v;
                v = temp;
            }
            size[u] += size[v];
            parent[v] = u;
        }
        public int Leader(int u) {
            if (u == parent[u])
                return u;
            return parent[u] = Leader(parent[u]);
        }
    }
    static class Pair {
        int u, v;
        public Pair(int u, int v) {
            this.u = u;
            this.v = v;
        }
        @Override
        public String toString() {
            return "(" + u + " " + v + ")";
        }
        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null || getClass() != obj.getClass())
                return false;
            Pair current = (Pair)(obj);
            return current.u == u && current.v == v;
        }
        @Override
        public int hashCode() {
            return Objects.hash(u, v);
        }
    }
    public boolean[] friendRequests(int n, int[][] restrictions, int[][] requests) {
        DSU dsu = new DSU(n + 1);
        DSU tempDSU = new DSU(n + 1);
        HashSet<Pair> set = new HashSet<>();
        for (int rest[] : restrictions) {
            set.add(new Pair(rest[0], rest[1])); 
        }

        boolean res[] = new boolean[requests.length];
        for (int i = 0; i < requests.length; i++) {
            int u = requests[i][0], v = requests[i][1];
            boolean flag = true;

            //They can never be friends
            if (set.contains(new Pair(u, v)) || set.contains(new Pair(v, u))) {
                res[i] = false;
                continue;
            }

            //if i make them friend do they violate the condition;
            if (dsu.Leader(u) == dsu.Leader(v)) {
                //they are friends;
                res[i] = true;
                continue;
            }
            tempDSU = new DSU(dsu);
            tempDSU.merge(u, v);
            for (Pair x : set) {
                int u1 = x.u, v1 = x.v;
                if (tempDSU.Leader(u1) == tempDSU.Leader(v1)) {
                    flag = false;
                    break;
                }
            }
            if (flag == true) {
                res[i] = true;
                dsu.merge(u, v); 
            }
            else {
                res[i] = false;
            }
        }
        return res;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here