图算法：表示与遍历

# 邻接矩阵实现（Python）：稠密图场景
class GraphMatrix:
    """邻接矩阵表示的加权图

    适用于稠密图（E = Theta(V^2)）与频繁查询边存在的场景。
    空间复杂度 Theta(V^2)，查询边存在 O(1)，遍历邻居 O(V)。
    """
    def __init__(self, n: int, directed: bool = False):
        # n: 顶点数；directed: 是否有向
        self.n = n
        self.directed = directed
        # 初始化为 0 表示无边；权值非 0 表示有边
        self.adj = [[0] * n for _ in range(n)]

    def add_edge(self, u: int, v: int, w: int = 1) -> None:
        """添加边 (u, v)，权为 w"""
        self.adj[u][v] = w
        if not self.directed:
            self.adj[v][u] = w

    def has_edge(self, u: int, v: int) -> bool:
        """O(1) 查询边是否存在"""
        return self.adj[u][v] != 0

    def neighbors(self, u: int) -> list:
        """遍历 u 的所有邻居，O(V)"""
        return [v for v in range(self.n) if self.adj[u][v] != 0]

// 邻接矩阵实现（C++）：稠密图场景
#include <vector>
class GraphMatrix {
    int n;
    bool directed;
    std::vector<std::vector<int>> adj;
public:
    GraphMatrix(int n, bool dir = false)
        : n(n), directed(dir), adj(n, std::vector<int>(n, 0)) {}

    void addEdge(int u, int v, int w = 1) {
        adj[u][v] = w;
        if (!directed) adj[v][u] = w;
    }

    bool hasEdge(int u, int v) const {
        return adj[u][v] != 0;
    }

    int weight(int u, int v) const {
        return adj[u][v];
    }
};

# 邻接表实现（Python）：稀疏图场景
from collections import defaultdict

class GraphList:
    """邻接表表示的加权图

    适用于稀疏图（E = O(V)）与遍历为主的场景。
    空间复杂度 Theta(V + E)，查询边存在 O(deg(u))，遍历邻居 O(deg(u))。
    """
    def __init__(self, n: int, directed: bool = False):
        self.n = n
        self.directed = directed
        # 每个顶点维护 (邻居, 权值) 列表
        self.adj = [[] for _ in range(n)]

    def add_edge(self, u: int, v: int, w: int = 1) -> None:
        self.adj[u].append((v, w))
        if not self.directed:
            self.adj[v].append((u, w))

    def neighbors(self, u: int) -> list:
        """O(deg(u)) 遍历邻居"""
        return self.adj[u]

    def has_edge(self, u: int, v: int) -> bool:
        """O(deg(u)) 查询边存在"""
        return any(node == v for node, _ in self.adj[u])

// 邻接表实现（C++）：稀疏图场景
#include <vector>
#include <utility>
class GraphList {
    int n;
    bool directed;
    std::vector<std::vector<std::pair<int, int>>> adj;
public:
    GraphList(int n, bool dir = false) : n(n), directed(dir), adj(n) {}

    void addEdge(int u, int v, int w = 1) {
        adj[u].emplace_back(v, w);
        if (!directed) adj[v].emplace_back(u, w);
    }

    const std::vector<std::pair<int, int>>& neighbors(int u) const {
        return adj[u];
    }
};

// 邻接表实现（Java）：稀疏图场景
import java.util.*;

public class GraphList {
    private int n;
    private boolean directed;
    private List<List<int[]>> adj;

    public GraphList(int n, boolean directed) {
        this.n = n;
        this.directed = directed;
        this.adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    }

    public void addEdge(int u, int v, int w) {
        adj.get(u).add(new int[]{v, w});
        if (!directed) adj.get(v).add(new int[]{u, w});
    }

    public List<int[]> neighbors(int u) {
        return adj.get(u);
    }
}

// 链式前向星实现（C++）：内存紧凑，竞赛常用
#include <cstring>
const int MAXN = 100010;
const int MAXM = 200010;

int head[MAXN];           // head[u] = u 的第一条边在 edges 数组中的下标
int nxt[MAXM];            // nxt[i] = 与 edges[i] 同起点的下一条边
int to[MAXM];             // edges[i] 的终点
int weight[MAXM];         // edges[i] 的权值
int edgeCnt = 0;          // 当前边数

