O(nm α(nm))  ≈ O(nm) || Python Solution || Union-Find
\nclass DisjointSet:\n    def __init__(self, iterable):\n        self.parent = {}\n        self.rank = {}\n\n        for x in iterable:\n            self.make_s
```\nclass DisjointSet:\n    def __init__(self, iterable):\n        self.parent = {}\n        self.rank = {}\n\n        for x in iterable:\n            self.make_set(x)\n\n    def __contains__(self, x):\n        return x in self.parent\n\n    def make_set(self, x):\n        self.parent[x] = x\n        self.rank[x] = 0\n\n    def find(self, x):\n        while self.parent[x] != x:\n            self.parent[x] = self.parent[self.parent[x]]\n            x = self.parent[x]\n        return x\n\n    def union(self, x, y):\n        x = self.find(x)\n        y = self.find(y)\n\n        if x == y:\n            return x\n\n        if self.rank[x] < self.rank[y]:\n            x, y = y, x\n\n        self.parent[y] = x\n        if self.rank[x] == self.rank[y]:\n            self.rank[x] += 1\n\n\nclass Solution:\n    def containVirus(self, isInfected: List[List[int]]) -> int:\n        n, m = len(isInfected), len(isInfected[0])\n\n        def neighbors(x):\n            i, j = x\n            for i_d, j_d in ((0, 1), (0, -1), (1, 0), (-1, 0)):\n                ii = i + i_d\n                jj = j + j_d\n                if 0 <= ii < n and 0 <= jj < m:\n                    yield (ii, jj)\n\n        isolated = set()\n        last_infected = set(\n            (i, j) for i in range(n) for j in range(m) if isInfected[i][j]\n        )\n        ds = DisjointSet(last_infected)\n        res = 0\n\n        while last_infected:\n            for x in last_infected:\n                for y in neighbors(x):\n                    if y in ds and ds.find(y) not in isolated:\n                        ds.union(x, y)\n\n            candidates = defaultdict(list)\n            for x in last_infected:\n                root = ds.find(x)\n                for y in neighbors(x):\n                    if y not in ds:\n                        candidates[root].append(y)\n\n            if not candidates:\n                break\n\n            key = lambda root: len(set(candidates[root]))\n            max_root = max(candidates.keys(), key=key)\n            res += len(candidates[max_root])\n            isolated.add(max_root)\n            del candidates[max_root]\n\n            last_infected = set()\n            for root, cells in candidates.items():\n                for x in cells:\n                    if x not in ds:\n                        last_infected.add(x)\n                        ds.make_set(x)\n                    ds.union(root, x)\n\n        return res\n\n```
['Python3']