有向图中的环检测在有向图中检测是否存在环（Cycle）是一个经典问题。环是指从某个节点出发，沿着有向边最终能回到该节点的路径。 方法一：DFS + 三色标记算法思想使用三种颜色标记节点的状态： 白色 (0)：未访问 灰色 (1)：正在访问（在当前递归栈中） 黑色 (2)：已访问完成（不在递归栈中） 如果在 DFS 过程中遇到灰色节点，说明找到了环。 为什么有效？ 灰色节点表示当前路径上的节点

并查集什么是并查集？并查集（Disjoint Set Union，DSU）数据结构，也称为联合-查找数据结构，允许你向图中添加边，并测试图中两个顶点是否相连。 由于实现非常简单，你可能更倾向于使用它来代替 DFS 计算连通分量。 核心优化1. 路径压缩 (Path Compression)在 find 操作中，将路径上的所有节点直接指向根节点，大大加快后续查询。 2. 按秩合并 (Union by

差分数组模板diff = [0] * (n + 1) # 开 n+1，防止 r+1 越界 # 对区间 [l, r] 加 v diff[l] += v diff[r+1] -= v # 还原：对 diff 求前缀和 arr = [0] * n curr = 0 for i in range(n): curr += diff[i] arr[i] = curr 字典版（稀疏差分）

二分查找模板有序数组：bisect 函数 功能 返回值 lower_bound(x) 第一个 >= x 的位置 第一个 >= x 的元素下标 upper_bound(x) 第一个 > x 的位置 第一个 > x 的元素下标 import bisect arr = sorted([...]) # 先排序 # lower_bound: 第一个 &

Priority Queues 优先队列简介优先队列（Priority Queue 或 Heap）支持以下操作： 插入元素 删除最高优先级元素 获取最高优先级元素 以上操作的时间复杂度均为 O(log N)。 优先队列比集合更简单更快，应尽可能使用优先队列。 Python 实现注意：Python（与 C++ 不同）中删除和获取的是最小元素。 heapq 不是封装好的类，而是直接操作传入的列表，

输入输出基础输入# 单个整数 n = int(input()) # 多个整数（空格分隔） a, b = map(int, input().split()) # 一行整数转列表 arr = list(map(int, input().split())) # 去除换行符 s = input().strip() # 去除首尾空白（含 \n） # 读取 n 行到列表 arr = [int(inp

Python 工具函数itertools.accumulate —— 前缀和 / 前缀最值签名：itertools.accumulate(iterable, func=operator.add, *, initial=None) 一遍扫描累积出「每一步的折叠结果」，默认就是前缀和： from itertools import accumulate from operator import mul

高级数据结构树状数组 (Fenwick Tree)class Fenwick: """树状数组 (Fenwick Tree / Binary Indexed Tree)""" def __init__(self, n: int = 0): self.n = n self.a = [0] *

完全背包类型一：计数问题（方案数）Coin Combinations I（有序）题目描述https://cses.fi/problemset/task/1635 给定 n 种硬币，每种硬币价值为 $c_i$，求凑成金额 x 的不同方式数（顺序不同视为不同）。输出模 $10^9+7$ 的结果。 限制： 1 ≤ n ≤ 100 1 ≤ x ≤ $10^6$ 1 ≤ c_i ≤ $10^6$ 示例：

0/1 背包问题问题描述有 $N$ 件物品，每件物品有重量 $w_i$ 和价值 $v_i$，求在不超过背包容量 $W$ 的情况下，选择物品使得总价值最大。 一维 DP定义：dp[j] 为背包容量为 j 时的最大价值 初始条件：dp[j] = 0 状态转移： dp[j] = \max(dp[j], dp[j - w] + v)代码： N, W = map(int, input().split())