void init() {
    std::memset(head, -1, sizeof(head));
    edgeCnt = 0;
}

void addEdge(int u, int v, int w) {
    to[edgeCnt] = v;
    weight[edgeCnt] = w;
    nxt[edgeCnt] = head[u];       // 新边指向原 head
    head[u] = edgeCnt++;          // 更新 head
}

// 遍历 u 的所有出边
void traverse(int u) {
    for (int e = head[u]; e != -1; e = nxt[e]) {
        int v = to[e];
        int w = weight[e];
        // 处理边 (u, v, w)
    }
}

# 边集数组（Python）：Bellman-Ford 与 Kruskal 的天然输入格式
edges = [
    (0, 1, 4),
    (0, 2, 1),
    (1, 3, 2),
    (2, 3, 5),
]
# 空间 Theta(E)；查询 (u, v) 是否有边需 O(E) 扫描
# 构建：读入 m 条边直接 append，无需任何索引结构

# 隐式图（Python）：4 连通网格的邻居生成函数，无需显式建图
def grid_neighbors(state, rows, cols, grid):
    """状态 (r, c) 的邻居按需生成；BFS/DFS 框架完全不变"""
    r, c = state
    for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0:
            yield (nr, nc)

# 标准输入构建无向加权图
def build_undirected_graph():
    """从标准输入读取 n 个顶点、m 条边构建无向加权图

    输入格式：
    第一行：n m
    后续 m 行：u v w（顶点编号从 0 开始）
    """
    n, m = map(int, input().split())
    g = GraphList(n, directed=False)
    for _ in range(m):
        u, v, w = map(int, input().split())
        g.add_edge(u, v, w)
    return g

from collections import deque

def bfs(n, graph, start):
    """广度优先搜索

    输入：顶点数 n、邻接表 graph、起始顶点 start
    输出：dist 数组（从 start 到各顶点的最短边数）、prev 数组（前驱）
    时间复杂度：O(V + E)
    """
    dist = [-1] * n
    prev = [-1] * n
    dist[start] = 0
    q = deque([start])
    while q:
        u = q.popleft()
        for v, _ in graph[u]:
            if dist[v] == -1:        # 未访问
                dist[v] = dist[u] + 1
                prev[v] = u
                q.append(v)
    return dist, prev

#include <queue>
#include <vector>
// BFS（C++ 实现）
std::vector<int> bfs(int n, std::vector<std::vector<std::pair<int,int>>>& graph, int start) {
    std::vector<int> dist(n, -1);
    std::vector<int> prev(n, -1);
    std::queue<int> q;
    dist[start] = 0;
    q.push(start);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto& [v, w] : graph[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                prev[v] = u;
                q.push(v);
            }
        }
    }
    return dist;
}

graph = [
    [(1, 1), (2, 1)],          # A 的邻居
    [(0, 1), (3, 1)],          # B
    [(0, 1), (3, 1), (4, 1)],  # C
    [(1, 1), (2, 1), (4, 1)],  # D
    [(2, 1), (3, 1)],          # E
]
dist, prev = bfs(5, graph, 0)
# 预期输出：
# dist = [0, 1, 1, 2, 2]    A 到 B、C 距离 1，到 D、E 距离 2
# prev = [-1, 0, 0, 1, 2]   最短路树：B<-A、C<-A、D<-B、E<-C

def dfs_recursive(n, graph, start):
    """DFS 递归实现

    输出：visited 数组、discovery/finish 时间戳
    时间复杂度：O(V + E)
    """
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n
    disc = [0] * n
    finish = [0] * n
    timer = [0]

    def dfs(u):
        timer[0] += 1
        disc[u] = timer[0]
        color[u] = GRAY
        for v, _ in graph[u]:
            if color[v] == WHITE:
                dfs(v)
        color[u] = BLACK
        timer[0] += 1
        finish[u] = timer[0]

    dfs(start)
    return disc, finish

