1
class UnionFindSet(object):
2
    def __init__(self, n):
3
        self.data = range(n)
4

5
    def find(self, x):
6
        while x <> self.data[x]:
7
            x = self.data[x]
8
        return x
9

10
    def union(self, x, y):
11
        self.data[self.find(x)] = self.find(y)
12

13
    def speedup(self):
14
        for i in range(len(self.data)):
15
            self.data[i] = self.find(i)
16

17

18
class Solution(object):
19
    def friendRequests(self, n, restrictions, requests):
20
        uf = UnionFindSet(n)
21
        ret = [True] * len(requests)
22
        for k, [x, y] in enumerate(requests):  # Process Requests Sequentially
23
            xh = uf.find(x)  # backup the head of x for undo
24
            uf.union(x, y)  # link [x, y] and verify if any restriction triggers
25
            for [i, j] in restrictions:
26
                if uf.find(i) == uf.find(j):
27
                    ret[k] = False
28
                    break
29
            if not ret[k]:  # if any restriction triggers, undo
30
                uf.data[xh] = xh
31
            else:
32
                uf.speedup()
33
        return ret