from typing import List
from collections import defaultdict


class Solution:
    """
    ## 721. Accounts Merge

    Given a list of `accounts` where each element `accounts[i]` is a list of strings,
    where `accounts[i][0]` is a name and the rest are emails belonging to that account.

    Merge accounts that share at least one common email. Return the merged accounts in
    any order. Within each account, return emails in sorted order, with the name first.

    ### Examples

    ```text
    Input:
      accounts = [
        ["John","johnsmith@mail.com","john_newyork@mail.com"],
        ["John","johnsmith@mail.com","john00@mail.com"],
        ["Mary","mary@mail.com"],
        ["John","johnnybravo@mail.com"]
      ]
    Output:
      [
        ["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],
        ["Mary","mary@mail.com"],
        ["John","johnnybravo@mail.com"]
      ]

    Input:
      accounts = [["John","j1@","j2@"],["John","j1@","j3@"]]
    Output:
      [["John","j1@","j2@","j3@"]]
    ```

    ### Constraints

    - `1 <= accounts.length <= 1000`
    - `2 <= accounts[i].length <= 10`
    - `1 <= accounts[i][j].length <= 30`
    - `accounts[i][0]` consists of English letters.
    - `accounts[i][j]` (for `j > 0`) is a valid email.
    """

    def accountsMerge_dfs(self, accounts: List[List[str]]) -> List[List[str]]:
        # O(n*k*log(n*k)) time, O(n*k) space
        email_to_accounts = defaultdict(list)
        for i, account in enumerate(accounts):
            for email in account[1:]:
                email_to_accounts[email].append(i)

        visited_accounts = set()
        result = []

        def dfs(idx: int, emails: set) -> None:
            if idx in visited_accounts:
                return
            visited_accounts.add(idx)
            for email in accounts[idx][1:]:
                emails.add(email)
                for neighbor in email_to_accounts[email]:
                    dfs(neighbor, emails)

        for i in range(len(accounts)):
            if i not in visited_accounts:
                emails: set = set()
                dfs(i, emails)
                result.append([accounts[i][0]] + sorted(emails))
        return result

    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        # Union-Find: union all emails within the same account
        # Group emails by their root representative; attach account name
        # O(n*k*alpha(n*k)) time, O(n*k) space — Union-Find
        parent: dict = {}
        rank: dict = {}

        def find(x: str) -> str:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(x: str, y: str) -> None:
            px, py = find(x), find(y)
            if px == py:
                return
            if rank.get(px, 0) < rank.get(py, 0):
                px, py = py, px
            parent[py] = px
            if rank.get(px, 0) == rank.get(py, 0):
                rank[px] = rank.get(px, 0) + 1

        email_to_name: dict = {}
        for account in accounts:
            name = account[0]
            for email in account[1:]:
                if email not in parent:
                    parent[email] = email
                email_to_name[email] = name
                union(account[1], email)

        groups: dict = defaultdict(list)
        for email in parent:
            groups[find(email)].append(email)

        return [[email_to_name[root]] + sorted(emails) for root, emails in groups.items()]


if __name__ == '__main__':
    s = Solution()

    accounts1 = [
        ["John", "johnsmith@mail.com", "john_newyork@mail.com"],
        ["John", "johnsmith@mail.com", "john00@mail.com"],
        ["Mary", "mary@mail.com"],
        ["John", "johnnybravo@mail.com"],
    ]
    res = s.accountsMerge(accounts1)
    assert len(res) == 3

    accounts2 = [["John", "j1@", "j2@"], ["John", "j1@", "j3@"]]
    res2 = s.accountsMerge(accounts2)
    assert len(res2) == 1 and sorted(res2[0][1:]) == ["j1@", "j2@", "j3@"]

    res3 = s.accountsMerge_dfs(accounts2)
    assert len(res3) == 1 and sorted(res3[0][1:]) == ["j1@", "j2@", "j3@"]
    print("All tests passed.")

"""
# LC 785: Is Graph Bipartite?

A graph is bipartite if its nodes can be split into two groups such that
every edge connects nodes from different groups (i.e., it is 2-colorable and
contains no odd-length cycles). Return whether the given adjacency-list graph
is bipartite.

## Examples
```text
Input: graph = [[1,3],[0,2],[1,3],[0,2]]
Output: True

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: False
```

## Constraints
- Disconnected components must each be checked independently.
- A self-loop makes a graph non-bipartite.
- An empty graph or a single node is bipartite.
"""
from typing import List
from collections import deque