def dfs_iterative(n, graph, start):
    """DFS 迭代实现，避免递归栈溢出

    注意：栈中需记录"下一个待访问邻居的下标"才能模拟递归回溯
    """
    visited = [False] * n
    order = []
    # 栈元素：(顶点, 下一个邻居下标)
    stack = [(start, 0)]
    visited[start] = True
    while stack:
        u, idx = stack[-1]
        if idx < len(graph[u]):
            stack[-1] = (u, idx + 1)
            v, _ = graph[u][idx]
            if not visited[v]:
                visited[v] = True
                stack.append((v, 0))
        else:
            stack.pop()
            order.append(u)
    return order

#include <vector>
#include <stack>
// DFS 迭代实现（C++）
std::vector<int> dfsIterative(int n, std::vector<std::vector<std::pair<int,int>>>& graph, int start) {
    std::vector<bool> visited(n, false);
    std::vector<int> order;
    std::stack<std::pair<int, int>> stk;   // (顶点, 下一个邻居下标)
    stk.push({start, 0});
    visited[start] = true;
    while (!stk.empty()) {
        auto& [u, idx] = stk.top();
        if (idx < (int)graph[u].size()) {
            int v = graph[u][idx].first;
            idx++;
            if (!visited[v]) {
                visited[v] = true;
                stk.push({v, 0});
            }
        } else {
            stk.pop();
            order.push_back(u);
        }
    }
    return order;
}

disc, finish = dfs_recursive(5, graph, 0)   # graph 与 5.1 节示例相同
# 预期输出（发现时间 disc）：
# disc = [1, 2, 4, 3, 5]
# 访问顺序：A(1) -> B(2) -> D(3) -> C(4) -> E(5)，深入到底再回溯
# 完成时间 finish = [10, 9, 7, 8, 6]，满足括号化定理：
# 区间 [1, 10] 包含其余所有区间

def connected_components(n, graph):
    """计算无向图连通分量

    时间复杂度：O(V + E)
    """
    visited = [False] * n
    components = []
    for s in range(n):
        if not visited[s]:
            comp = []
            stack = [s]
            visited[s] = True
            while stack:
                u = stack.pop()
                comp.append(u)
                for v, _ in graph[u]:
                    if not visited[v]:
                        visited[v] = True
                        stack.append(v)
            components.append(comp)
    return components

def has_cycle_undirected(n, graph):
    """无向图环检测（DFS）"""
    visited = [False] * n
    def dfs(u, parent):
        visited[u] = True
        for v, _ in graph[u]:
            if not visited[v]:
                if dfs(v, u):
                    return True
            elif v != parent:
                return True
        return False
    for s in range(n):
        if not visited[s]:
            if dfs(s, -1):
                return True
    return False

def is_bipartite(n, graph):
    """二分图判定（BFS 染色法）

    返回 True 当且仅当图不含奇环
    """
    color = [-1] * n
    from collections import deque
    for s in range(n):
        if color[s] == -1:
            color[s] = 0
            q = deque([s])
            while q:
                u = q.popleft()
                for v, _ in graph[u]:
                    if color[v] == -1:
                        color[v] = color[u] ^ 1
                        q.append(v)
                    elif color[v] == color[u]:
                        return False
    return True

from collections import deque

def topological_sort_kahn(n, graph):
    """Kahn 拓扑排序（BFS 入度法）

    输入：顶点数 n、邻接表 graph
    输出：拓扑序（若存在），否则 None
    时间复杂度：O(V + E)
    """
    in_degree = [0] * n
    for u in range(n):
        for v, _ in graph[u]:
            in_degree[v] += 1
    # 初始入度为 0 的顶点入队
    q = deque([i for i in range(n) if in_degree[i] == 0])
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v, _ in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                q.append(v)
    if len(order) != n:
        return None                # 存在环
    return order

#include <vector>
#include <queue>
// Kahn 拓扑排序（C++）
std::vector<int> topologicalSortKahn(int n, std::vector<std::vector<std::pair<int,int>>>& graph) {
    std::vector<int> inDegree(n, 0);
    for (int u = 0; u < n; u++) {
        for (auto& [v, w] : graph[u]) inDegree[v]++;
    }
    std::queue<int> q;
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) q.push(i);
    }
    std::vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (auto& [v, w] : graph[u]) {
            if (--inDegree[v] == 0) q.push(v);
        }
    }
    if ((int)order.size() != n) return {};     // 存在环
    return order;
}

