LeetCode: Graphs

def dfs_pre(r, c, grid):
    if not (0 <= r < len(grid) and 0 <= c < len(grid[0])) or grid[r][c] == '0':
        return

    grid[r][c] = '0'  # mark visited (pre-order processing)

    for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
        dfs_pre(r + dr, c + dc, grid)

# Example: numIslands uses pre-order DFS to flood fill

def inorder(node, res):
    if not node:
        return
    inorder(node.left, res)
    res.append(node.val)  # process node in between left/right
    inorder(node.right, res)

# Example: LeetCode 98, Validate BST or BST inorder traversal

def dfs_post(r, c, grid):
    if not (0 <= r < len(grid) and 0 <= c < len(grid[0])) or grid[r][c] == '0':
        return 0

    grid[r][c] = '0'  # mark visited
    size = 1  # count current cell

    for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
        size += dfs_post(r + dr, c + dc, grid)

    return size  # post-order: aggregate after children

# Example: maxAreaOfIsland uses post-order DFS to sum area

def bfs_shortest(grid, start):
    queue = deque([(*start, 0)])  # (r, c, distance)
    visited = set([start])

    while queue:
        r, c, dist = queue.popleft()
        if grid[r][c] == 'target':
            return dist

        for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and (nr,nc) not in visited:
                visited.add((nr,nc))
                queue.append((nr,nc, dist + 1))

    def numIslandsUnion(grid):
        parent = {}
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def union(x, y):
            parent[find(x)] = find(y)
        
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if grid[r][c] == '1':
                    parent[(r,c)] = (r,c)
        
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if grid[r][c] == '1':
                    for dr, dc in [(1,0),(0,1)]:
                        nr, nc = r+dr, c+dc
                        if (nr,nc) in parent:
                            union((r,c),(nr,nc))
        
        roots = {find(x) for x in parent}
        return len(roots)

    def numIslands(self, grid: List[List[str]]) -> int:

        # Note:
        # Recursive DFS traversal: mark visited cells to avoid re-processing
        # 1. Process Root -> check if current cell is '1'
        # 2. Process Choices -> explore four neighbors (up, down, left, right)
        # 3. Backtrack -> recursion returns after marking all connected land
        # Result: increment island count per root land cell
        
        # Empty check
        if not grid:
            return 0
        
        # boundaries
        rows, cols = len(grid), len(grid[0])

        # tracking
        visited = set()

        # count
        islands = 0

        # visits any land touching (r, c)
        def dfs(r, c):

            # Late Pruning -> skip if out-of-bounds, water, or already visited
            if (r < 0 or r >= rows or 
                c < 0 or c >= cols or 
                grid[r][c] == "0" or 
                (r, c) in visited):
                return

            # Process Root -> mark current cell as visited land
            visited.add((r, c))

            # Explore -> visit all 4 neighbors
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

            # Backtrack -> implicit, no undo needed

        # iterate over grid
        for r in range(rows):
            for c in range(cols):

                # Process Root -> unvisited land found
                if grid[r][c] == '1' and (r, c) not in visited:
                    islands += 1
                    dfs(r, c)

        # overall: time complexity
        # overall: space complexity
        return islands

    def numIslands(self, grid: List[List[str]]) -> int:
        # Note:
        # Recursive DFS flood fill: mark visited land in-place
        # 1. Process Root -> check if current cell is '1'
        # 2. Process Choices -> explore four neighbors
        # 3. Backtrack -> recursion returns after marking all connected land
        # Result: increment island count per root land cell
        
        # Empty check
        if not grid:
            return 0
        
        # boundaries
        rows, cols = len(grid), len(grid[0])

        # count
        islands = 0

        # visits any land touching (r, c)
        def dfs(r, c):

            # Late Pruning -> skip out-of-bounds or water
            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
                return

            # Build / Mark -> sink current land
            grid[r][c] = '0'

            # Explore -> visit all 4 neighbors
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

            # Backtrack -> implicit, no undo needed

        for r in range(rows):
            for c in range(cols):

                # Process Root -> unvisited land found
                if grid[r][c] == '1':
                    islands += 1
                    dfs(r, c)

        # overall: time complexity O(m * n)
        # overall: space complexity O(m * n) worst-case recursion depth
        return islands

    def numIslands(self, grid: List[List[str]]) -> int:

        # Note:
        # Iterative BFS flood fill: explore entire island per root land
        # 1. Process Root -> enqueue starting land cell
        # 2. Process Choices -> explore neighbors iteratively
        # 3. Backtrack -> implicit by queue processing
        # Result: increment island count per root land cell

        # Empty check
        if not grid:
            return 0

        # boundaries
        rows, cols = len(grid), len(grid[0])
        islands = 0

        # visits any land touching (r, c)
        def bfs(r, c):

            # iterative queue
            queue = deque()

            # start iteration
            queue.append((r, c))

            # Build -> sink root island
            grid[r][c] = '0'

            while queue:

                # grab 
                cr, cc = queue.popleft()

                # Explore -> neighbors in 4 directions
                for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
                    nr, nc = cr + dr, cc + dc

                    # Late Pruning -> skip out-of-bounds or water
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                        grid[nr][nc] = '0'
                        queue.append((nr, nc))

        # iterate over grid
        for r in range(rows):
            for c in range(cols):

                # Process Root -> unvisited land found
                if grid[r][c] == '1':
                    islands += 1
                    bfs(r, c)

        # overall: time complexity O(m * n)
        # overall: space complexity O(m * n) worst-case queue
        return islands

    def numIslands(self, grid: List[List[str]]) -> int:

        # Note:
        # Union-Find approach: treat each land cell as a node
        # 1. Process Root -> initialize parent and rank for each land
        # 2. Process Choices -> union adjacent lands (right and down)
        # 3. Backtrack -> implicit via union
        # Result: number of connected components = number of islands

        # Empty check
        if not grid:
            return 0
        
        # boundaries
        rows, cols = len(grid), len(grid[0])

        # parent and rank (size)
        parent = {}
        rank = {}

        # initialize unions -> set parent to self rank to 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1':
                    parent[(r, c)] = (r, c)
                    rank[(r, c)] = 0

        # Find Path compression
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        # Union between sets
        def union(x, y):
            rootX, rootY = find(x), find(y)
            if rootX == rootY:
                return

            # union by rank (height based)
            if rank[rootX] > rank[rootY]:
               parent[rootY] = rootX
            elif rank[rootX] < rank[rootY]:
                parent[rootX] = rootY
            else:
                # height of tree only increases by 1 on equal size trees
                # A=3, B=2 -> B will point to Root A, leading to height of 3
                parent[rootY] = rootX
                rank[rootX] += 1

            # union by size (weight based)
            # if rank[rootX] > rank[rootY]:
            #     rank[rootX] += rank[rootY]
            #     parent[rootY] = rootX
            # else rank[rootX] < rank[rootY]:
            #     rank[rootY] += rank[rootX]
            #     parent[rootX] = rootY

        # iterate over grid
        for r in range(rows):
            for c in range(cols):

                # island found
                if grid[r][c] == '1':

                    # Process Choices -> 
                    # Union only down and right to avoid double union
                    for dr, dc in [(1,0), (0,1)]:
                        nr, nc = r + dr, c + dc

                        # Early Candidate Pruning -> boundaries
                        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                            union((r, c), (nr, nc))

        # Unique root count -> Unique Island Counts
        roots = set(find(cell) for cell in parent)

        # overall: time complexity
        # overall: space complexity
        return len(roots)

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        # Note:
        # 1. Treat grid as a graph: 1 = land node, edges = 4-direction adjacency
        # 2. DFS flood fill sinks land in-place to mark visited cells
        # 3. Track area of each island during DFS
        # 4. Return the maximum island area

        # Empty check
        if not grid:
            return 0

        # Boundaries
        m, n = len(grid), len(grid[0])

        # max
        max_area = 0

        def dfs(r: int, c: int) -> int:
            # Late Candidate Prune -> : out of bounds or water
            if r < 0 or c < 0 or r >= m or c >= n:
                return 0

            # Late Candidate Prune -> : water
            if grid[r][c] == 0:
                return 0

            # Process Root -> sink land
            grid[r][c] = 0

            # Process Root -> count land from root
            area = 1

            # Process Choices -> explore neighbors, add to land count
            area += dfs(r + 1, c)
            area += dfs(r - 1, c)
            area += dfs(r, c + 1)
            area += dfs(r, c - 1)

            # Backtrack -> return root land count to parent
            return area
    
        # iterate over grid
        for r in range(m):
            for c in range(n):

                # Process Root -> unvisited land found
                if grid[r][c] == 1:

                    # grab area of new island, check with max
                    island_area = dfs(r, c)
                    max_area = max(max_area, island_area)

        # overall: time complexity O(m * n)
        # overall: space complexity O(m * n) worst-case (DFS recursion stack)
        return max_area

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        # Note:
        # 1. Treat grid as a graph: 1 = land, edges = 4-direction adjacency
        # 2. BFS explores each island iteratively using a queue
        # 3. Sink land cells in-place to mark visited
        # 4. Track area of each island, return maximum

        # Empty check
        if not grid:
            return 0

        # Boundaries
        m, n = len(grid), len(grid[0])

        # max
        max_area = 0

        def bfs(r, c):
            # start BFS for this island
            area = 0
            queue = deque([(r, c)])
            grid[r][c] = 0  # mark visited

            while queue:
                cr, cc = queue.popleft()
                area += 1

                for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
                    nr, nc = cr + dr, cc + dc
                    if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
                        grid[nr][nc] = 0  # mark visited
                        queue.append((nr, nc))

            return area


        # iterate over grid 
        for r in range(m):
            for c in range(n):
                if grid[r][c] == 1:
                    island_area = bfs(r, c)
                    max_area = max(max_area, island_area)


        # overall: time complexity O(m * n)
        # overall: space complexity O(m * n) worst-case (queue holds all land cells)
        return max_area

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        
        # Note:
        # Union-Find approach to track connected components by size
        # 1. Process Root -> initialize parent and size for each land cell
        # 2. Process Candidates -> union adjacent land cells (down/right)
        # 3. Early Prune -> skip out-of-bounds
        # 4. Late Prune -> skip water cells
        # Result: max size among all connected components = max island area

        # Empty check
        if not grid:
            return 0

        # Boundaries
        m, n = len(grid), len(grid[0])

        # Union find info
        parent = {}
        size = {}

        # Find Path Compression
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        # Union two sets
        def union(x, y):
            
            rootX, rootY = find(x), find(y)
            if rootX == rootY:
                return
            
            # Union by size
            if size[rootX] >= size[rootY]:
                parent[rootY] = rootX
                size[rootX] += size[rootY]
            else:
                parent[rootX] = rootY
                size[rootY] += size[rootX]

        # Init Union Find,
        # set parent to self and size to 0
        for r in range(m):
            for c in range(n):
                if grid[r][c] == 1:
                    parent[(r, c)] = (r, c)
                    size[(r, c)] = 1

        # Iterate over grid and Union adjacent 
        # bottom and right land cells (to avoid double union)
        for r in range(m):
            for c in range(n):
                if grid[r][c] == 1:

                    # Process Choices -> 
                    # Union only down and right to avoid double union
                    for dr, dc in [(1,0), (0,1)]:
                        nr, nc = r + dr, c + dc
                        if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
                            union((r, c), (nr, nc))

        # grab the largest union size
        largestIsland = max(size.values(), default=0)

        # overall: time complexity
        # overall: space complexity
        return largestIsland

    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        # Note:
        # 1. Use DFS to traverse the graph
        # 2. Use a hashmap to store already cloned nodes
        # 3. For each node, recursively clone its neighbors
        # 4. Return the cloned node corresponding to the input
        
        # Empty check
        if not node:
            return None

        # original -> deep copy
        cloned = {}

        def dfs(n) -> Node:

            # Early Prune -> node already cloned
            if n in cloned:
                return cloned[n]

            # Process Root -> clone current node
            copy = Node(n.val)
            cloned[n] = copy

            # Process Candidates -> recursively clone all neighbors
            for neighbor in n.neighbors:
                copy.neighbors.append(dfs(neighbor))

            # Backtrack -> return cloned node
            return copy

        # grab root of cloned graph
        cloneRoot = dfs(node)

        # overall: time complexity O(V + E), visit each node and edge once
        # overall: space complexity O(V), for hashmap + recursion stack
        return cloneRoot

    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        
        # Note:
        # 1. Iterative BFS traversal to clone graph nodes
        # 2. Use hashmap to track original -> cloned node
        # 3. Process Root -> start with input node in queue
        # 4. Process Candidates -> clone neighbors iteratively
        # 5. Early Prune -> skip already cloned neighbors
        # 6. Backtrack -> queue ensures all reachable nodes are processed

        # Empty check
        if not node:
            return None

        # clone root
        cloned = {node: Node(node.val)}

        # iterative queue
        queue = deque([node])

        # iterate over all nodes
        while queue:

            # get previous roots neighbor
            current = queue.popleft()

            # iterate over neighbors
            for neighbor in current.neighbors:

                # Early Prune -> neighbor already cloned
                if neighbor not in cloned:
                    cloned[neighbor] = Node(neighbor.val)
                    queue.append(neighbor)

                # Process Candidate -> connect cloned neighbor
                cloned[current].neighbors.append(cloned[neighbor])

        # overall: time complexity O(V + E), each node and edge visited once
        # overall: space complexity O(V), for hashmap + queue
        return cloned[node]

    def orangesRotting(self, grid: List[List[int]]) -> int:
        # Note:
        # 1. Start BFS from all initially rotten oranges (multi-source BFS)
        # 2. Each BFS level = 1 minute of rotting spread
        # 3. Track fresh oranges count, decrement when they rot
        # 4. Return minutes if all fresh rot, else -1

        # Empty check
        if not grid:
            return -1

        # boundaries
        m, n = len(grid), len(grid[0])

        # count
        fresh = 0

        # time
        minutes = 0

        # iterative queue
        queue = deque()

        # set up multi source BFS
        for r in range(m):
            for c in range(n):

                # Append Rotten Source to BFS
                if grid[r][c] == 2:
                    # (row, col, minute)
                    queue.append((r, c, 0))
                
                # Add to fresh count
                elif grid[r][c] == 1:
                    fresh += 1

        # iterate over rotten sources
        while queue:

            # next rotten orange
            # minutes will be overwritten by pop,
            # last pop will have the longest and final minute count
            r, c, minutes = queue.popleft()

            # Process Choices -> 
            for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
                nr, nc = r + dr, c + dc

                # Early Prune -> : valid boundary and fresh orange
                if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    
                    # add to time and pass down
                    queue.append((nr, nc, minutes + 1))

        # total time taken if no oranges remain, else fresh orange remain so -1
        res = minutes if fresh == 0 else -1

        # overall: time complexity
        # overall: space complexity
        return res

    def orangesRotting(self, grid: List[List[int]]) -> int:
        
        # Note:
        # 1. Instead of storing time in queue, process BFS by levels
        # 2. Each level of queue expansion corresponds to +1 minute
        # 3. Track number of fresh oranges, ensure all rot or return -1

        # Empty check
        if not grid:
            return -1

        # boundaries
        m, n = len(grid), len(grid[0])

        # count
        fresh = 0

        # time
        minutes = 0

        # iterative
        queue = deque()

        # set up multi source BFS
        for r in range(m):
            for c in range(n):

                # append rotten source to queue
                if grid[r][c] == 2:
                    queue.append((r, c))

                # add to fresh count
                elif grid[r][c] == 1:
                    fresh += 1

        # iterate over rotten sources
        while queue and fresh > 0:

            # Process roots -> process all sources at this level
            for _ in range(len(queue)):

                # next candidate
                r, c = queue.popleft()

                # Process Choices -> : visit neighbors
                for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
                    nr, nc = r + dr, c + dc

                    # Early Pruning -> valid bounds and fresh fruit
                    if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
                        grid[nr][nc] = 2
                        fresh -= 1

                        # add next rotten source to queue
                        queue.append((nr, nc))

            # iterate tick for next source level
            minutes += 1

        # total time taken if no oranges remain, else fresh orange remain so -1
        res = minutes if fresh == 0 else -1

        # overall: time complexity
        # overall: space complexity
        return res

    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        
        # Note:
        # 1. Instead of simulating water flow forward (downhill), reverse the process:
        #    Start from the oceans and "climb uphill" (to neighbors with height >= current).
        # 2. Perform DFS from Pacific edges and Atlantic edges separately.
        # 3. Any cell visited in both traversals can reach both oceans.
        # 4. Collect intersection of visited sets.

        # Empty check
        if not heights:
            return []

        # boundaries
        m, n = len(heights), len(heights[0])

        # seen
        pacific = set()
        atlantic = set()

        def dfs(r: int, c: int, visited: set, prev_height: int) -> None:
            
            # Early Prune -> out of bounds, visited, or downhill
            if ((r, c) in visited or r < 0 or c < 0 or r >= m or c >= n 
                or heights[r][c] < prev_height):
                return

            # Process Root -> mark as visited
            visited.add((r, c))

            # Process Candidates -> explore 4 directions
            dfs(r + 1, c, visited, heights[r][c])
            dfs(r - 1, c, visited, heights[r][c])
            dfs(r, c + 1, visited, heights[r][c])
            dfs(r, c - 1, visited, heights[r][c])

        # Process Roots -> start from Pacific and Atlantic edges
        # These are the edge cells adjacent to each ocean from which water can "flow uphill"
        # just collecting outermost edge calls

        for i in range(m):
            # left column
            dfs(i, 0, pacific, heights[i][0])
            # right column
            dfs(i, n - 1, atlantic, heights[i][n - 1])
        for j in range(n):
            # top row
            dfs(0, j, pacific, heights[0][j])
            # bottom row
            dfs(m - 1, j, atlantic, heights[m - 1][j])

        # Late Prune -> intersection: cells reachable to both oceans
        intersection = list(pacific & atlantic)

        # overall: time complexity
        # overall: space complexity
        return intersection

    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        
        # Note:
        # 1. Same reverse flow idea, but BFS is used instead of DFS.
        # 2. BFS avoids recursion depth issues and may be easier to reason about.
        # 3. Initialize queues with Pacific and Atlantic edges separately.
        # 4. Traverse "uphill" from oceans, track visited cells for each.
        # 5. Answer = intersection of both visited sets.

        # Empty check
        if not heights:
            return []

        # boundaries
        m, n = len(heights), len(heights[0])

        #
        def bfs(starts: List[Tuple[int,int]]) -> set:
            visited = set(starts)
            queue = deque(starts)

            while queue:
                # Process Root -> current cell
                r, c = queue.popleft()

                # Process Choices -> explore neighbors
                for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
                    nr, nc = r + dr, c + dc

                    # Early Prune -> bounds, visited, uphill condition
                    if (0 <= nr < m and 0 <= nc < n and (nr, nc) not in visited
                        and heights[nr][nc] >= heights[r][c]):
                        visited.add((nr, nc))
                        queue.append((nr, nc))
            return visited

        # Process Roots -> edge cells for each ocean
        # These are the edge cells adjacent to each ocean from which water can "flow uphill"
        # just collecting outermost edge calls

        # pacific_starts = all cells on the top row (0, j) and all cells on the left column (i, 0)
        pacific_starts = [(0, j) for j in range(n)] + [(i, 0) for i in range(m)]
        
        # atlantic_starts = all cells on the bottom row (m-1, j) and all cells on the right column (i, n-1)
        atlantic_starts = [(m - 1, j) for j in range(n)] + [(i, n - 1) for i in range(m)]

        pacific = bfs(pacific_starts)
        atlantic = bfs(atlantic_starts)

        # return intersection between
        intersection = list(pacific & atlantic)

        # overall: time complexity
        # overall: space complexity
        return intersection

    def solve(self, board: List[List[str]]) -> None:
        
        # Note:
        # 1. Any 'O' connected to the border cannot be captured.
        # 2. Mark all border-connected 'O's with DFS (temporary marker 'T').
        # 3. After traversal:
        #    Flip all remaining 'O' to 'X' (they are surrounded).
        #    Flip all 'T' back to 'O'.
        # 4. Mutates board in-place, no return required.

        # Empty check
        if not board:
            return

        # boundaries
        m, n = len(board), len(board[0])

        def dfs(r, c):

            # Early Prune -> : out of bounds or not a 'O'
            if r < 0 or c < 0 or r >= m or c >= n or board[r][c] != 'O':
                return

            # Process Root -> mark as safe
            board[r][c] = 'T'

            # Process Candidates -> explore neighbors
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

        # Process Roots -> start DFS from border cells
        for i in range(m):
            # left column
            dfs(i, 0)
            # right column
            dfs(i, n - 1)
        for j in range(n):
            # top row
            dfs(0, j)
            # bottom row
            dfs(m - 1, j)

        # Late Prune -> Flip surrounded 'O' -> 'X', safe 'T' -> 'O'
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                elif board[i][j] == 'T':
                    board[i][j] = 'O'

        
        # overall: time complexity
        # overall: space complexity

    def solve(self, board: List[List[str]]) -> None:
        
        # Note:
        # 1. Same idea as DFS, but BFS is used to avoid recursion depth issues.
        # 2. Traverse from border 'O's, mark as 'T'.
        # 3. After BFS, flip surrounded 'O' -> 'X' and 'T' -> 'O'.

        # Empty Check
        if not board:
            return

        # Boundaries
        m, n = len(board), len(board[0])

        def bfs(r, c):

            # Process Root -> initialize BFS from this cell
            queue = deque([(r, c)])
            board[r][c] = 'T'
            
            while queue:
                cr, cc = queue.popleft()
                # Process Candidates -> explore neighbors
                for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
                    nr, nc = cr + dr, cc + dc

                    # Early Prune -> valid bounds and 'O'
                    if 0 <= nr < m and 0 <= nc < n and board[nr][nc] == 'O':
                        board[nr][nc] = 'T'
                        queue.append((nr, nc))

        # Process Roots -> start BFS from border 'O's
        for i in range(m):
            if board[i][0] == 'O':
                bfs(i, 0)
            if board[i][n - 1] == 'O':
                bfs(i, n - 1)
        for j in range(n):
            if board[0][j] == 'O':
                bfs(0, j)
            if board[m - 1][j] == 'O':
                bfs(m - 1, j)

        # Late Prune -> Flip surrounded 'O' -> 'X', safe 'T' -> 'O'
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                elif board[i][j] == 'T':
                    board[i][j] = 'O'

    def solve(self, board: List[List[str]]) -> None:
        # Note:
        # 1. Use Union Find (Disjoint Set Union).
        # 2. Create a dummy node representing the border.
        # 3. Union all 'O's on the border with the dummy node.
        # 4. Union all adjacent 'O's with each other.
        # 5. After unions, any 'O' connected to dummy is safe.
        # 6. Flip all other 'O' to 'X'.

        # Empty check
        if not board:
            return

        # Boundaries
        m, n = len(board), len(board[0])

        # 
        parent = {}

        # Find Path Compression
        def find(x: int) -> int:
            parent.setdefault(x, x)
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        # Union two Sets
        def union(x: int, y: int) -> None:
            parent[find(x)] = find(y)

        # Special node for border
        dummy = m * n 

        # Process Roots and Candidates -> Union Border 'O's and neighbors
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O':
                    idx = i * n + j

                    # Union border cells with dummy
                    if i in (0, m - 1) or j in (0, n - 1):
                        union(idx, dummy)

                    # Union neighbors
                    for di, dj in [(1,0), (-1,0), (0,1), (0,-1)]:
                        ni, nj = i + di, j + dj
                        if 0 <= ni < m and 0 <= nj < n and board[ni][nj] == 'O':
                            union(idx, ni * n + nj)

        # Late Prune -> flip 'O' not connected to dummy to 'X'
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O' and find(i * n + j) != find(dummy):
                    board[i][j] = 'X'

        # overall: time complexity
        # overall: space complexity

    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        
        # Note:
        # 1. Build a graph from prerequisites (course -> list of courses depending on it).
        # 2. Use DFS to detect cycles.
        #    visited[course] = 0: unvisited
        #    visited[course] = 1: visiting (currently in recursion stack)
        #    visited[course] = 2: visited (safe, no cycles in this path)
        # 3. If a cycle is found, return False (cannot finish all courses).
        # 4. Otherwise, all courses can be completed.

        # Build graph
        graph = {i: [] for i in range(numCourses)}
        for course, prereq in prerequisites:
            graph[prereq].append(course)

        # State array
        # 0 = unvisited, 1 = visiting, 2 = visited
        visited = [0] * numCourses

        def dfs(course):
            # Early Prune -> cycle detected
            if visited[course] == 1:
                return False
            # Late Prune -> already processed
            if visited[course] == 2:
                return True

            # Process Root -> mark as visiting
            visited[course] = 1

            # Process Candidates -> traverse neighbors
            for nei in graph[course]:
                if not dfs(nei):
                    return False
            
            # LAte Prune -> mark as visited
            visited[course] = 2
            return True

        # Process Roots -> traverse all courses
        for c in range(numCourses):
            if not dfs(c):
                return False

        # All courses processed, no cycles

        # overall: time complexity
        # overall: space complexity
        return True

    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        
        # Note:
        # 1. Build graph (course -> list of dependent courses) and indegree array.
        # 2. BFS from courses with indegree 0 (no prerequisites).
        # 3. Reduce indegree of neighbors; add to queue when indegree becomes 0.
        # 4. Count processed courses; if count == numCourses, return True.

        # Init graph and indegree
        indegree = [0] * numCourses
        graph = {i: [] for i in range(numCourses)}
        for course, prereq in prerequisites:
            graph[prereq].append(course)
            indegree[course] += 1

        # Process Roots -> start with courses without prerequisites
        queue = deque([i for i in range(numCourses) if indegree[i] == 0])
        count = 0

        # Process Candidates -> BFS topological sort
        while queue:
            curr = queue.popleft()
            count += 1
            for nei in graph[curr]:
                indegree[nei] -= 1
                # Early Prune -> neighbor ready to process
                if indegree[nei] == 0:
                    queue.append(nei)

        # Late Prune -> if all courses processed, no cycles
        return count == numCourses

    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = {i: [] for i in range(numCourses)}
        for course, prereq in prerequisites:
            graph[prereq].append(course)

        visited = [0] * numCourses  # 0 = unvisited, 1 = visiting, 2 = visited
        res = []
        self.is_possible = True

        def dfs(course):
            if visited[course] == 1:  # cycle detected
                self.is_possible = False
                return
            if visited[course] == 2:  # already processed
                return

            visited[course] = 1
            for nei in graph[course]:
                dfs(nei)
                if not self.is_possible:
                    return
            visited[course] = 2
            res.append(course)

        for c in range(numCourses):
            if visited[c] == 0:
                dfs(c)
                if not self.is_possible:
                    return []
        return res[::-1]  # reverse postorder

    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        indegree = [0] * numCourses
        graph = {i: [] for i in range(numCourses)}

        for course, prereq in prerequisites:
            graph[prereq].append(course)
            indegree[course] += 1

        queue = deque([i for i in range(numCourses) if indegree[i] == 0])
        res = []

        while queue:
            curr = queue.popleft()
            res.append(curr)
            for nei in graph[curr]:
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    queue.append(nei)

        return res if len(res) == numCourses else []

    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        if len(edges) != n - 1:  # a tree must have exactly n-1 edges
            return False

        graph = {i: [] for i in range(n)}
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        visited = set()

        def dfs(node, parent):
            if node in visited:
                return False
            visited.add(node)
            for nei in graph[node]:
                if nei == parent:
                    continue
                if not dfs(nei, node):
                    return False
            return True

        return dfs(0, -1) and len(visited) == n

    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        if len(edges) != n - 1:
            return False

        graph = {i: [] for i in range(n)}
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        visited = set()
        queue = deque([(0, -1)])

        while queue:
            node, parent = queue.popleft()
            if node in visited:
                return False
            visited.add(node)
            for nei in graph[node]:
                if nei != parent:
                    queue.append((nei, node))

        return len(visited) == n

    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        if len(edges) != n - 1:
            return False

        parent = [i for i in range(n)]
        rank = [1] * n

        def find(x):
            while x != parent[x]:
                parent[x] = parent[parent[x]]  # path compression
                x = parent[x]
            return x

        def union(x, y):
            rootX, rootY = find(x), find(y)
            if rootX == rootY:
                return False  # cycle detected
            if rank[rootX] > rank[rootY]:
                parent[rootY] = rootX
            elif rank[rootX] < rank[rootY]:
                parent[rootX] = rootY
            else:
                parent[rootY] = rootX
                rank[rootX] += 1
            return True

        for u, v in edges:
            if not union(u, v):
                return False

        return True

    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        # build adjacency list
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
        
        visited = set()
        
        def dfs(node):
            for nei in graph[node]:
                if nei not in visited:
                    visited.add(nei)
                    dfs(nei)
        
        components = 0
        for i in range(n):
            if i not in visited:
                visited.add(i)
                dfs(i)
                components += 1
        return components

    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
        
        visited = set()
        
        def bfs(start):
            queue = deque([start])
            while queue:
                node = queue.popleft()
                for nei in graph[node]:
                    if nei not in visited:
                        visited.add(nei)
                        queue.append(nei)
        
        components = 0
        for i in range(n):
            if i not in visited:
                visited.add(i)
                bfs(i)
                components += 1
        return components

    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        parent = [i for i in range(n)]
        rank = [1] * n
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])   # path compression
            return parent[x]
        
        def union(x, y):
            rootX, rootY = find(x), find(y)
            if rootX == rootY:
                return 0  # no merge
            if rank[rootX] > rank[rootY]:
                parent[rootY] = rootX
            elif rank[rootX] < rank[rootY]:
                parent[rootX] = rootY
            else:
                parent[rootY] = rootX
                rank[rootX] += 1
            return 1  # successful merge
        
        components = n
        for u, v in edges:
            if union(u, v):
                components -= 1
        return components

    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        graph = defaultdict(list)
        
        def dfs(u, target, visited):
            if u == target:
                return True
            visited.add(u)
            for v in graph[u]:
                if v not in visited and dfs(v, target, visited):
                    return True
            return False
        
        for u, v in edges:
            visited = set()
            if u in graph and v in graph and dfs(u, v, visited):
                return [u, v]
            graph[u].append(v)
            graph[v].append(u)

    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        graph = defaultdict(list)
        
        def bfs(u, target):
            visited = set([u])
            queue = deque([u])
            while queue:
                node = queue.popleft()
                if node == target:
                    return True
                for nei in graph[node]:
                    if nei not in visited:
                        visited.add(nei)
                        queue.append(nei)
            return False
        
        for u, v in edges:
            if u in graph and v in graph and bfs(u, v):
                return [u, v]
            graph[u].append(v)
            graph[v].append(u)

    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        parent = [i for i in range(n + 1)]
        rank = [1] * (n + 1)
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def union(x, y):
            rootX, rootY = find(x), find(y)
            if rootX == rootY:
                return False
            if rank[rootX] > rank[rootY]:
                parent[rootY] = rootX
            elif rank[rootX] < rank[rootY]:
                parent[rootX] = rootY
            else:
                parent[rootY] = rootX
                rank[rootX] += 1
            return True
        
        for u, v in edges:
            if not union(u, v):
                return [u, v]

    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        wordSet = set(wordList)
        if endWord not in wordSet:
            return 0

        L = len(beginWord)
        all_combo_dict = defaultdict(list)
        for word in wordSet:
            for i in range(L):
                pattern = word[:i] + "*" + word[i+1:]
                all_combo_dict[pattern].append(word)

        queue = deque([(beginWord, 1)])
        visited = set([beginWord])

        while queue:
            current_word, level = queue.popleft()
            for i in range(L):
                pattern = current_word[:i] + "*" + current_word[i+1:]
                for neighbor in all_combo_dict[pattern]:
                    if neighbor == endWord:
                        return level + 1
                    if neighbor not in visited:
                        visited.add(neighbor)
                        queue.append((neighbor, level + 1))
                all_combo_dict[pattern] = []  # mark pattern visited
        return 0

    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        wordSet = set(wordList)
        if endWord not in wordSet:
            return 0

        L = len(beginWord)
        all_combo_dict = defaultdict(list)
        for word in wordSet:
            for i in range(L):
                pattern = word[:i] + "*" + word[i+1:]
                all_combo_dict[pattern].append(word)

        begin_set = {beginWord}
        end_set = {endWord}
        visited = set([beginWord, endWord])
        level = 1

        while begin_set and end_set:
            if len(begin_set) > len(end_set):
                begin_set, end_set = end_set, begin_set  # expand smaller frontier

            temp = set()
            for word in begin_set:
                for i in range(L):
                    pattern = word[:i] + "*" + word[i+1:]
                    for neighbor in all_combo_dict[pattern]:
                        if neighbor in end_set:
                            return level + 1
                        if neighbor not in visited:
                            visited.add(neighbor)
                            temp.add(neighbor)
            begin_set = temp
            level += 1

        return 0