3 posts tagged with "Union Find"

from ..notes import Uf


class Solution:
    # https://leetcode.com/problems/number-of-provinces/solutions/923039/union-find-with-union-by-ranks-and-path-compression/
    def findCircleNum(self, isConnected: list[list[int]]) -> int:
        uf = Uf(list(range(len(isConnected))))
        for i in range(len(isConnected)):
            for j in range(i + 1, len(isConnected)):
                if isConnected[i][j]:
                    uf.union(i, j)
        return len(set(uf.find(x) for x in range(len(isConnected))))

from collections import deque

vertexT = int


class Solution1:
    # [dfs] Runtime 2560 ms Beats 7.20%
    def validPath(
        self, n: int, edges: list[list[int]], source: int, destination: int
    ) -> bool:
        graph: dict[vertexT, list[vertexT]] = {}
        for vertex_1, vertex_2 in edges:
            graph.setdefault(vertex_1, []).append(vertex_2)
            graph.setdefault(vertex_2, []).append(vertex_1)

        visiteds: set[vertexT] = set()

        def dfs(vertex: vertexT):
            if vertex == destination:
                return True
            if vertex in visiteds:
                return False
            visiteds.add(vertex)
            return any(map(dfs, graph[vertex]))

        return dfs(source)


class Solution2:
    # [bfs] Runtime 1971 ms Beats 61.44%
    def validPath(
        self, n: int, edges: list[list[int]], source: int, destination: int
    ) -> bool:
        graph: dict[vertexT, set[vertexT]] = {}
        for vertex_1, vertex_2 in edges:
            graph.setdefault(vertex_1, set()).add(vertex_2)
            graph.setdefault(vertex_2, set()).add(vertex_1)

        visiteds: set[vertexT] = set()
        queue: deque[set[vertexT]] = deque([{source}])
        while queue:
            next_: set[vertexT] = set()
            q = queue.popleft()
            for vertex in q:
                if vertex == destination:
                    return True
                if vertex in visiteds:
                    continue
                visiteds.add(vertex)
                next_ |= graph[vertex]
            if next_:
                queue.append(next_)
        return False


class Uf3:
    def __init__(self, root: dict[vertexT, vertexT]):
        self.root = root

    def find(self, x: vertexT):
        if x not in self.root:
            self.root[x] = x
        if self.root[x] != x:
            self.root[x] = self.find(self.root[x])
        return self.root[x]

    def union(self, x: vertexT, y: vertexT):
        x_root, y_root = self.find(x), self.find(y)
        self.root[x_root] = y_root


class Solution3:
    # [uf]
    def validPath(
        self, n: int, edges: list[list[int]], source: int, destination: int
    ) -> bool:
        uf = Uf3({})
        for x, y in edges:
            uf.union(x, y)
        return uf.find(source) == uf.find(destination)


class Uf4:
    def __init__(self, root: dict[vertexT, vertexT]):
        self.root = root

    def find(self, x: vertexT):
        # [iteratively]
        if x not in self.root:
            self.root[x] = x
        while self.root[x] != x:
            self.root[x] = self.root[self.root[x]]
            x = self.root[x]
        return self.root[x]

    def union(self, x: vertexT, y: vertexT):
        x_root, y_root = self.find(x), self.find(y)
        self.root[x_root] = y_root


class Solution4:
    def validPath(
        self, n: int, edges: list[list[int]], source: int, destination: int
    ) -> bool:
        uf = Uf4({})
        for x, y in edges:
            uf.union(x, y)
        return uf.find(source) == uf.find(destination)


class Uf5:
    def __init__(self, root: dict[vertexT, vertexT]):
        self.root = root

    def find(self, x: vertexT):
        # dict.setdefault
        if self.root.setdefault(x, x) != x:
            self.root[x] = self.find(self.root[x])
        return self.root[x]

    def union(self, x: vertexT, y: vertexT):
        x_root, y_root = self.find(x), self.find(y)
        self.root[x_root] = y_root