def topological_sort_dfs(n, graph):
    """DFS 后序逆序拓扑排序

    关键观察：DAG 的 DFS 完成时间逆序即为合法拓扑序
    时间复杂度：O(V + E)
    """
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n
    order = []
    has_cycle = False

    def dfs(u):
        nonlocal has_cycle
        color[u] = GRAY
        for v, _ in graph[u]:
            if color[v] == WHITE:
                dfs(v)
            elif color[v] == GRAY:
                has_cycle = True        # 检测到回边，存在环
        color[u] = BLACK
        order.append(u)                 # 后序追加

    for s in range(n):
        if color[s] == WHITE:
            dfs(s)
    if has_cycle:
        return None
    return order[::-1]                  # 后序逆序

def dag_shortest_path(n, graph, start):
    """DAG 单源最短路径

    时间复杂度：O(V + E)
    支持负权边（无负环即 DAG 无环）
    """
    INF = float('inf')
    order = topological_sort_kahn(n, graph)
    if order is None:
        return None                     # 非 DAG
    dist = [INF] * n
    dist[start] = 0
    for u in order:
        if dist[u] == INF:
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist

def dag_longest_path(n, graph, start):
    """DAG 单源最长路径

    技巧：边权取负后求最短路径，再取反
    """
    neg_graph = [[(v, -w) for v, w in adj] for adj in graph]
    dist = dag_shortest_path(n, neg_graph, start)
    if dist is None:
        return None
    return [-d if d != float('inf') else float('inf') for d in dist]

def critical_path(n, graph, source, sink):
    """AOE 网关键路径算法

    输出：关键活动列表
    """
    order = topological_sort_kahn(n, graph)
    if order is None:
        return None
    INF = float('inf')
    # 正向计算 Ve
    Ve = [0] * n
    for u in order:
        for v, w in graph[u]:
            if Ve[u] + w > Ve[v]:
                Ve[v] = Ve[u] + w
    # 逆向计算 Vl
    Vl = [INF] * n
    Vl[sink] = Ve[sink]
    for u in reversed(order):
        for v, w in graph[u]:
            if Vl[v] - w < Vl[u]:
                Vl[u] = Vl[v] - w
    # 关键活动
    critical = []
    for u in range(n):
        for v, w in graph[u]:
            if Ve[u] + w == Vl[v]:
                critical.append((u, v, w))
    return critical

def tarjan_scc(n, graph):
    """Tarjan 强连通分量算法

    输入：顶点数 n、邻接表 graph
    输出：SCC 列表（每个 SCC 是顶点列表）
    时间复杂度：O(V + E)
    空间复杂度：O(V)
    """
    dfn = [0] * n
    low = [0] * n
    on_stack = [False] * n
    stack = []
    sccs = []
    timer = [0]

    def dfs(u):
        timer[0] += 1
        dfn[u] = low[u] = timer[0]
        stack.append(u)
        on_stack[u] = True
        for v in graph[u]:
            if dfn[v] == 0:                 # 树边
                dfs(v)
                low[u] = min(low[u], low[v])
            elif on_stack[v]:               # 回边或横叉边（v 在栈中）
                low[u] = min(low[u], dfn[v])
        # 若 u 是 SCC 根，弹出栈中 u 及其之上顶点
        if dfn[u] == low[u]:
            scc = []
            while True:
                v = stack.pop()
                on_stack[v] = False
                scc.append(v)
                if v == u:
                    break
            sccs.append(scc)

    for i in range(n):
        if dfn[i] == 0:
            dfs(i)
    return sccs

#include <vector>
#include <stack>
// Tarjan SCC（C++）
class TarjanSCC {
    int n;
    std::vector<std::vector<int>> graph;
    std::vector<int> dfn, low;
    std::vector<bool> onStack;
    std::stack<int> stk;
    std::vector<std::vector<int>> sccs;
    int timer = 0;
public:
    TarjanSCC(int n, std::vector<std::vector<int>>& g)
        : n(n), graph(g), dfn(n, 0), low(n, 0), onStack(n, false) {}

