01.负环检测
a.基本思想
如果一个节点入队次数超过n次，则存在负环。
b.原理
负环会导致无限松弛，节点会被反复加入队列。
02.SPFA判负环
a.Java实现
---
public boolean hasNegativeCycle(int n) {
int[] dist = new int[n];
int[] count = new int[n]; // 记录入队次数
boolean[] inQueue = new boolean[n];
Queue<Integer> queue = new LinkedList<>();
// 将所有节点加入队列
for (int i = 0; i < n; i++) {
queue.offer(i);
inQueue[i] = true;
}
while (!queue.isEmpty()) {
int u = queue.poll();
inQueue[u] = false;
for (int i = h[u]; i != -1; i = ne[i]) {
int v = e[i];
if (dist[v] > dist[u] + w[i]) {
dist[v] = dist[u] + w[i];
count[v] = count[u] + 1;
if (count[v] >= n) {
return true; // 存在负环
}
if (!inQueue[v]) {
queue.offer(v);
inQueue[v] = true;
}
}
}
}
return false;
}
---
03.AcWing 904虫洞
a.题目
判断是否存在负环，使得可以回到过去。
b.SPFA解法
建图后使用SPFA判断负环。
04.应用场景
a.套利检测
在货币兑换中检测是否存在套利机会。
b.时间旅行
判断是否可以回到过去。
4.5 差分约束
01.差分约束概述
a.定义
给定一组不等式x[i] - x[j] <= c[k]，求一组解或判断无解。
b.转化为图论
将不等式转化为有向边，x[i] - x[j] <= c[k]对应边j->i权值为c[k]。
c.求解方法
使用SPFA求最短路，如果存在负环则无解。
02.差分约束系统
a.标准形式
x[i] - x[j] <= c[k]
b.转化规则
a.x[i] - x[j] <= c
添加边j->i，权值c。
b.x[i] - x[j] >= c
转化为x[j] - x[i] <= -c，添加边i->j，权值-c。
c.x[i] - x[j] < c
转化为x[i] - x[j] <= c-1。
d.x[i] - x[j] = c
转化为x[i] - x[j] <= c且x[j] - x[i] <= -c。
03.求解实现
a.Java实现
---
public boolean solveDifferenceConstraints(int n, int[][] constraints) {
// 建图
for (int[] c : constraints) {
int j = c[0], i = c[1], w = c[2];
add(j, i, w); // x[i] - x[j] <= w
}
// 添加超级源点
for (int i = 1; i <= n; i++) {
add(0, i, 0);
}
// SPFA求最短路
return !hasNegativeCycle(n + 1);
}
---
04.AcWing 1169糖果
a.题目
给定n个小朋友和m个约束条件，求最少需要多少糖果。
b.差分约束解法
将约束转化为不等式，建图后求最长路。
4.6 最近公共祖先
01.LCA概述
a.定义
树中两个节点的最近公共祖先是距离这两个节点最近的共同祖先节点。
b.应用场景
树上路径查询、树上距离计算。
02.倍增算法
a.基本思想
预处理每个节点向上跳2^k步的祖先，查询时二进制拆分。
b.Java实现
---
int[][] parent; // parent[i][j]表示i向上跳2^j步的祖先
int[] depth;
int maxLog;
public void preprocess(TreeNode root, int n) {
maxLog = (int)(Math.log(n) / Math.log(2)) + 1;
parent = new int[n][maxLog];
depth = new int[n];
dfs(root, -1, 0);
for (int j = 1; j < maxLog; j++) {
for (int i = 0; i < n; i++) {
if (parent[i][j-1] != -1) {
parent[i][j] = parent[parent[i][j-1]][j-1];
}
}
}
}
private void dfs(TreeNode node, int p, int d) {
if (node == null) return;
parent[node.val][0] = p;
depth[node.val] = d;
dfs(node.left, node.val, d + 1);
dfs(node.right, node.val, d + 1);
}
public int lca(int u, int v) {
if (depth[u] < depth[v]) {
int temp = u; u = v; v = temp;
}
// 将u提升到与v同一深度
int diff = depth[u] - depth[v];
for (int i = 0; i < maxLog; i++) {
if ((diff & (1 << i)) != 0) {
u = parent[u][i];
}
}
if (u == v) return u;
// 同时向上跳
for (int i = maxLog - 1; i >= 0; i--) {
if (parent[u][i] != parent[v][i]) {
u = parent[u][i];
v = parent[v][i];
}
}
return parent[u][0];
}
---
03.Tarjan算法
a.基本思想
离线算法，使用并查集和DFS一次性处理所有查询。
b.时间复杂度
O(n + q)，其中q是查询次数。
4.7 强连通分量
01.强连通分量定义
a.基本概念
有向图中的极大强连通子图，子图内任意两点可达。
b.缩点
将每个强连通分量缩成一个点，得到DAG。
02.Tarjan算法
a.基本思想
使用DFS和栈，维护dfn和low数组。
b.Java实现
---
int[] dfn, low;
boolean[] inStack;
Stack<Integer> stack;
List<List<Integer>> sccs;
int timestamp, sccCount;
public List<List<Integer>> tarjan(List<Integer>[] graph, int n) {
dfn = new int[n];
low = new int[n];
inStack = new boolean[n];
stack = new Stack<>();
sccs = new ArrayList<>();
timestamp = 0;
sccCount = 0;
for (int i = 0; i < n; i++) {
if (dfn[i] == 0) {
dfs(i, graph);
}
}
return sccs;
}
private void dfs(int u, List<Integer>[] graph) {
dfn[u] = low[u] = ++timestamp;
stack.push(u);
inStack[u] = true;
for (int v : graph[u]) {
if (dfn[v] == 0) {
dfs(v, graph);
low[u] = Math.min(low[u], low[v]);
} else if (inStack[v]) {
low[u] = Math.min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
List<Integer> scc = new ArrayList<>();
int v;
do {
v = stack.pop();
inStack[v] = false;
scc.add(v);
} while (v != u);
sccs.add(scc);
sccCount++;
}
}
---
03.Kosaraju算法
a.基本思想
两次DFS，第一次在原图上DFS得到后序遍历，第二次在反图上按后序逆序DFS。
b.时间复杂度
O(n + m)。
04.应用
a.2-SAT问题
判断布尔表达式是否可满足。
b.有向图缩点
将强连通分量缩成一个点。
4.8 双连通分量
01.双连通分量定义
a.点双连通分量
无向图中的极大子图，删除任意一个顶点后仍连通。
b.边双连通分量
无向图中的极大子图，删除任意一条边后仍连通。
c.割点和桥
割点：删除后图不连通的点。桥：删除后图不连通的边。
02.求割点
a.Tarjan算法
---
int[] dfn, low;
boolean[] isCut;
int timestamp;
public List<Integer> findCutPoints(List<Integer>[] graph, int n) {
dfn = new int[n];
low = new int[n];
isCut = new boolean[n];
timestamp = 0;
for (int i = 0; i < n; i++) {
if (dfn[i] == 0) {
dfs(i, -1, graph);
}
}
List<Integer> cutPoints = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (isCut[i]) cutPoints.add(i);
}
return cutPoints;
}
private void dfs(int u, int parent, List<Integer>[] graph) {
dfn[u] = low[u] = ++timestamp;
int children = 0;
for (int v : graph[u]) {
if (dfn[v] == 0) {
children++;
dfs(v, u, graph);
low[u] = Math.min(low[u], low[v]);
if (parent != -1 && low[v] >= dfn[u]) {
isCut[u] = true;
}
} else if (v != parent) {
low[u] = Math.min(low[u], dfn[v]);
}
}
if (parent == -1 && children > 1) {
isCut[u] = true;
}
}
---
03.求桥
a.Tarjan算法
---
public List<int[]> findBridges(List<Integer>[] graph, int n) {
dfn = new int[n];
low = new int[n];
timestamp = 0;
List<int[]> bridges = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (dfn[i] == 0) {
dfs(i, -1, graph, bridges);
}
}
return bridges;
}
private void dfs(int u, int parent, List<Integer>[] graph, List<int[]> bridges) {
dfn[u] = low[u] = ++timestamp;
for (int v : graph[u]) {
if (dfn[v] == 0) {
dfs(v, u, graph, bridges);
low[u] = Math.min(low[u], low[v]);
if (low[v] > dfn[u]) {
bridges.add(new int[]{u, v});
}
} else if (v != parent) {
low[u] = Math.min(low[u], dfn[v]);
}
}
}
---
5 高级数据结构
5.1 并查集进阶
01.带权并查集
a.定义
在并查集的基础上，维护节点到根节点的距离或关系。
b.应用场景
食物链问题、关系判断。
02.食物链问题
a.问题描述
有三种动物A、B、C，A吃B，B吃C，C吃A，给定若干关系，判断矛盾。
b.带权并查集解法
---
class UnionFind {
int[] parent;
int[] relation; // 0:同类, 1:吃parent, 2:被parent吃
public UnionFind(int n) {
parent = new int[n];
relation = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
public int find(int x) {
if (parent[x] != x) {
int root = find(parent[x]);
relation[x] = (relation[x] + relation[parent[x]]) % 3;
parent[x] = root;
}
return parent[x];
}
public void union(int x, int y, int type) {
int px = find(x);
int py = find(y);
if (px != py) {
parent[px] = py;
relation[px] = (relation[y] - relation[x] + type + 3) % 3;
}
}
public boolean isSame(int x, int y) {
if (find(x) != find(y)) return false;
return relation[x] == relation[y];
}
}
---
03.按秩合并优化
a.定义
合并时将深度小的树合并到深度大的树上。
b.实现
---
class UnionFind {
int[] parent;
int[] rank;
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 1;
}
}
public void union(int x, int y) {
int px = find(x);
int py = find(y);
if (px == py) return;
if (rank[px] < rank[py]) {
parent[px] = py;
} else if (rank[px] > rank[py]) {
parent[py] = px;
} else {
parent[py] = px;
rank[px]++;
}
}
}
---
5.2 树状数组
01.树状数组概述
a.定义
树状数组Binary Indexed Tree是一种支持单点修改和区间查询的数据结构。
b.时间复杂度
单点修改O(log n)，区间查询O(log n)。
c.空间复杂度
O(n)。
02.树状数组原理
a.lowbit操作
---
int lowbit(int x) {
return x & -x;
}
---
b.区间和查询
c[i]存储区间[i-lowbit(i)+1, i]的和。
03.树状数组实现
a.Java实现
---
class BIT {
int[] tree;
int n;
public BIT(int n) {
this.n = n;
tree = new int[n + 1];
}
// 单点修改：给位置i加上val
public void update(int i, int val) {
while (i <= n) {
tree[i] += val;
i += lowbit(i);
}
}
// 查询前缀和[1, i]
public int query(int i) {
int sum = 0;
while (i > 0) {
sum += tree[i];
i -= lowbit(i);
}
return sum;
}
// 查询区间和[l, r]
public int rangeQuery(int l, int r) {
return query(r) - query(l - 1);
}
private int lowbit(int x) {
return x & -x;
}
}
---
b.Go实现
---
type BIT struct {
tree []int
n int
}
func NewBIT(n int) *BIT {
return &BIT{
tree: make([]int, n+1),
n: n,
}
}
func (b *BIT) Update(i, val int) {
for i <= b.n {
b.tree[i] += val
i += i & -i
}
}
func (b *BIT) Query(i int) int {
sum := 0
for i > 0 {
sum += b.tree[i]
i -= i & -i
}
return sum
}
---
04.应用场景
a.区间和查询
动态维护数组的区间和。
b.逆序对统计
统计数组中的逆序对数量。
c.二维树状数组
支持二维区间和查询和单点修改。
5.3 线段树
01.线段树概述
a.定义
线段树是一种二叉树结构，用于维护区间信息，支持区间查询和区间修改。
b.时间复杂度
建树O(n)，单点修改O(log n)，区间查询O(log n)，区间修改O(log n)。
c.空间复杂度
O(4n)。
02.线段树基本操作
a.Java实现
---
class SegmentTree {
int[] tree, lazy;
int n;
public SegmentTree(int[] arr) {
n = arr.length;
tree = new int[4 * n];
lazy = new int[4 * n];
build(arr, 1, 0, n - 1);
}
// 建树
private void build(int[] arr, int node, int start, int end) {
if (start == end) {
tree[node] = arr[start];
return;
}
int mid = (start + end) / 2;
build(arr, 2 * node, start, mid);
build(arr, 2 * node + 1, mid + 1, end);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
// 区间查询
public int query(int l, int r) {
return query(1, 0, n - 1, l, r);
}
private int query(int node, int start, int end, int l, int r) {
if (r < start || end < l) return 0;
if (l <= start && end <= r) return tree[node];
pushDown(node, start, end);
int mid = (start + end) / 2;
return query(2 * node, start, mid, l, r) +
query(2 * node + 1, mid + 1, end, l, r);
}
// 区间修改
public void update(int l, int r, int val) {
update(1, 0, n - 1, l, r, val);
}
private void update(int node, int start, int end, int l, int r, int val) {
if (r < start || end < l) return;
if (l <= start && end <= r) {
tree[node] += (end - start + 1) * val;
lazy[node] += val;
return;
}
pushDown(node, start, end);
int mid = (start + end) / 2;
update(2 * node, start, mid, l, r, val);
update(2 * node + 1, mid + 1, end, l, r, val);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
// 懒标记下传
private void pushDown(int node, int start, int end) {
if (lazy[node] != 0) {
int mid = (start + end) / 2;
tree[2 * node] += (mid - start + 1) * lazy[node];
tree[2 * node + 1] += (end - mid) * lazy[node];
lazy[2 * node] += lazy[node];
lazy[2 * node + 1] += lazy[node];
lazy[node] = 0;
}
}
}
---
03.线段树应用
a.区间最值查询
维护区间最大值或最小值。
b.区间GCD
维护区间最大公约数。
c.区间修改
支持区间加、区间乘等操作。
01.埃氏筛
a.基本思想
从2开始，筛掉所有2的倍数，再筛3的倍数，依此类推。
b.时间复杂度
O(n log log n)。
02.线性筛
a.基本思想
每个合数只被其最小质因子筛掉一次。
b.Java实现
---
public List<Integer> linearSieve(int n) {
boolean[] isPrime = new boolean[n + 1];
Arrays.fill(isPrime, true);
List<Integer> primes = new ArrayList<>();
for (int i = 2; i <= n; i++) {
if (isPrime[i]) primes.add(i);
for (int j = 0; j < primes.size() && i * primes.get(j) <= n; j++) {
isPrime[i * primes.get(j)] = false;
if (i % primes.get(j) == 0) break;
}
}
return primes;
}
---
6.2 欧拉函数
01.欧拉函数定义
a.φ(n)
小于等于n且与n互质的正整数个数。
b.性质
若n = p^k，则φ(n) = p^(k-1) * (p-1)。
02.欧拉函数计算
a.单个数
---
public int phi(int n) {
int res = n;
for (int i = 2; i <= n / i; i++) {
if (n % i == 0) {
res = res / i * (i - 1);
while (n % i == 0) n /= i;
}
}
if (n > 1) res = res / n * (n - 1);
return res;
}
---
b.筛法求1到n的欧拉函数
线性筛的同时计算欧拉函数。
03.欧拉定理
a.定理
若gcd(a,n)=1，则a^φ(n) ≡ 1 (mod n)。
b.应用
求逆元、快速幂。
01.矩阵乘法基础
a.定义
C[i][j] = Σ A[i][k] * B[k][j]
b.时间复杂度
O(n³)。
02.矩阵快速幂
a.应用
加速线性递推，如斐波那契数列。
b.Java实现
---
public long[][] matrixPow(long[][] A, long n, long mod) {
int size = A.length;
long[][] res = new long[size][size];
for (int i = 0; i < size; i++) res[i][i] = 1;
while (n > 0) {
if ((n & 1) == 1) res = multiply(res, A, mod);
A = multiply(A, A, mod);
n >>= 1;
}
return res;
}
private long[][] multiply(long[][] A, long[][] B, long mod) {
int n = A.length;
long[][] C = new long[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod;
}
}
}
return C;
}
---
03.应用
a.斐波那契数列
F(n) = [[1,1],[1,0]]^n
b.图的路径计数
A^k[i][j]表示i到j长度为k的路径数。