defines the unionfind or disjoint set data structure a disjoint set is made up of a number of elements contained within another number of sets initially elements are put in their own set but sets may be merged using the unite operation we can check if two elements are in the same seet by comparing their roots if they are identical the two elements are in the same set all operations can be completed in oan where n is the number of elements and a the inverse ackermann function an grows so slowly that it might as well be constant for any conceivable n a unionfind data structure consider the following sequence of events starting with the elements 1 2 3 and 4 1 2 3 4 initally they all live in their own sets which means that root1 root3 however if we call unite1 3 we would then have the following 1 3 2 4 now we have root1 root3 but it is still the case that root1 root2 we may call unite2 4 and end up with 1 3 2 4 again we have root1 root2 but after unite3 4 we end up with 1 2 3 4 which results in root1 root2 add a new set containing the single element find the root element which represents the set of a given element that is all elements that are in the same set will return the same root element finds the sets which contains the two elements and merges them into a single set given a list of positions to operate count the number of islands after each addland operation an island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically you may assume all four edges of the grid are all surrounded by water given a 3x3 grid positions 0 0 0 1 1 2 2 1 initially the 2d grid grid is filled with water assume 0 represents water and 1 represents land 0 0 0 0 0 0 0 0 0 operation 1 addland0 0 turns the water at grid00 into a land 1 0 0 0 0 0 number of islands 1 0 0 0 operation 2 addland0 1 turns the water at grid01 into a land 1 1 0 0 0 0 number of islands 1 0 0 0 operation 3 addland1 2 turns the water at grid12 into a land 1 1 0 0 0 1 number of islands 2 0 0 0 operation 4 addland2 1 turns the water at grid21 into a land 1 1 0 0 0 1 number of islands 3 0 1 0 a union find data structure consider the following sequence of events starting with the elements 1 2 3 and 4 1 2 3 4 initally they all live in their own sets which means that root 1 root 3 however if we call unite 1 3 we would then have the following 1 3 2 4 now we have root 1 root 3 but it is still the case that root 1 root 2 we may call unite 2 4 and end up with 1 3 2 4 again we have root 1 root 2 but after unite 3 4 we end up with 1 2 3 4 which results in root 1 root 2 add a new set containing the single element find the root element which represents the set of a given element that is all elements that are in the same set will return the same root element finds the sets which contains the two elements and merges them into a single set given a list of positions to operate count the number of islands after each addland operation an island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically you may assume all four edges of the grid are all surrounded by water given a 3x3 grid positions 0 0 0 1 1 2 2 1 initially the 2d grid grid is filled with water assume 0 represents water and 1 represents land 0 0 0 0 0 0 0 0 0 operation 1 addland 0 0 turns the water at grid 0 0 into a land 1 0 0 0 0 0 number of islands 1 0 0 0 operation 2 addland 0 1 turns the water at grid 0 1 into a land 1 1 0 0 0 0 number of islands 1 0 0 0 operation 3 addland 1 2 turns the water at grid 1 2 into a land 1 1 0 0 0 1 number of islands 2 0 0 0 operation 4 addland 2 1 turns the water at grid 2 1 into a land 1 1 0 0 0 1 number of islands 3 0 1 0
class Union:
    

    def __init__(self):
        self.parents = {}
        self.size = {}
        self.count = 0

    def add(self, element):
        

        self.parents[element] = element
        self.size[element] = 1
        self.count += 1

    def root(self, element):
        

        while element != self.parents[element]:
            self.parents[element] = self.parents[self.parents[element]]
            element = self.parents[element]
        return element

    def unite(self, element1, element2):
        

        root1, root2 = self.root(element1), self.root(element2)
        if root1 == root2:
            return
        if self.size[root1] > self.size[root2]:
            root1, root2 = root2, root1
        self.parents[root1] = root2
        self.size[root2] += self.size[root1]
        self.count -= 1

def num_islands(positions):
    

    ans = []
    islands = Union()
    for position in map(tuple, positions):
        islands.add(position)
        for delta in (0, 1), (0, -1), (1, 0), (-1, 0):
            adjacent = (position[0] + delta[0], position[1] + delta[1])
            if adjacent in islands.parents:
                islands.unite(position, adjacent)
        ans += [islands.count]
    return ans