    void dfs(int u) {
        dfn[u] = low[u] = ++timer;
        stk.push(u);
        onStack[u] = true;
        for (int v : graph[u]) {
            if (dfn[v] == 0) {
                dfs(v);
                low[u] = std::min(low[u], low[v]);
            } else if (onStack[v]) {
                low[u] = std::min(low[u], dfn[v]);
            }
        }
        if (dfn[u] == low[u]) {
            std::vector<int> scc;
            int v;
            do {
                v = stk.top(); stk.pop();
                onStack[v] = false;
                scc.push_back(v);
            } while (v != u);
            sccs.push_back(scc);
        }
    }

    std::vector<std::vector<int>> run() {
        for (int i = 0; i < n; i++) {
            if (dfn[i] == 0) dfs(i);
        }
        return sccs;
    }
};

def kosaraju_scc(n, graph):
    """Kosaraju 强连通分量算法

    时间复杂度：O(V + E)
    空间复杂度：O(V + E)（需存储反图）
    """
    # 第一次 DFS：原图后序
    visited = [False] * n
    order = []
    def dfs1(u):
        visited[u] = True
        for v, _ in graph[u]:
            if not visited[v]:
                dfs1(v)
        order.append(u)
    for i in range(n):
        if not visited[i]:
            dfs1(i)
    # 构建反图
    rev_graph = [[] for _ in range(n)]
    for u in range(n):
        for v, _ in graph[u]:
            rev_graph[v].append(u)
    # 第二次 DFS：反图按后序逆序
    visited = [False] * n
    sccs = []
    def dfs2(u, scc):
        visited[u] = True
        scc.append(u)
        for v in rev_graph[u]:
            if not visited[v]:
                dfs2(v, scc)
    for u in reversed(order):
        if not visited[u]:
            scc = []
            dfs2(u, scc)
            sccs.append(scc)
    return sccs

def shrink_scc(n, graph, sccs):
    """SCC 缩点为 DAG

    输入：原图、SCC 列表
    输出：(SCC 编号数组 scc_id、DAG 邻接表)
    """
    scc_id = [-1] * n
    for i, scc in enumerate(sccs):
        for v in scc:
            scc_id[v] = i
    dag = [set() for _ in range(len(sccs))]
    for u in range(n):
        for v, _ in graph[u]:
            if scc_id[u] != scc_id[v]:
                dag[scc_id[u]].add(scc_id[v])
    # 转为列表
    dag = [list(s) for s in dag]
    return scc_id, dag

def find_bridges(n, graph):
    """寻找无向图所有桥

    时间复杂度：O(V + E)
    """
    dfn = [0] * n
    low = [0] * n
    timer = [0]
    bridges = []

    def dfs(u, parent):
        timer[0] += 1
        dfn[u] = low[u] = timer[0]
        for v, _ in graph[u]:
            if dfn[v] == 0:
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > dfn[u]:
                    bridges.append((u, v))
            elif v != parent:
                low[u] = min(low[u], dfn[v])

    for i in range(n):
        if dfn[i] == 0:
            dfs(i, -1)
    return bridges

def two_sat(n, implications):
    """2-SAT 求解

    输入：变量数 n、蕴含列表 [(not_a, b_idx), ...] 表示 a -> b
          变量 i 用 i*2 表示真，i*2+1 表示假
    输出：赋值数组或 None（无解）
    """
    # 构建蕴含图：2n 个顶点，i 表示 x_i 真，i+n 表示 x_i 假
    graph = [[] for _ in range(2 * n)]
    for a, b in implications:
        graph[a].append(b)
        # 反向蕴含（若 a -> b 给定，自动有 !b -> !a）
        graph[b ^ 1].append(a ^ 1)
    sccs = tarjan_scc(2 * n, graph)
    scc_id = [-1] * (2 * n)
    for i, scc in enumerate(sccs):
        for v in scc:
            scc_id[v] = i
    # 检查 x 与 !x 是否同 SCC
    assignment = [False] * n
    for i in range(n):
        if scc_id[2 * i] == scc_id[2 * i + 1]:
            return None                     # 无解
        # 选择拓扑序较大的 SCC（即后弹出/编号较小的）
        assignment[i] = scc_id[2 * i] < scc_id[2 * i + 1]
    return assignment