# 邻接矩阵：适合稠密图
adj_matrix = [
    [0, 1, 0, 1],
    [1, 0, 1, 0],
    [0, 1, 0, 1],
    [1, 0, 1, 0]
]

# 邻接表：适合稀疏图（大多数面试题）
from collections import defaultdict
adj_list = defaultdict(list)
edges = [[0, 1], [0, 3], [1, 2], [2, 3]]
for u, v in edges:
    adj_list[u].append(v)
    adj_list[v].append(u)  # 无向图

from collections import deque

def bfs(graph, start):
    """BFS 求最短路径（无权图）"""
    visited = {start}
    queue = deque([(start, 0)])
    while queue:
        node, dist = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    return visited

def dfs(graph, node, visited):
    """DFS 遍历（递归版）"""
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

from collections import deque, defaultdict

def canFinish(numCourses, prerequisites):
    # 构建图和入度数组
    graph = defaultdict(list)
    indegree = [0] * numCourses
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        indegree[course] += 1

    # 入度为 0 的节点入队
    queue = deque([i for i, d in enumerate(indegree) if d == 0])
    visited = 0

    while queue:
        node = queue.popleft()
        visited += 1
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    return visited == numCourses

def alienOrder(words):
    # 构建有向图和入度
    chars = set(''.join(words))
    graph = {c: [] for c in chars}
    indegree = {c: 0 for c in chars}

    for i in range(len(words) - 1):
        w1, w2 = words[i], words[i + 1]
        # 检查前缀问题：["abc", "ab"] 非法
        if len(w1) > len(w2) and w1[:len(w2)] == w2:
            return ""
        for a, b in zip(w1, w2):
            if a != b:
                graph[a].append(b)
                indegree[b] += 1
                break

    # Kahn 拓扑排序
    queue = deque([c for c in chars if indegree[c] == 0])
    result = []
    while queue:
        c = queue.popleft()
        result.append(c)
        for neighbor in graph[c]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    return ''.join(result) if len(result) == len(chars) else ""

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n  # 连通分量数

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路径压缩
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return
        # 按秩合并
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        self.count -= 1

def findCircleNum(isConnected):
    n = len(isConnected)
    uf = UnionFind(n)
    for i in range(n):
        for j in range(i + 1, n):
            if isConnected[i][j] == 1:
                uf.union(i, j)
    return uf.count

def findRedundantConnection(edges):
    n = len(edges)
    uf = UnionFind(n + 1)
    for u, v in edges:
        if uf.find(u) == uf.find(v):
            return [u, v]
        uf.union(u, v)
    return []

import heapq
from collections import defaultdict

def networkDelayTime(times, n, k):
    # 构建图
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))

    # Dijkstra
    dist = {i: float('inf') for i in range(1, n + 1)}
    dist[k] = 0
    pq = [(0, k)]

    while pq:
        d, node = heapq.heappop(pq)
        if d > dist[node]:
            continue
        for neighbor, weight in graph[node]:
            new_dist = d + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))

    max_dist = max(dist.values())
    return max_dist if max_dist < float('inf') else -1

def findCheapestPrice(n, flights, src, dst, k):
    # Bellman-Ford: dist[i][v] = 最多 i 条边到达 v 的最小成本
    dist = [float('inf')] * n
    dist[src] = 0

    for _ in range(k + 1):
        new_dist = dist[:]
        for u, v, w in flights:
            if dist[u] + w < new_dist[v]:
                new_dist[v] = dist[u] + w
        dist = new_dist

    return dist[dst] if dist[dst] < float('inf') else -1

def minCostConnectPoints(points):
    n = len(points)
    # 构建所有边
    edges = []
    for i in range(n):
        for j in range(i + 1, n):
            dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
            edges.append((dist, i, j))

    edges.sort()
    uf = UnionFind(n)
    cost = 0
    edges_used = 0

    for dist, u, v in edges:
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            cost += dist
            edges_used += 1
            if edges_used == n - 1:
                break

    return cost

import heapq

def minCostConnectPointsPrim(points):
    n = len(points)
    visited = [False] * n
    # (cost, node)
    pq = [(0, 0)]
    total_cost = 0
    edges_used = 0

    while edges_used < n:
        cost, node = heapq.heappop(pq)
        if visited[node]:
            continue
        visited[node] = True
        total_cost += cost
        edges_used += 1

        for neighbor in range(n):
            if not visited[neighbor]:
                dist = abs(points[node][0] - points[neighbor][0]) + \
                       abs(points[node][1] - points[neighbor][1])
                heapq.heappush(pq, (dist, neighbor))

    return total_cost

from collections import deque

def ladderLength(beginWord, endWord, wordList):
    wordSet = set(wordList)
    if endWord not in wordSet:
        return 0

    # 双向 BFS
    front = {beginWord}
    back = {endWord}
    length = 1

    while front:
        # 每次都从较小的一端扩展
        if len(front) > len(back):
            front, back = back, front

        next_front = set()
        for word in front:
            for i in range(len(word)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    next_word = word[:i] + c + word[i+1:]
                    if next_word in back:
                        return length + 1
                    if next_word in wordSet:
                        next_front.add(next_word)
                        wordSet.remove(next_word)

        front = next_front
        length += 1

    return 0

def numIslands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    count = 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'  # 标记已访问
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            dfs(r + dr, c + dc)

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