class Solution5:
    def validPath(
        self, n: int, edges: list[list[int]], source: int, destination: int
    ) -> bool:
        uf = Uf5({})
        for x, y in edges:
            uf.union(x, y)
        return uf.find(source) == uf.find(destination)


class Uf6:
    DUMMY_VERTEX = -1

    def __init__(self, root: list[vertexT]):
        # use `list`
        self.root = root

    def find(self, x: vertexT):
        if self.root[x] is self.DUMMY_VERTEX:
            self.root[x] = x
        if self.root[x] != x:
            self.root[x] = self.find(self.root[x])
        return self.root[x]

    def union(self, x: vertexT, y: vertexT):
        x_root, y_root = self.find(x), self.find(y)
        self.root[x_root] = y_root


class Solution6:
    def validPath(
        self, n: int, edges: list[list[int]], source: int, destination: int
    ) -> bool:
        uf = Uf6(list(range(n)))
        for x, y in edges:
            uf.union(x, y)
        return uf.find(source) == uf.find(destination)


class Uf7:
    def __init__(self, root: list[vertexT]):
        self.root = root

    def find(self, x: vertexT):
        # without dummy (run union)
        if self.root[x] != x:
            self.root[x] = self.find(self.root[x])
        return self.root[x]

    def union(self, x: vertexT, y: vertexT):
        x_root, y_root = self.find(x), self.find(y)
        self.root[x_root] = y_root


class Solution7:
    def validPath(
        self, n: int, edges: list[list[int]], source: int, destination: int
    ) -> bool:
        uf = Uf7(list(range(n)))
        for x, y in edges:
            uf.union(x, y)
        return uf.find(source) == uf.find(destination)

vertexT = int


class Uf1:
    def __init__(self, root: list[vertexT], groups: int):
        self.root = root
        self.groups = groups

    def find(self, x: vertexT):
        if self.root[x] != x:
            self.root[x] = self.find(self.root[x])
        return self.root[x]

    def union(self, x: vertexT, y: vertexT):
        x_root, y_root = self.find(x), self.find(y)
        result = int(x_root != y_root)
        if result:
            self.root[x_root] = y_root
            self.groups -= 1
        return result


class Solution1:
    def maxNumEdgesToRemove(self, n: int, edges: list[list[int]]) -> int:
        result = 0
        ufs = [Uf1(list(range(n)), n), Uf1(list(range(n)), n)]
        for t, u, v in sorted(edges, reverse=True):
            r = 1
            for i in range(len(ufs) - 1, -1, -1):
                if t > i:
                    r &= ufs[i].union(u - 1, v - 1)
                    t -= i + 1
            result += r ^ 1  # 1, 0 -> 0, 1
        return result if ufs[0].groups == ufs[1].groups == 1 else -1


class Uf:
    def __init__(self, root: list[vertexT]):
        self.root = root

    def find(self, x: vertexT):
        if self.root[x] != x:
            self.root[x] = self.find(self.root[x])
        return self.root[x]

    def union(self, x: vertexT, y: vertexT):
        x_root, y_root = self.find(x), self.find(y)
        result = int(x_root != y_root)
        if result:
            self.root[x_root] = y_root
        return result


class Solution:
    def maxNumEdgesToRemove(self, n: int, edges: list[list[int]]) -> int:
        result = 0
        ufs = [Uf(list(range(n))), Uf(list(range(n)))]
        groups = [n, n]
        for t, u, v in sorted(edges, reverse=True):
            r = 1
            for i in range(len(groups) - 1, -1, -1):
                if t > i:
                    uni = ufs[i].union(u - 1, v - 1)
                    if uni:
                        groups[i] -= 1
                    r &= uni
                    t -= i + 1
            result += r ^ 1  # 1, 0 -> 0, 1
        return result if all(x == 1 for x in groups) else -1