785. Is Graph Bipartite? - Explanation

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        color = [0] * len(graph)  # Map node i -> odd=1, even=-1

        def dfs(i, c):
            color[i] = c
            for nei in graph[i]:
                if color[nei] == c:
                    return False
                if color[nei] == 0 and not dfs(nei, -c):
                    return False
            return True

        for i in range(len(graph)):
            if color[i] == 0 and not dfs(i, 1):
                return False
        return True

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        color = [0] * len(graph)  # Map node i -> odd=1, even=-1

        def bfs(i):
            if color[i]:
                return True
            q = deque([i])
            color[i] = -1
            while q:
                i = q.popleft()
                for nei in graph[i]:
                    if color[i] == color[nei]:
                        return False
                    elif not color[nei]:
                        q.append(nei)
                        color[nei] = -1 * color[i]
            return True

        for i in range(len(graph)):
            if not bfs(i):
                return False
        return True

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        color = [0] * len(graph)  # Map node i -> odd=1, even=-1
        stack = []

        for i in range(len(graph)):
            if color[i] != 0:
                continue
            color[i] = -1
            stack.append(i)
            while stack:
                node = stack.pop()
                for nei in graph[node]:
                    if color[node] == color[nei]:
                        return False
                    elif not color[nei]:
                        stack.append(nei)
                        color[nei] = -1 * color[node]

        return True

class DSU:
    def __init__(self, n):
        self.Parent = list(range(n))
        self.Size = [0] * n

    def find(self, node):
        if self.Parent[node] != node:
            self.Parent[node] = self.find(self.Parent[node])
        return self.Parent[node]

    def union(self, u, v):
        pu, pv = self.find(u), self.find(v)
        if pu == pv:
            return False
        if self.Size[pu] > self.Size[pv]:
            self.Parent[pv] = pu
        elif self.Size[pu] < self.Size[pv]:
            self.Parent[pu] = pv
        else:
            self.Parent[pv] = pu
            self.Size[pu] += 1
        return True

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        dsu = DSU(n)

        for node in range(n):
            for nei in graph[node]:
                if dsu.find(node) == dsu.find(nei):
                    return False
                dsu.union(graph[node][0], nei)

        return True