1
/ Standard DSU Class class DSU {
2
  vector<int> parent, size;
3

4
 public:
5
  DSU(int n) {
6
    for (int i = 0; i <= n; i++) {
7
      parent.push_back(i);
8
      size.push_back(1);
9
    }
10
  }
11

12
  int findParent(int num) {
13
    if (parent[num] == num) return num;
14
    return parent[num] = findParent(parent[num]);
15
  }
16

17
  // Directly getting parents of u and v
18
  // To avoid finding parent multiple times
19
  void unionBySize(int parU, int parV) {
20
    if (size[parU] < size[parV]) {
21
      size[parV] += size[parU];
22
      parent[parU] = parV;
23
    } else {
24
      size[parU] += size[parV];
25
      parent[parV] = parU;
26
    }
27
  }
28
};
29

30
class Solution {
31
 public:
32
  vector<bool> friendRequests(int n, vector<vector<int>> &restrictions,
33
                              vector<vector<int>> &requests) {
34
    DSU dsu(n);
35

36
    vector<bool> successful;
37

38
    for (auto &request : requests) {
39
      int u = request[0], v = request[1];
40

41
      int parU = dsu.findParent(u), parV = dsu.findParent(v);
42

43
      bool flag = true;
44

45
      if (parU != parV) {
46
        // Check if current friend requested is restricted or not.
47
        for (auto &restriction : restrictions) {
48
          int restricted_U = restriction[0], restricted_V = restriction[1];
49

50
          int restricted_parU = dsu.findParent(restricted_U);
51
          int restricted_parV = dsu.findParent(restricted_V);
52

53
          if ((parU == restricted_parU && parV == restricted_parV) ||
54
              (parU == restricted_parV && parV == restricted_parU)) {
55
            flag = false;
56
            break;
57
          }
58
        }
59

60
        // Union u and v by passing parents
61
        // Since it is already calculated above
62
        if (flag) {
63
          dsu.unionBySize(parU, parV);
64
        }
65
      }
66

67
      successful.push_back(flag);
68
    }
69

70
    return successful;
71
  }
72
};