class Solution:
    # Approach 1: BFS coloring - try to 2-color the graph
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        color = [-1] * n  # -1 = unvisited, 0 and 1 are the two colors

        for start in range(n):  # handle disconnected components
            if color[start] != -1:
                continue
            queue = deque([start])
            color[start] = 0
            while queue:
                node = queue.popleft()
                for neighbor in graph[node]:
                    if color[neighbor] == -1:
                        color[neighbor] = 1 - color[node]  # assign opposite color
                        queue.append(neighbor)
                    elif color[neighbor] == color[node]:
                        return False  # same color on both ends = odd cycle
        return True

    # Approach 2: DFS coloring
    def isBipartite_dfs(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        color = [-1] * n

        def dfs(node, c):
            color[node] = c
            for neighbor in graph[node]:
                if color[neighbor] == -1:
                    if not dfs(neighbor, 1 - c):
                        return False
                elif color[neighbor] == c:
                    return False  # conflict
            return True

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


if __name__ == "__main__":
    s = Solution()
    assert s.isBipartite([[1,3],[0,2],[1,3],[0,2]]) is True
    assert s.isBipartite([[1,2,3],[0,2],[0,1,3],[0,2]]) is False
    assert s.isBipartite_dfs([[1,3],[0,2],[1,3],[0,2]]) is True
    assert s.isBipartite_dfs([[1,2,3],[0,2],[0,1,3],[0,2]]) is False
    print("All tests passed.")

"""
# 133. Clone Graph

## Problem
Given a reference of a node in a connected undirected graph, return a deep copy (clone)
of the graph. Each node in the graph contains a value (`int`) and a list of its neighbors.

```text
class Node {
    public int val;
    public List<Node> neighbors;
}
```

## Examples
```text
Input:  adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: 4 nodes, node 1 connects to 2 and 4, node 2 connects to 1 and 3, etc.
```

```text
Input:  adjList = [[]]
Output: [[]]
Explanation: Single node with no neighbors.
```

```text
Input:  adjList = []
Output: []
Explanation: Empty graph.
```

## Constraints
- The number of nodes in the graph is in the range `[0, 100]`
- `1 <= Node.val <= 100`
- `Node.val` is unique for each node
- There are no repeated edges and no self-loops
- The graph is connected (all nodes can be visited starting from the given node)
"""

from typing import Optional
from collections import deque


class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []


class Solution:
    def cloneGraph_dfs(self, node: Optional['Node']) -> Optional['Node']:
        # O(V+E) time, O(V) space — DFS with visited map
        if not node:
            return None
        visited = {}

        def dfs(n):
            if n in visited:
                return visited[n]
            clone = Node(n.val)
            visited[n] = clone
            for nb in n.neighbors:
                clone.neighbors.append(dfs(nb))
            return clone

        return dfs(node)

    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        # BFS/DFS with a visited map: old_node -> new_node clone
        # For each node, clone it if not seen, then clone all its neighbors
        # O(V+E) time, O(V) space — BFS with visited map
        if not node:
            return None
        visited = {node: Node(node.val)}
        q = deque([node])
        while q:
            curr = q.popleft()
            for nb in curr.neighbors:
                if nb not in visited:
                    visited[nb] = Node(nb.val)
                    q.append(nb)
                visited[curr].neighbors.append(visited[nb])
        return visited[node]


def build_graph(adj: list) -> Optional[Node]:
    if not adj:
        return None
    nodes = [Node(i+1) for i in range(len(adj))]
    for i, neighbors in enumerate(adj):
        nodes[i].neighbors = [nodes[j-1] for j in neighbors]
    return nodes[0]

def graph_to_adj(node: Optional[Node]) -> list:
    if not node:
        return []
    visited, result = {}, {}
    q = deque([node])
    visited[node.val] = node
    while q:
        curr = q.popleft()
        result[curr.val] = sorted(nb.val for nb in curr.neighbors)
        for nb in curr.neighbors:
            if nb.val not in visited:
                visited[nb.val] = nb
                q.append(nb)
    return [result[i] for i in sorted(result)]


if __name__ == '__main__':
    s = Solution()
    adj = [[2,4],[1,3],[2,4],[1,3]]
    g = build_graph(adj)
    assert graph_to_adj(s.cloneGraph_dfs(g)) == [[2,4],[1,3],[2,4],[1,3]]
    assert graph_to_adj(s.cloneGraph(build_graph(adj))) == [[2,4],[1,3],[2,4],[1,3]]
    assert s.cloneGraph(None) is None
    print("All tests passed.")

"""
# 207. Course Schedule

## Problem
There are a total of `numCourses` courses you have to take, labeled from `0` to
`numCourses - 1`. You are given an array `prerequisites` where `prerequisites[i] = [a, b]`
indicates that you must take course `b` first if you want to take course `a`.

Return `true` if you can finish all courses. Otherwise, return `false`.

## Examples
```text
Input:  numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: Take course 0 first, then course 1.
```

```text
Input:  numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: Courses 0 and 1 are mutually dependent — impossible.
```

```text
Input:  numCourses = 5, prerequisites = [[1,0],[2,1],[3,2],[4,3]]
Output: true
```

## Constraints
- `1 <= numCourses <= 2000`
- `0 <= prerequisites.length <= 5000`
- `prerequisites[i].length == 2`
- `0 <= a, b < numCourses`
- All the pairs `prerequisites[i]` are unique
"""

from typing import List
from collections import deque, defaultdict


class Solution:
    def canFinish_dfs(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # O(V+E) time, O(V+E) space — DFS cycle detection with 3-color marking
        graph = defaultdict(list)
        for a, b in prerequisites:
            graph[b].append(a)
        # 0=unvisited, 1=visiting, 2=done
        state = [0] * numCourses

        def dfs(node):
            if state[node] == 1:
                return False   # back edge → cycle
            if state[node] == 2:
                return True
            state[node] = 1
            for nb in graph[node]:
                if not dfs(nb):
                    return False
            state[node] = 2
            return True

        return all(dfs(i) for i in range(numCourses))

    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # Build adjacency list; detect cycle using DFS with 3-state coloring
        # States: 0=unvisited, 1=in-progress (cycle if revisited), 2=done
        # O(V+E) time, O(V+E) space — BFS topological sort (Kahn's algorithm)
        graph = defaultdict(list)
        indegree = [0] * numCourses
        for a, b in prerequisites:
            graph[b].append(a)
            indegree[a] += 1
        q = deque(i for i in range(numCourses) if indegree[i] == 0)
        processed = 0
        while q:
            node = q.popleft()
            processed += 1
            for nb in graph[node]:
                indegree[nb] -= 1
                if indegree[nb] == 0:
                    q.append(nb)
        return processed == numCourses


if __name__ == '__main__':
    s = Solution()
    assert s.canFinish_dfs(2, [[1,0]]) == True
    assert s.canFinish_dfs(2, [[1,0],[0,1]]) == False
    assert s.canFinish_dfs(5, [[1,0],[2,1],[3,2],[4,3]]) == True
    assert s.canFinish(2, [[1,0]]) == True
    assert s.canFinish(2, [[1,0],[0,1]]) == False
    assert s.canFinish(1, []) == True
    print("All tests passed.")

from typing import List
from collections import deque


class Solution:
    """
    ## 210. Course Schedule II

    There are `numCourses` courses labeled `0` to `numCourses - 1`. You are given
    an array `prerequisites` where `prerequisites[i] = [ai, bi]` indicates you must
    take course `bi` first if you want to take course `ai`.

    Return the ordering of courses you should take to finish all courses. If there
    are many valid answers, return any of them. If it is impossible to finish all
    courses, return an empty array.

    ### Examples

    ```text
    Input:  numCourses = 2, prerequisites = [[1,0]]
    Output: [0, 1]

    Input:  numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
    Output: [0,2,1,3]

    Input:  numCourses = 1, prerequisites = []
    Output: [0]
    ```

    ### Constraints

    - `1 <= numCourses <= 2000`
    - `0 <= prerequisites.length <= numCourses * (numCourses - 1)`
    - `prerequisites[i].length == 2`
    - `0 <= ai, bi < numCourses`
    - `ai != bi`
    - All pairs `[ai, bi]` are distinct.
    """

    def findOrder_dfs(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # O(V+E) time, O(V+E) space
        graph = [[] for _ in range(numCourses)]
        for a, b in prerequisites:
            graph[b].append(a)

        # 0=unvisited, 1=visiting, 2=visited
        state = [0] * numCourses
        order = []

        def dfs(node: int) -> bool:
            if state[node] == 1:
                return False  # cycle
            if state[node] == 2:
                return True
            state[node] = 1
            for nei in graph[node]:
                if not dfs(nei):
                    return False
            state[node] = 2
            order.append(node)
            return True

        for i in range(numCourses):
            if not dfs(i):
                return []
        return order[::-1]

    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # Topological sort via DFS post-order; cycle detection aborts
        # Reverse post-order gives valid course order
        # O(V+E) time, O(V+E) space — Kahn's BFS
        graph = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses
        for a, b in prerequisites:
            graph[b].append(a)
            indegree[a] += 1

        queue = deque(i for i in range(numCourses) if indegree[i] == 0)
        order = []
        while queue:
            node = queue.popleft()
            order.append(node)
            for nei in graph[node]:
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    queue.append(nei)
        return order if len(order) == numCourses else []


if __name__ == '__main__':
    s = Solution()
    assert s.findOrder(2, [[1, 0]]) == [0, 1]
    result = s.findOrder(4, [[1, 0], [2, 0], [3, 1], [3, 2]])
    assert result[0] == 0 and result[-1] == 3
    assert s.findOrder(2, [[1, 0], [0, 1]]) == []
    assert s.findOrder(1, []) == [0]

    assert s.findOrder_dfs(2, [[1, 0]]) == [0, 1]
    assert s.findOrder_dfs(2, [[1, 0], [0, 1]]) == []
    print("All tests passed.")

from typing import List
from collections import deque


class Solution:
    """
    ## 1462. Course Schedule IV

    There are `numCourses` courses labeled `0` to `numCourses - 1`. You are given
    an array `prerequisites` where `prerequisites[i] = [ai, bi]` means course `ai`
    must be taken before course `bi`.

    Given a list of `queries` where `queries[j] = [uj, vj]`, answer whether course
    `uj` is a prerequisite of course `vj` (directly or indirectly).

    ### Examples

    ```text
    Input:  numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
    Output: [false, true]

    Input:  numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]]
    Output: [false, false]

    Input:  numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
    Output: [true, true]
    ```

    ### Constraints

    - `2 <= numCourses <= 100`
    - `0 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)`
    - `prerequisites[i].length == 2`
    - `0 <= ai, bi < numCourses`
    - `ai != bi`
    - All prerequisite pairs are distinct.
    - `1 <= queries.length <= 10^4`
    """

    def checkIfPrerequisite_bfs(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        # O(V*(V+E)) time, O(V^2) space
        graph = [[] for _ in range(numCourses)]
        for a, b in prerequisites:
            graph[a].append(b)

        def can_reach(src: int, dst: int) -> bool:
            visited = set()
            queue = deque([src])
            while queue:
                node = queue.popleft()
                if node == dst:
                    return True
                for nei in graph[node]:
                    if nei not in visited:
                        visited.add(nei)
                        queue.append(nei)
            return False

        return [can_reach(u, v) for u, v in queries]

    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
        # Build reachability matrix via DFS/BFS or Floyd-Warshall
        # reachable[u][v] = True if u can reach v through prerequisites
        # O(V^3) time, O(V^2) space — Floyd-Warshall transitive closure
        reach = [[False] * numCourses for _ in range(numCourses)]
        for a, b in prerequisites:
            reach[a][b] = True
        for k in range(numCourses):
            for i in range(numCourses):
                for j in range(numCourses):
                    if reach[i][k] and reach[k][j]:
                        reach[i][j] = True
        return [reach[u][v] for u, v in queries]


if __name__ == '__main__':
    s = Solution()
    assert s.checkIfPrerequisite(2, [[1, 0]], [[0, 1], [1, 0]]) == [False, True]
    assert s.checkIfPrerequisite(2, [], [[1, 0], [0, 1]]) == [False, False]
    assert s.checkIfPrerequisite(3, [[1, 2], [1, 0], [2, 0]], [[1, 0], [1, 2]]) == [True, True]

    assert s.checkIfPrerequisite_bfs(2, [[1, 0]], [[0, 1], [1, 0]]) == [False, True]
    assert s.checkIfPrerequisite_bfs(3, [[1, 2], [1, 0], [2, 0]], [[1, 0], [1, 2]]) == [True, True]
    print("All tests passed.")

"""
# LC 542: 01 Matrix (Distance of Nearest 0)

For each cell in a binary matrix, find the distance to the nearest `0`, where
distance is the number of 4-directional steps.

## Examples
```text
Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]

Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]
```

## Constraints
- A cell that is already `0` has distance 0.
- Use multi-source BFS from all `0` cells simultaneously.
- At least one `0` is present in the matrix.
"""
from typing import List
from collections import deque

class Solution:
    # Multi-source BFS: start from ALL 0s simultaneously, expand outward
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        rows, cols = len(mat), len(mat[0])
        dist = [[float('inf')] * cols for _ in range(rows)]
        queue = deque()

        # initialize BFS with all 0-cells at distance 0
        for r in range(rows):
            for c in range(cols):
                if mat[r][c] == 0:
                    dist[r][c] = 0
                    queue.append((r, c))

        # BFS expands layer by layer - first time we reach a 1-cell is shortest distance
        while queue:
            r, c = queue.popleft()
            for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols:
                    if dist[nr][nc] > dist[r][c] + 1:
                        dist[nr][nc] = dist[r][c] + 1
                        queue.append((nr, nc))

        return dist


if __name__ == "__main__":
    s = Solution()
    assert s.updateMatrix([[0,0,0],[0,1,0],[1,1,1]]) == [[0,0,0],[0,1,0],[1,2,1]]
    assert s.updateMatrix([[0,0,0],[0,1,0],[0,0,0]]) == [[0,0,0],[0,1,0],[0,0,0]]
    print("All tests passed.")

from typing import List
from collections import defaultdict, deque


class Solution:
    """
    ## 399. Evaluate Division

    You are given an array of variable pairs `equations` and an array of real numbers
    `values`, where `equations[i] = [Ai, Bi]` and `values[i]` represent the equation
    `Ai / Bi = values[i]`.

    Given some `queries`, where `queries[j] = [Cj, Dj]`, return the answers to all
    queries. If the answer does not exist, return `-1.0`.

    ### Examples

    ```text
    Input:
      equations = [["a","b"],["b","c"]], values = [2.0,3.0]
      queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
    Output: [6.0, 0.5, -1.0, 1.0, -1.0]

    Input:
      equations = [["a","b"],["b","c"]], values = [2.0,3.0]
      queries = [["a","c"]]
    Output: [6.0]
    ```

    ### Constraints

    - `1 <= equations.length <= 20`
    - `equations[i].length == 2`
    - `1 <= Ai.length, Bi.length <= 5`
    - `values[i] > 0.0`
    - `1 <= queries.length <= 20`
    """

    def calcEquation_bfs(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        # O(Q*(V+E)) time, O(V+E) space
        graph: dict = defaultdict(dict)
        for (a, b), val in zip(equations, values):
            graph[a][b] = val
            graph[b][a] = 1.0 / val

        def bfs(src: str, dst: str) -> float:
            if src not in graph or dst not in graph:
                return -1.0
            if src == dst:
                return 1.0
            visited = set()
            queue = deque([(src, 1.0)])
            visited.add(src)
            while queue:
                node, product = queue.popleft()
                if node == dst:
                    return product
                for nei, weight in graph[node].items():
                    if nei not in visited:
                        visited.add(nei)
                        queue.append((nei, product * weight))
            return -1.0

        return [bfs(c, d) for c, d in queries]

    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        # Build weighted graph: a/b=k means edge a->b with weight k, b->a with 1/k
        # BFS/DFS for each query to find the product of weights along the path
        # O(E*alpha(V) + Q) time, O(V) space — Union-Find with weights
        parent: dict = {}
        weight: dict = {}  # weight[x] = x / find(x)

        def find(x: str):
            if x not in parent:
                parent[x] = x
                weight[x] = 1.0
            if parent[x] != x:
                root, w = find(parent[x])
                parent[x] = root
                weight[x] *= w
            return parent[x], weight[x]

        def union(x: str, y: str, val: float) -> None:
            rx, wx = find(x)
            ry, wy = find(y)
            if rx != ry:
                parent[rx] = ry
                weight[rx] = val * wy / wx

        for (a, b), val in zip(equations, values):
            union(a, b, val)

        results = []
        for c, d in queries:
            if c not in parent or d not in parent:
                results.append(-1.0)
            else:
                rc, wc = find(c)
                rd, wd = find(d)
                results.append(wc / wd if rc == rd else -1.0)
        return results


if __name__ == '__main__':
    s = Solution()
    eq = [["a", "b"], ["b", "c"]]
    vals = [2.0, 3.0]
    queries = [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]]
    expected = [6.0, 0.5, -1.0, 1.0, -1.0]

    res = s.calcEquation_bfs(eq, vals, queries)
    assert res == expected, res

    res2 = s.calcEquation(eq, vals, [["a", "c"]])
    assert abs(res2[0] - 6.0) < 1e-9
    print("All tests passed.")

"""
# LC 802: Find Eventual Safe States

Return, in ascending order, all nodes of a directed graph from which every
path eventually leads to a terminal node (no cycle is reachable).

## Examples
```text
Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output: [2,4,5,6]

Input: graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
Output: [4]
```

## Constraints
- A node with no outgoing edges is always safe (terminal).
- If all nodes form one cycle, return `[]`.
- Handle disconnected components.
"""
from typing import List
from collections import deque

class Solution:
    # Approach 1: DFS with 3-color marking (0=unvisited, 1=in-stack, 2=safe)
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        state = [0] * n  # 0=unvisited, 1=visiting(in cycle path), 2=safe

        def dfs(node) -> bool:
            if state[node] == 1: return False  # back edge = cycle
            if state[node] == 2: return True   # already confirmed safe
            state[node] = 1  # mark as being visited
            for neighbor in graph[node]:
                if not dfs(neighbor):
                    return False  # neighbor leads to cycle
            state[node] = 2  # all neighbors safe, mark safe
            return True

        return [i for i in range(n) if dfs(i)]

    # Approach 2: Reverse graph + topological sort (Kahn's)
    def eventualSafeNodes_topo(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        rev = [[] for _ in range(n)]
        out_degree = [0] * n

        for u in range(n):
            for v in graph[u]:
                rev[v].append(u)  # reverse edge
            out_degree[u] = len(graph[u])

        # nodes with out_degree 0 are terminal (safe)
        queue = deque(i for i in range(n) if out_degree[i] == 0)
        safe = set()

        while queue:
            node = queue.popleft()
            safe.add(node)
            for parent in rev[node]:
                out_degree[parent] -= 1
                if out_degree[parent] == 0:
                    queue.append(parent)

        return sorted(safe)


if __name__ == "__main__":
    s = Solution()
    assert s.eventualSafeNodes([[1,2],[2,3],[5],[0],[5],[],[]]) == [2,4,5,6]
    assert s.eventualSafeNodes([[1,2,3,4],[1,2],[3,4],[0,4],[]]) == [4]
    assert s.eventualSafeNodes_topo([[1,2],[2,3],[5],[0],[5],[],[]]) == [2,4,5,6]
    assert s.eventualSafeNodes_topo([[1,2,3,4],[1,2],[3,4],[0,4],[]]) == [4]
    print("All tests passed.")

"""
# 997. Find the Town Judge

## Problem
In a town, there are `n` people labeled from `1` to `n`. There is a rumor that one of
these people is secretly the town judge. If the town judge exists, then:
1. The town judge trusts nobody.
2. Everybody (except the town judge) trusts the town judge.
3. There is exactly one person that satisfies properties 1 and 2.

Given an array `trust` where `trust[i] = [a, b]` means person `a` trusts person `b`,
return the label of the town judge if the town judge exists, otherwise return `-1`.

## Examples
```text
Input:  n = 2, trust = [[1,2]]
Output: 2
```

```text
Input:  n = 3, trust = [[1,3],[2,3]]
Output: 3
```

```text
Input:  n = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1
```

## Constraints
- `1 <= n <= 1000`
- `0 <= trust.length <= 10^4`
- `trust[i].length == 2`
- All the pairs in `trust` are unique
- `a != b`
"""

from typing import List


class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        # Judge trusts nobody (out-degree 0) and is trusted by everyone else (in-degree n-1)
        # Track trust counts: net_trust[i] = in_degree[i] - out_degree[i]; judge has n-1
        # O(n+e) time, O(n) space — net trust score: +1 for being trusted, -1 for trusting
        score = [0] * (n + 1)
        for a, b in trust:
            score[a] -= 1
            score[b] += 1
        for person in range(1, n + 1):
            if score[person] == n - 1:
                return person
        return -1


if __name__ == '__main__':
    s = Solution()
    assert s.findJudge(2, [[1,2]]) == 2
    assert s.findJudge(3, [[1,3],[2,3]]) == 3
    assert s.findJudge(3, [[1,3],[2,3],[3,1]]) == -1
    assert s.findJudge(1, []) == 1
    print("All tests passed.")

"""
# LC 733: Flood Fill

Starting from pixel `(sr, sc)`, change all 4-directionally connected pixels
that share the same original color to `color`, and return the image.

## Examples
```text
Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]

Input: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0
Output: [[0,0,0],[0,0,0]]
```

## Constraints
- If the starting pixel already has the target color, return as-is (no-op).
- A single-pixel image just changes that pixel.
- Only pixels connected to the start with the original color are repainted.
"""
from typing import List

class Solution:
    # DFS flood fill - change all connected same-color pixels to new color
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        original = image[sr][sc]
        if original == color:
            return image  # edge case: already the target color, avoid infinite loop

        rows, cols = len(image), len(image[0])

        def dfs(r, c):
            if r < 0 or r >= rows or c < 0 or c >= cols:
                return
            if image[r][c] != original:
                return
            image[r][c] = color  # paint in-place
            dfs(r + 1, c)
            dfs(r - 1, c)
            dfs(r, c + 1)
            dfs(r, c - 1)

        dfs(sr, sc)
        return image


if __name__ == "__main__":
    s = Solution()
    assert s.floodFill([[1,1,1],[1,1,0],[1,0,1]], 1, 1, 2) == [[2,2,2],[2,2,0],[2,0,1]]
    assert s.floodFill([[0,0,0],[0,0,0]], 0, 0, 0) == [[0,0,0],[0,0,0]]
    print("All tests passed.")

from typing import List
from collections import deque


class Solution:
    """
    ## 261. Graph Valid Tree

    You have `n` nodes labeled from `0` to `n - 1` and a list of undirected edges.
    Write a function to check whether these edges make up a valid tree.

    A valid tree must be connected and contain no cycles.

    ### Examples

    ```text
    Input:  n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
    Output: true

    Input:  n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
    Output: false
    ```

    ### Constraints

    - `1 <= n <= 2000`
    - `0 <= edges.length <= 5000`
    - `edges[i].length == 2`
    - `0 <= ai, bi < n`
    - `ai != bi`
    - No self-loops or repeated edges.
    """

    def validTree_bfs(self, n: int, edges: List[List[int]]) -> bool:
        # O(V+E) time, O(V+E) space
        if len(edges) != n - 1:
            return False
        graph = [[] for _ in range(n)]
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)

        visited = set()
        queue = deque([0])
        visited.add(0)
        while queue:
            node = queue.popleft()
            for nei in graph[node]:
                if nei not in visited:
                    visited.add(nei)
                    queue.append(nei)
        return len(visited) == n

    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        # A valid tree has exactly n-1 edges and is fully connected (no cycles)
        # Union-Find: if any edge connects already-connected nodes, it's a cycle
        # O(V+E) time, O(V) space — Union-Find
        if len(edges) != n - 1:
            return False
        parent = list(range(n))
        rank = [0] * n

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        def union(x: int, y: int) -> bool:
            px, py = find(x), find(y)
            if px == py:
                return False
            if rank[px] < rank[py]:
                px, py = py, px
            parent[py] = px
            if rank[px] == rank[py]:
                rank[px] += 1
            return True

        return all(union(a, b) for a, b in edges)


if __name__ == '__main__':
    s = Solution()
    assert s.validTree(5, [[0, 1], [0, 2], [0, 3], [1, 4]]) is True
    assert s.validTree(5, [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]) is False
    assert s.validTree(1, []) is True
    assert s.validTree(4, [[0, 1], [2, 3]]) is False

    assert s.validTree_bfs(5, [[0, 1], [0, 2], [0, 3], [1, 4]]) is True
    assert s.validTree_bfs(5, [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]) is False
    print("All tests passed.")

"""
# 463. Island Perimeter

## Problem
You are given `row x col` grid representing a map where `grid[i][j] = 1` represents land
and `grid[i][j] = 0` represents water. Grid cells are connected horizontally/vertically.
There is exactly one island (no lakes). Return the perimeter of the island.

## Examples
```text
Input:  grid = [[0,1,0,0],
                [1,1,1,0],
                [0,1,0,0],
                [1,1,0,0]]
Output: 16
```

```text
Input:  grid = [[1]]
Output: 4
```

```text
Input:  grid = [[1,0]]
Output: 4
```

## Constraints
- `row == grid.length`
- `col == grid[i].length`
- `1 <= row, col <= 100`
- `grid[i][j]` is `0` or `1`
- There is exactly one island in `grid`
"""

from typing import List
from collections import deque


class Solution:
    def islandPerimeter_counting(self, grid: List[List[int]]) -> int:
        # O(m*n) time, O(1) space
        rows, cols = len(grid), len(grid[0])
        perimeter = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    perimeter += 4
                    if r > 0 and grid[r-1][c] == 1:
                        perimeter -= 2
                    if c > 0 and grid[r][c-1] == 1:
                        perimeter -= 2
        return perimeter

    def islandPerimeter(self, grid: List[List[int]]) -> int:
        # For each land cell, add 4 sides; subtract 2 for each shared edge with neighbor
        # O(m*n) time, O(m*n) space — DFS
        rows, cols = len(grid), len(grid[0])
        visited = set()

        def dfs(r, c):
            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 0:
                return 1
            if (r, c) in visited:
                return 0
            visited.add((r, c))
            return dfs(r+1, c) + dfs(r-1, c) + dfs(r, c+1) + dfs(r, c-1)

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    return dfs(r, c)
        return 0


if __name__ == '__main__':
    s = Solution()
    assert s.islandPerimeter([[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]) == 16
    assert s.islandPerimeter([[1]]) == 4
    assert s.islandPerimeter([[1,0]]) == 4
    assert s.islandPerimeter_counting([[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]) == 16
    print("All tests passed.")

"""
# 695. Max Area of Island

## Problem
You are given an `m x n` binary matrix `grid`. An island is a group of `1`s (representing
land) connected 4-directionally (horizontal or vertical). The area of an island is the
number of cells with value `1` in the island. Return the maximum area of an island in
`grid`. If there is no island, return `0`.

## Examples
```text
Input:  grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],
                [0,0,0,0,0,0,0,1,1,1,0,0,0],
                [0,1,1,0,1,0,0,0,0,0,0,0,0],
                [0,1,0,0,1,1,0,0,1,0,1,0,0],
                [0,1,0,0,1,1,0,0,1,1,1,0,0],
                [0,0,0,0,0,0,0,0,0,0,1,0,0],
                [0,0,0,0,0,0,0,1,1,1,0,0,0],
                [0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6
```

```text
Input:  grid = [[0,0,0,0,0,0,0,0]]
Output: 0
```

## Constraints
- `m == grid.length`
- `n == grid[i].length`
- `1 <= m, n <= 50`
- `grid[i][j]` is `0` or `1`
"""

from typing import List
from collections import deque


class Solution:
    def maxAreaOfIsland_dfs(self, grid: List[List[int]]) -> int:
        # O(m*n) time, O(m*n) space — DFS flood fill tracking area
        rows, cols = len(grid), len(grid[0])

        def dfs(r, c):
            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != 1:
                return 0
            grid[r][c] = 0
            return 1 + dfs(r+1,c) + dfs(r-1,c) + dfs(r,c+1) + dfs(r,c-1)

        return max(dfs(r, c) for r in range(rows) for c in range(cols) if grid[r][c] == 1) or 0

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        # DFS flood fill: return size of each island; track global maximum
        # O(m*n) time, O(m*n) space — BFS flood fill tracking area
        rows, cols = len(grid), len(grid[0])
        best = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    grid[r][c] = 0
                    area, q = 1, deque([(r, c)])
                    while q:
                        cr, cc = q.popleft()
                        for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                            nr, nc = cr+dr, cc+dc
                            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                                grid[nr][nc] = 0
                                area += 1
                                q.append((nr, nc))
                    best = max(best, area)
        return best


if __name__ == '__main__':
    import copy
    s = Solution()
    g = [[0,0,1,0,0,0,0,1,0,0,0,0,0],
         [0,0,0,0,0,0,0,1,1,1,0,0,0],
         [0,1,1,0,1,0,0,0,0,0,0,0,0],
         [0,1,0,0,1,1,0,0,1,0,1,0,0],
         [0,1,0,0,1,1,0,0,1,1,1,0,0],
         [0,0,0,0,0,0,0,0,0,0,1,0,0],
         [0,0,0,0,0,0,0,1,1,1,0,0,0],
         [0,0,0,0,0,0,0,1,1,0,0,0,0]]
    assert s.maxAreaOfIsland_dfs(copy.deepcopy(g)) == 6
    assert s.maxAreaOfIsland(copy.deepcopy(g)) == 6
    assert s.maxAreaOfIsland([[0,0,0,0,0,0,0,0]]) == 0
    print("All tests passed.")

from typing import List
from collections import deque


class Solution:
    """
    ## 310. Minimum Height Trees

    A tree is an undirected graph in which any two vertices are connected by exactly
    one path. Given a tree of `n` nodes labeled from `0` to `n - 1`, and an array of
    `n - 1` edges, find all the nodes that can be the root of a Minimum Height Tree (MHT).

    Return a list of all MHT root labels. You may return the answer in any order.

    ### Examples

    ```text
    Input:  n = 4, edges = [[1,0],[1,2],[1,3]]
    Output: [1]

    Input:  n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
    Output: [3,4]

    Input:  n = 1, edges = []
    Output: [0]
    ```

    ### Constraints

    - `1 <= n <= 2 * 10^4`
    - `edges.length == n - 1`
    - `0 <= ai, bi < n`
    - `ai != bi`
    - All pairs `(ai, bi)` are distinct.
    - The given input is guaranteed to be a tree.
    """

    def findMinHeightTrees_brute(self, n: int, edges: List[List[int]]) -> List[int]:
        # O(V^2) time, O(V+E) space — BFS from each node
        if n == 1:
            return [0]
        graph = [[] for _ in range(n)]
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)

        def bfs_height(root: int) -> int:
            visited = {root}
            queue = deque([root])
            height = 0
            while queue:
                for _ in range(len(queue)):
                    node = queue.popleft()
                    for nei in graph[node]:
                        if nei not in visited:
                            visited.add(nei)
                            queue.append(nei)
                height += 1
            return height

        min_h = float('inf')
        heights = []
        for i in range(n):
            h = bfs_height(i)
            heights.append(h)
            min_h = min(min_h, h)
        return [i for i, h in enumerate(heights) if h == min_h]

    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        # Iteratively remove leaf nodes (degree 1) layer by layer
        # The remaining 1 or 2 nodes are the roots of minimum height trees
        # O(V+E) time, O(V+E) space — iterative leaf removal
        if n == 1:
            return [0]
        graph = [set() for _ in range(n)]
        for a, b in edges:
            graph[a].add(b)
            graph[b].add(a)

        leaves = deque(i for i in range(n) if len(graph[i]) == 1)
        remaining = n
        while remaining > 2:
            remaining -= len(leaves)
            new_leaves = deque()
            for leaf in leaves:
                nei = next(iter(graph[leaf]))
                graph[nei].remove(leaf)
                if len(graph[nei]) == 1:
                    new_leaves.append(nei)
            leaves = new_leaves
        return list(leaves)


if __name__ == '__main__':
    s = Solution()
    assert s.findMinHeightTrees(4, [[1, 0], [1, 2], [1, 3]]) == [1]
    assert sorted(s.findMinHeightTrees(6, [[3, 0], [3, 1], [3, 2], [3, 4], [5, 4]])) == [3, 4]
    assert s.findMinHeightTrees(1, []) == [0]

    assert s.findMinHeightTrees_brute(4, [[1, 0], [1, 2], [1, 3]]) == [1]
    assert sorted(s.findMinHeightTrees_brute(6, [[3, 0], [3, 1], [3, 2], [3, 4], [5, 4]])) == [3, 4]
    print("All tests passed.")

from typing import List


class Solution:
    """
    ## 323. Number of Connected Components in an Undirected Graph

    You have `n` nodes labeled from `0` to `n - 1` and a list of undirected edges.
    Write a function to find the number of connected components in the graph.

    ### Examples

    ```text
    Input:  n = 5, edges = [[0,1],[1,2],[3,4]]
    Output: 2

    Input:  n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
    Output: 1
    ```

    ### Constraints

    - `1 <= n <= 2000`
    - `1 <= edges.length <= 5000`
    - `edges[i].length == 2`
    - `0 <= ai, bi < n`
    - `ai != bi`
    - No repeated edges.
    """

    def countComponents_dfs(self, n: int, edges: List[List[int]]) -> int:
        # O(V+E) time, O(V+E) space
        graph = [[] for _ in range(n)]
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)

        visited = [False] * n

        def dfs(node: int) -> None:
            visited[node] = True
            for nei in graph[node]:
                if not visited[nei]:
                    dfs(nei)

        count = 0
        for i in range(n):
            if not visited[i]:
                dfs(i)
                count += 1
        return count

    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        # Union-Find or DFS: count distinct connected components
        # O(V+E) time, O(V) space — Union-Find
        parent = list(range(n))
        rank = [0] * n

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        def union(x: int, y: int) -> bool:
            px, py = find(x), find(y)
            if px == py:
                return False
            if rank[px] < rank[py]:
                px, py = py, px
            parent[py] = px
            if rank[px] == rank[py]:
                rank[px] += 1
            return True

        components = n
        for a, b in edges:
            if union(a, b):
                components -= 1
        return components


if __name__ == '__main__':
    s = Solution()
    assert s.countComponents(5, [[0, 1], [1, 2], [3, 4]]) == 2
    assert s.countComponents(5, [[0, 1], [1, 2], [2, 3], [3, 4]]) == 1
    assert s.countComponents(3, []) == 3

    assert s.countComponents_dfs(5, [[0, 1], [1, 2], [3, 4]]) == 2
    assert s.countComponents_dfs(5, [[0, 1], [1, 2], [2, 3], [3, 4]]) == 1
    print("All tests passed.")

"""
# LC 1020: Number of Enclaves

Count land cells (`1`s) from which you cannot walk off the boundary of the
grid by moving 4-directionally.

## Examples
```text
Input: grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
Output: 3

Input: grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
Output: 0
```

## Constraints
- If no land touches the boundary, all land cells are enclaves.
- If all land connects to the boundary, the answer is 0.
- A grid with no land yields 0.
"""
from typing import List
from collections import deque

class Solution:
    # BFS from all boundary land cells, mark reachable land, count unmarked land
    def numEnclaves(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        queue = deque()

        # seed BFS with all boundary land cells
        for r in range(rows):
            for c in range(cols):
                if (r == 0 or r == rows - 1 or c == 0 or c == cols - 1) and grid[r][c] == 1:
                    queue.append((r, c))
                    grid[r][c] = 0  # mark visited by sinking to 0

        # flood-fill from boundary - sink all connected land
        while queue:
            r, c = queue.popleft()
            for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 0
                    queue.append((nr, nc))

        # remaining 1s are enclaves (not reachable from boundary)
        return sum(grid[r][c] for r in range(rows) for c in range(cols))


if __name__ == "__main__":
    s = Solution()
    assert s.numEnclaves([[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]) == 3
    assert s.numEnclaves([[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]) == 0
    print("All tests passed.")

"""
# 200. Number of Islands

## Problem
Given an `m x n` 2D binary grid `grid` which represents a map of `'1'`s (land) and
`'0'`s (water), return the number of islands. An island is surrounded by water and is
formed by connecting adjacent lands horizontally or vertically.

## Examples
```text
Input:  grid = [["1","1","1","1","0"],
                ["1","1","0","1","0"],
                ["1","1","0","0","0"],
                ["0","0","0","0","0"]]
Output: 1
```

```text
Input:  grid = [["1","1","0","0","0"],
                ["1","1","0","0","0"],
                ["0","0","1","0","0"],
                ["0","0","0","1","1"]]
Output: 3
```

## Constraints
- `m == grid.length`
- `n == grid[i].length`
- `1 <= m, n <= 300`
- `grid[i][j]` is `'0'` or `'1'`
"""

from typing import List
from collections import deque


class Solution:
    def numIslands_dfs(self, grid: List[List[str]]) -> int:
        # DFS flood fill: mark visited cells as '0' to avoid revisiting
        # Each DFS call from an unvisited '1' cell counts as one island
        # O(m*n) time, O(m*n) space — DFS flood fill
        rows, cols = len(grid), len(grid[0])

        def dfs(r, c):
            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
                return
            grid[r][c] = '0'
            dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)

        count = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1':
                    dfs(r, c)
                    count += 1
        return count

    def numIslands_bfs(self, grid: List[List[str]]) -> int:
        # BFS flood fill: same idea but uses a queue instead of recursion
        # O(m*n) time, O(min(m,n)) space — BFS flood fill
        rows, cols = len(grid), len(grid[0])
        count = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1':
                    count += 1
                    grid[r][c] = '0'
                    q = deque([(r, c)])
                    while q:
                        cr, cc = q.popleft()
                        for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                            nr, nc = cr+dr, cc+dc
                            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                                grid[nr][nc] = '0'
                                q.append((nr, nc))
        return count

    def numIslands(self, grid: List[List[str]]) -> int:
        # Union-Find: union adjacent land cells; count distinct components
        # O(m*n) time, O(m*n) space — Union-Find
        rows, cols = len(grid), len(grid[0])
        parent = list(range(rows * cols))
        rank = [0] * (rows * cols)

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

        def union(x, y):
            px, py = find(x), find(y)
            if px == py:
                return False
            if rank[px] < rank[py]:
                px, py = py, px
            parent[py] = px
            if rank[px] == rank[py]:
                rank[px] += 1
            return True

        count = sum(grid[r][c] == '1' for r in range(rows) for c in range(cols))
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1':
                    for dr, dc in [(1,0),(0,1)]:
                        nr, nc = r+dr, c+dc
                        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                            if union(r*cols+c, nr*cols+nc):
                                count -= 1
        return count


if __name__ == '__main__':
    import copy
    s = Solution()
    g1 = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]
    g2 = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]
    assert s.numIslands(copy.deepcopy(g1)) == 3
    assert s.numIslands(copy.deepcopy(g2)) == 1
    assert s.numIslands_dfs(copy.deepcopy(g1)) == 3
    assert s.numIslands_bfs(copy.deepcopy(g1)) == 3
    print("All tests passed.")