1
class Solution {
2
  int[] parent;
3
  boolean[] result;
4

5
  public boolean[] friendRequests(int n, int[][] restrictions, int[][] requests) {
6
    parent = new int[n];
7
    for (int i = 0; i < n; i++) {
8
      parent[i] = i;
9
    }
10
    result = new boolean[requests.length];
11

12
    for (int i = 0; i < requests.length; i++) {
13
      // personA and personB can become friends if for all restrictions
14
      // person x_i and person y_i are not in the same set as personA and personB
15
      // and vice versa
16
      int personA = requests[i][0];
17
      int personB = requests[i][1];
18
      int personASetRepresentative = find(personA);
19
      int personBSetRepresentative = find(personB);
20
      boolean flag = true;
21
      for (int[] restriction : restrictions) {
22
        int blackListPersonARepresentative = find(restriction[0]);
23
        int blackListPersonBRepresentative = find(restriction[1]);
24
        if (personASetRepresentative == blackListPersonARepresentative
25
            && personBSetRepresentative == blackListPersonBRepresentative) {
26
          flag = false;
27
        }
28
        if (personASetRepresentative == blackListPersonBRepresentative
29
            && personBSetRepresentative == blackListPersonARepresentative) {
30
          flag = false;
31
        }
32
      }
33
      if (flag) {
34
        union(personA, personB);
35
      }
36
      result[i] = flag;
37
    }
38
    return result;
39
  }
40

41
  private int find(int node) {
42
    int root = node;
43
    while (parent[root] != root) {
44
      root = parent[root];
45
    }
46

47
    // path compression
48
    int curr = node;
49
    while (parent[curr] != root) {
50
      int next = parent[curr];
51
      parent[curr] = root;
52
      curr = next;
53
    }
54
    return root;
55
  }
56

57
  private boolean union(int node1, int node2) {
58
    int root1 = find(node1);
59
    int root2 = find(node2);
60
    if (root1 == root2) {
61
      return false;
62
    }
63
    parent[root2] = root1;
64
    return true;
65
  }
66
}