1
/*
2
DSU Class Template
3
*/
4
class DSU {
5
  constructor() {
6
    this.parents = new Map();
7
    this.rank = new Map();
8
  }
9

10
  add(x) {
11
    this.parents.set(x, x);
12
    this.rank.set(x, 0);
13
  }
14

15
  find(x) {
16
    const parent = this.parents.get(x);
17
    if (parent === x) return x;
18
    const setParent = this.find(parent);
19
    this.parents.set(x, setParent);
20
    return setParent;
21
  }
22

23
  union(x, y) {
24
    const xParent = this.find(x),
25
      yParent = this.find(y);
26
    const xRank = this.rank.get(xParent),
27
      yRank = this.rank.get(yParent);
28
    if (xParent === yParent) return;
29
    if (xRank > yRank) {
30
      this.parents.set(yParent, xParent);
31
    } else if (yRank > xRank) {
32
      this.parents.set(xParent, yParent);
33
    } else {
34
      this.parents.set(xParent, yParent);
35
      this.rank.set(yParent, yRank + 1);
36
    }
37
  }
38
}
39

40
/*
41
Friend Requests
42
*/
43
var friendRequests = function (n, restrictions, requests) {
44
  const dsu = new DSU(),
45
    result = [];
46
  for (let i = 0; i < n; i++) dsu.add(i);
47

48
  for (let [friend1, friend2] of requests) {
49
    const parent1 = dsu.find(friend1),
50
      parent2 = dsu.find(friend2);
51
    let friendshipPossible = true;
52
    for (let [enemy1, enemy2] of restrictions) {
53
      const enemyParent1 = dsu.find(enemy1),
54
        enemyParent2 = dsu.find(enemy2);
55
      const condition1 = enemyParent1 === parent1 && enemyParent2 === parent2;
56
      const condition2 = enemyParent1 === parent2 && enemyParent2 === parent1;
57
      if (condition1 || condition2) {
58
        friendshipPossible = false;
59
        break;
60
      }
61
    }
62
    if (friendshipPossible) dsu.union(friend1, friend2);
63
    result.push(friendshipPossible);
64
  }
65
  return result;
66
};