基础算法

快速排序

  • 思路：
    1.选择一个基准值
    2.将数组分为两个子数组，左边的子数组元素都小于基准值，右边的子数组元素都大于基准值
    3.递归地对这两个子数组进行排序
1
2
3
4
5
6
7
8
9
10
11
12
13
void quickSort(int q[], int l, int r) {
    if (l >= r) return;

    int key = q[(l + r + 1) / 2], i = l - 1, j = r + 1;
    while (i < j) {
        do i++; while (q[i] <= key);
        do j--; while (q[j] >= key);
        if (i < j) swap(q[i], q[j]);
    }

    quickSort(q, l, i-1);
    quickSort(q, i, r);
}

归并排序

  • 思路：
    1.将数组分成两半，分别对它们进行排序
    2.将排序好的两半合并成一个有序数组
1
2
3
4
5
6
7
8
9
10
11
12
13
void mergeSort(int q[], int l, int r){
    if ( l>= r ) return;
    int mid = (l + r) / 2;
    mergeSort(q, l, mid), mergeSort(q, mid+1, r);
    int tmp[r - l + 1], k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    }
    while (i <= mid) tmp[k++] = q[i++];
    while (j <= r) tmp[k++] = q[j++];
    for(i = l, j = 0; j < k; j++, i++) q[i] = tmp[j];
}

pivot的选取

上述代码默认选取数组中间值作为pivot，但实际上pivot选取为数组中位数(即每次都能二分数组)时，时间复杂度会更接近$O(nlogn)$.

  • 使用median of medians算法：
    1.将数组每5个元素分成一组，取出每组的中位数
    2.取这组中位数的中位数作为pivot

二分法

主要用于在有序数组中查找某一特定元素,时间复杂度为$O(logn)$.
在一个有序的区间中，每次选择中间点，将搜索区间分成两半，并根据中间点的值判断目标值落在哪一半，从而抛弃另一半，继续在剩余的区间内搜索，直到找到目标值或者区间缩小至无法再分.

  • 注意：

    1. mid的选取需要注意是否会造成死循环
    2. 二分法假定在搜索区间内一定存在解. 使用前最好确保问题本身是有解的，或者至少能够通过合理的处理（如返回近似解）来处理无解的情况

  • 应用：

    1. 有序数组的查找
    2. 求解方程的根
    3. 最优化问题的求解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 区间[l, r]被分成[l, mid]和[mid+1, r]
int binarySearch_1(int a[], int l, int r, int x)
{
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (check(a[mid], x)) r = mid;
        else l = mid + 1;
    }
    return l;
}

// 区间[l, r]被分成[l, mid-1]和[mid, r]
int binarySearch_2(int a[], int l, int r, int x)
{
    while (l < r)
    {
        int mid = (l + r + 1) / 2;
        if (check(a[mid], x)) l = mid;
        // 当l = r -1如果mid = (l + r) / 2 = l, 会导致死循环
        else r = mid - 1;
    }
    return l;
}

高精度

即超出标准数据类型所表示范围的数值计算.

整数的高精度计算（加减乘除）通过数组存储数字的每一位，再模拟手工计算方法过程实现.

前缀和与差分

  1. 一维前缀和即 $S[n]=\sum_{i=1}^{n}a[i]$ 其中 $S[n]=S[n-1]+a[n], S[0]=0$，可以快速计算数组 $a[l]+\dots +a[r]=S[r]-S[l-1]$.

  2. 二维前缀和 $S[i][j]=S[i][j-1]+S[i-1][j]-S[i-1][j-1]+a[i][j]$.

  3. 差分即前缀和的逆运算，$D[n]=a[n]-a[n-1], \sum_{i=1}^{n}D[i]=a[i]$, 可以快速将 $[l,r]$ 范围内数加上c：$D[l]+=c, D[r+1]-=c$, 而不引起其元素变化.

  • 作用：可以显著提高处理数组相关问题的效率.

离散化

将连续的或者较大范围的数值映射到有限的整数集合中，离散化的核心是通过排序和去重等操作将原始数据映射到更小的数据范围，减少空间和时间复杂度。

  • 时间复杂度：排序 $O(n\log n)$ + 去重 $O(n)$ + 查找(二分) $O(k\log n) = O((n+k)\log n)$.

  • 离散化并不会改变数值之间的相对大小关系，因此在区间查询、统计等场景中，离散化后的操作结果仍然能反映原始数据的关系。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <vector>
#include <algorithm>

vector<int> all; // all存储需要处理的所有数据，包括更新操作和查找操作的值
vector<int> query; // 存储查询操作的数据

// 离散后的查找函数
int find(int x, vector<int> a){
    int l = 0, r = a.size() - 1;
    while(l < r)
    {
        int mid = r + l >> 1;
        if(a[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 返回离散后的下标从1开始
}

int main(){
    // 输入数据
    // ...

    sort(all.begin(), all.end()); // 排序
    all.erase(unique(all.begin(), all.end()), all.end()); // 去重

    for(auto val: query)
    {
        int x = find(val, all); //x为离散化后的值，即数组下标
        // ...
    }
    return 0;
}
  • 应用：
    1. 区间求和：将较大范围的数值离散化为较小范围，配合树状数组、线段树等数据结构，可以高效进行区间求和、更新等操作。
    2. 动态规划：离散化可以减少状态空间的规模，从而优化算法的时间和空间复杂度。
    3. 统计问题：在一些需要对稀疏数据进行处理的问题中，离散化可以减少无效操作，提升效率。

区间合并

将重叠或相邻的区间合并成一个区间。常用于处理如区间覆盖、会议时间安排等问题。

  • 思路：将区间按照左端点排序后，从左到右遍历，每个区间后面的区间有两种情况：
    1. 两个区间有重叠，即 $ed \geq item.first$. 两个区间右端点中大的成为新的右端点。
    2. 两个区间不重叠，即 $ed < item.first$. 前一个区间合并完成，新区间成为新的比较区间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <algorithm>
#include <vector>

const int INF = -1e9;

void merge(vector<pair<int, int>> &a)
{
    sort(a.begin(), a.end()); // 按左端点排序

    vector<pair<int, int>> tmp;
    int st = INF, ed = INF; //st, ed初始值设为较小值或无穷小
    for(auto item: a){
        if(ed < item.first){ // 前一个区间合并完成
            if(st != INF) tmp.push_back({st, ed});
            st = item.first, ed = item.second;
        }
        else ed = max(ed, item.second);
    }
    if(st != INF) tmp.push_back({st, ed}); //最后一个区间加入数组
    a = tmp;
}

int main(){
    vector<pair<int, int>> a;
    // 输入
    // ...
    merge(a);

    // 输出
    // ...
    return 0;
}

数据结构

链表

此处链表用数组实现，相较于结构体实现效率高，内存消耗小，适用于节点数固定或上限已知的情况。

  • 基本操作: 头部或尾部插入一个节点、在第k个插入节点或第k个节点的左端或右端插入节点、删除第k个插入的节点或第k个节点,每插入一个节点都需要考虑两侧节点的变化。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
const int N; // 最高节点数目

int val[N], l[N], r[N], idx;// 存储值、左节点下标、右节点下标、存储的位置

// 节点a右边插入一个数
void insert(int a, int x)
{
    val[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx;
    r[a] = idx++;
}

// 删除节点a
void remove(int a)
{
    r[l[a]] = r[a];
    l[r[a]] = l[a];
}

int main(){
    // 0是左端点，1是右端点
    // 此初始化省去了考虑边界是否为头尾节点的判断操作
    r[0] = 1, l[1] = 0;
    idx = 2;

    int k, x;

    insert(0, x); // 头部插入x

    insert(l[1], x); // 尾部插入x

    insert(k+1, x); // 第k个插入节点的右边插入x
    
    insert(l[k+1], x); // 第k个插入节点的左边插入x

    remove(k+1); // 删除第k个插入的节点

    return 0;
}

KMP

KMP是一个模式串匹配算法, 时间复杂度为 $O(m+n)$, m为模式串长度, n为主串长度。相比于朴素模式匹配算法利用了模式串本身的部分匹配信息, 避免了不必要的重复匹配。

  • 核心: 前缀表(部分匹配表, 通常为next数组), 记录了每个模式串中前缀和后缀的最长匹配长度。当发生不匹配时，能将模式串向后移动合适的位置，避免重复检查已经匹配过的字符。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

char s[n], t[m];
int ne[m]; //next数组设置为全局变量最好，默认初始化为0

// 得到next数组
void get_next(auto t[], int m)
{
    for(int i=1, j=0; i<m; i++)
    {
        while(j && t[i] != t[j]) j = ne[j-1];
        if(t[i] == t[j]) j++;
        ne[i] = j;
    }
}

// 从主串中查找子串，返回子串出现的初始位置
void kmp_search(auto s[], int n, auto t[], int m)
{
    for(int i=0, j=0; i<n; i++)
    {
        while(j && s[i] != t[j]) j = ne[j-1];
        if( s[i] == t[j]) j++;
        if(j == m){
            cout << i - j + 1<<' ';
        }
    }
}

Trie(前缀树)字符串统计

一种用于高效查找和存储字符串的数据结构，适合处理字符串前缀匹配问题。

每个节点代表一个字符，所有从根节点到叶节点的路径构成一个字符串，再用一个标记表示每个节点结束的字符串的数量。

  • 插入和查询时间都是 $O(m), m$为字符串长度.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 假设只存储小写字母构成的字符串
int son[N][26]; // 字符串总长度不超过N，小写字母共26个
int count[N]; // 表示每个字符串的个数
int idx; // idx记录节点个数

void insert (char str[]){
    int p = 0;
    for(int i=0; str[i]; i++) // char[]类型末尾存储空字符，可用于判断
    {
        int q = str[i] - 'a'; // 转换成对应的26个数字
        if(!son[p][q]) son[p][q] = ++idx;
        p = son[p][q];
    }
    count[p]++; // 每个节点都有一个编号p
}

int query (char str[]){
    int p = 0;
    for(int i=0; str[i]; i++)
    {
        int q = str[i] - 'a';
        if(!son[p][q]) return 0;
        p = son[p][q];
    }
    return count[p];
}

并查集(Disjoint Set Union)

一种处理不相交集合的合并和查找两个元素是否属于同一集合的数据结构。

  • 并查集的合并和查找几乎为常数时间复杂度 $O(1)$.

基本结构：

  1. 父节点数组：记录每个元素的父节点，初始时每个元素的父节点是本身，最后根节点的父节点也为本身。
  2. 秩(Rank)：即树的高度，用于优化合并集合的操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
const int N;
int p[N], rank[N]; 

// 初始化
for(int i = 1, i<=n; i++){
    p[i] = i;
    rank[i] = 1;
}

int find(int x) // 查找操作
{
    if(p[x] != x) p[x] = find(p[x]); // 路径压缩，每个节点直接连向祖先节点
    return p[x];
}

void Union(int x, int y) // 合并x和y所在的两个集合
{
    int rx = find(x), ry = find(y);
    if(rx == ry) return;
    // 按秩合并
    if(rank[x] < rank[y]) p[rx] = ry;
    else if(rank[x] > rank[y]) p[ry] = rx;
    else{
        p[rx] = ry;
        rank[y]++;
    }
}

堆

常用于解决堆排序和优先队列的问题，是一棵完全二叉树， 分为大顶堆和小顶堆。

  • 优先队列(STL中的priorty_queue), 插入和删除元素均为 $O(\log n)$, 取最小(或最大)元素为 $O(1)$.

  • 关键操作：上浮(up)和下沉(down).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
const int N;
int heap[N], sz; // sz用于记录当前数组中元素个数
// hp[i]记录当前数组的第i个位置的插入元素的序号
// ph[i]记录第i个插入元素的位置
// idx记录插入元素的个数
int hp[N], ph[N], idx; // 用于删除或修改第k个插入的节点的操作

void heap_swap(int a, int b){
    swap(heap[a], heap[b]);
    swap(hp[a], hp[b]);
    ph[hp[a]] = a;
    ph[hp[b]] = b;
}

void up(int x){
    while(x > 1 && heap[x] < heap[x/2]){
        heap_swap(x, x/2);
        x /= 2;
    } // 也可以递归
}

void down(int x){
    int t = x;
    if(2*x <= sz && heap[t] > heap[2*x]) t = 2*x;
    if(2*x+1 <= sz && heap[t] > heap[2*x+1]) t = 2*x+1;
    if(t != x){
        heap_swap(x, t);
        down(t);
    }
}

// 插入
void insert(int a){
    heap[++sz] = a;
    hp[sz] = ++idx;
    ph[idx] = sz;
    up(sz);
}

// 删除头节点
void remove(){
    heap_swap(1, sz--);
    down(1);
}

// 删除第k个插入的节点
void remove_k(int k){
    int pos = ph[k];
    heap_swap(pos, sz--);
    up(pos); down(pos);
}

// 修改第k个插入的节点为x
void change_k(int k, int x){
    int pos = ph[k];
    heap[pos] = x;
    up(pos); down(pos);
}

哈希表

又称散列表，一种基于键值对的数据结构，通过哈希函数将键值映射到数组的索引位置，直接访问数据，减少查找的时间复杂度。

  1. 基本概念：
    1. 哈希函数：将值映射到哈希表中，好的哈希函数应尽量避免冲突。
    2. 哈希冲突：多个值映射到一个位置时产生冲突，处理冲突的方法主要为：
      • 链地址法：使用链表在相同位置储存散列值相同的数据
      • 开放寻址法：发生冲突时在数组寻找下一个空闲位置插入
    3. 装载因子：哈希表中元素个数与数组大小的比值。过大时冲突的概率会增加，导致查找效率变低。
  2. 操作：插入、查找和删除，平均时间复杂度为 $O(1)$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 此处哈希函数为取一个质数的模，冲突概率最小
#include <cstring>

const int N; // N为质数
int h[N], e[N], ne[N], idx; // idx记录链表数组的节点个数

memset(h, -1, sizeof(h)); // 初始化h，-1代表为空

void insert(int x){
    int k = (k % N + N) % N; // 负数取模为负数，取模加上N后再取模转化为正数
    e[idx] = x;
    ne[idx] = h[k]; // 插入到链表头部，将当前元素的next指向当前头元素
    h[k] = idx++; // 更新链表头为当前元素，idx自增
}

bool find(int x){
    int k = (k % N + N) % N;
    for(int i=h[k]; i!=-1; i=ne[i]){
        if(e[i] == x) return true;
    }
    return false;
}

字符串哈希

通过将字符串映射为一个整数（哈希值）来进行快速比较和查找的技术。常用于字符串匹配、字符串去重和处理大量字符串的数据结构中。

  • 单项哈希：将字符串看做一个基数为P的多项式，选择较大质数作为基数(131、13331)和模数(2e64)，以减少哈希冲突。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef unsigned long long ULL; // 自动取2e64的模

const int N, P = 131;

ULL h[N], p[N]; // p[i]记录P的i次方

// 计算哈希值
ULL get(int l, int r){
    return h[r] - h[l-1]*p[r-l+1];
}

int main(){
    int n;
    char str[N];
    // 预处理
    p[0] = 1;
    for(int i=0; i<=n; i++){
        p[i] = p[i-1]*P;
        h[i] = h[i-1]*P + str[i];
    }
}

搜索与图论

DFS/回溯

  • 时间复杂度 $O(|E|+|V|)$, $|E|$ 为边数, $|V|$ 为节点数。

用于组合问题。在回溯算法中，我们探索一个问题的所有可能解，当发现当前选择不符合要求时，就“回退”到上一步并尝试其他选择。回溯的核心在于选择、探索、回退的过程。

  • 应用：

    1. 检查连通性
    2. 寻找无向图联通分量
    3. 拓扑排序
      • 拓扑排序：若一个由图中所有点构成的序列 $A$ 满足：对于图中的每条边 $(x,y), x$ 在 $A$ 中都出现在 $y$ 之前，则称 $A$ 为拓扑排序。
      • 有向无环图(DAG, Directed Acyclic Graph)才有拓扑排序。
      • 根据完成时间从大到小排序，对每个节点DFS后将该节点入栈，最后输出栈的元素。
    4. 有向图强联通分量（找反图）

N皇后问题：力扣 51. N 皇后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> solutions;       // 存储所有解法
        vector<string> board(n, string(n, '.')); // 初始化棋盘
        // 列和正反对角线的标记数组
        vector<bool> col(n, false), dg(2 * n, false), udg(2 * n, false); 
        dfs(0, n, board, col, dg, udg, solutions);
        return solutions;
    }

private:
    void dfs(int row, int n, vector<string>& board, vector<bool>& col, vector<bool>& dg, vector<bool>& udg, vector<vector<string>>& solutions){
        if(row == n){ // 如果所有行都放置完皇后
            solutions.push_back(board);
            return;
        }
        for(int i = 0; i < n; i++){// 尝试在当前行的每一列放置皇后
            if (!col[i] && !dg[row + i] && !udg[i - row + n]){ 
                board[row][i] = 'Q';
                col[i] = dg[row + i] = udg[i - row + n] = true; // 标记列和对角线
                dfs(row + 1, n, board, col, dg, udg, solutions); // 递归处理下一行
                col[i] = dg[row + i] = udg[i - row + n] = false; // 回溯，撤销标记
                board[row][i] = '.';// 移除皇后
            }
        }
    }
};

找有向图的强连通分量：

  • 思路：
    1. 对反图做DFS，记录每个节点的finish时间，即DFS完成的时间。反图中的soure节点即为原图中的sink节点。
    2. 根据节点的finish时间从大到小对每个节点在原图做DFS，可得到强连通分量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

const int N = 100010; // 节点个数上限

int n, m; // n个节点，m条边
int idx = 0; // 强联通分量个数
vector<int> adj[N], radj[N]; // 原图和反图的邻接表
stack<int> finish_time; // 记录每个节点的finish时间
bool visited[N]; // 记录每个节点是否已被访问
vector<int> SCC[N]; // 记录强连通分量

void dfs1(int u){
    visited[u] = true;
    for(int v : radj[u]){
        if(!visited[v]) dfs1(v);
    }
    finish_time.push(u);
}

void dfs2(int u, int idx){
    visited[u] = true;
    SCC[idx].push_back(u);
    for(int v : adj[u]){
        if(!visited[v]) dfs2(v, idx);
    }
}

void scc(){
    // 反图DFS
    for(int i=1; i<=n; i++){
        if(!visited[i]) dfs1(i);
    }
    // 原图DFS
    fill(visited, visited+n+1, false);
    while(!finish_time.empty()){
        int u = finish_time.top();
        finish_time.pop();
        if(!visited[u]){
            dfs2(u, idx);
            idx++;
        }
    }
}
int main(){
    cin >> n>> m;
    for(int i=0; i<m; i++){
        int u, v;
        cin >> u>> v;
        adj[u].push_back(v);
        radj[v].push_back(u);
    }
    scc();
    for(int i=0; i<idx; i++){
        for(int u : SCC[i]) cout << u << " ";
        cout << endl;
    }
    return 0;
}

BFS

  • 时间复杂度 $O(|E|+|V|)$。

用于遍历或搜索树或图数据结构。先搜索最近的所有邻节点，再逐参层遍历。
应用：

  • 用于寻找无权图中的最短路径， 通常使用队列实现。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>

using namespace std;

void bfs(const vector<vector<int>>& graph, int start) {
    unordered_set<int> visited; // 用于存储已访问的节点
    queue<int> q;
    visited.insert(start);
    q.push(start);

    while (!q.empty()){
        int node = q.front();
        q.pop();
        cout << node << " ";

        for (int neighbor : graph[node]) {
            if (visited.find(neighbor) == visited.end()){  
                visited.insert(neighbor);
                q.push(neighbor);
            }
        }
    }
}

int main() {
    // 图的邻接表表示法
    vector<vector<int>> graph = {{1, 2}, {0, 3, 4}, {0, 5, 6}, {1}, {1}, {2}};
    bfs(graph, 0);
    cout << endl;
    return 0;
}

也可使用普通数组模拟队列和邻接表，布尔类型数组或者距离数组判断是否已经访问。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <cstring>
using namespace std;

const int N; // 节点个数上限

int n, m; // n个节点，m条边
// 无向图时为e[2*N], ne[2*N];
int h[N], e[N], ne[N], idx; // 链表头结点，节点值，下一个节点索引，存储节点的索引
int d[N], q[N], hh = 0, tt = -1; // d为每个节点到根节点的距离， q模拟队列
memset(d, -1, sizeof(d)); // 初始化每个节点到根节点距离为-1，可用于判断是否访问过

// 添加a到b的边
void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}


void bfs(){
    q[++tt] = 1;
    d[1] = 0;
    while(hh <= tt){
        int x = q[hh++];
        for(int i = h[x]; i != -1; i = ne[i]){
            int j = e[i]; // 节点序号
            if(d[j] == -1) d[j] = d[x] + 1; // 记录x节点邻节点的距离
            q[++tt] = j; // 邻节点加入队列
        }
    }
}

int main(){
    memset(h, -1, sizeof(h)); // 初始化头结点索引为-1，表示不存在
    cin >> n>> m;
    while(m--){
        int a, b;
        cin >> a>> b;
        add(a, b);
        //add(b, a); 无向图时添加
    }
    bfs();
    for(int i=0; i<n; i++)
        cout << d[i] << ' ';
    return 0;
}
  • 拓扑排序
    • 思路：输出入度为零的节点，删除该节点后更新图，递归，直到输出所有节点。如果没有遍历所有节点而不存在入度为零的节点，则存在环，即不存在拓扑排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <cstring>
using namespace std;

const int N; // 节点个数上限

int n, m; // n个节点，m条边
int h[N], e[N], ne[N], idx; // 链表头结点，节点值，下一个节点索引，存储节点的索引
int d[N], q[N], hh = 0, tt = -1; // d为每个节点到根节点的距离，q模拟队列，d记录每个节点的入度

// 添加a到b的边
void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

bool TopoSort(){
    for(int i=0; i<n; i++)
        if(d[i] == 0) q[++tt] = i;
    while(hh <= tt){
        int x = q[hh++];
        for(int i=h[x]; i != -1; i = ne[i]){
            int j = e[i];
            if(--d[j] == 0) q[++tt] = j;
        }
    }
    return tt == n-1; //是否输出所有节点
}

int main(){
    memset(h, -1, sizeof(h));
    cin >> n>> m;
    while(m--){
        int a, b;
        cin >> a>> b;
        add(a, b);
        d[b]++; // 入度增加
    }
    if(TopoSort()){
        for(int i=0; i<n; i++) cout << q[i] << ' ';
    }
    else cout << -1 << endl;
    return 0;
}

Dijkstra算法

  • 时间复杂度 $O(|E|log|V|)$。
  • 适用于有权图(权值非负)的单源最短路径问题。
  • 思路：维护一个优先队列，每次从队列中取出距离源点最近的点，更新其邻节点的距离，并将其邻节点加入队列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

typedef pair<int, int> PII;

const int N; // 节点个数上限

vector<vector<PII>> adj[N]; // 邻接表表示法
int d[N]; // 记录每个节点到源点的距离
bool visited[N]; // 记录每个节点是否已访问

int dijkstra(int s, int t, int n){ // 如果路径不一定存在则返回bool类型
    fill(d, d+n+1, 0x3f3f3f3f); // 初始化源点到所有节点的距离为无穷大，d[0]到d[n]一共n+1个节点
    priority_queue<PII, vector<PII>, greater<PII>> pq; // 优先队列返回距离最小的点
    d[s] = 0;
    pq.push({0, s}); // 加入源点{dist, node}记录距离和节点
    while(!pq.empty()){
        auto [dist, u] = pq.top();
        pq.pop();
        if(visited[u]) continue; // 已经访问过的节点不再加入队列
        visited[u] = true;
        if(u == t) return dist; // 找到目标点   // 若存在路径则return true;
        for(auto [v, w] : adj[u]){
            if(d[u] + w < d[v]){ // 更新距离
                d[v] = d[u] + w;
                pq.push({d[v], v});
            }
        }
    }
    return d[t]; // 返回源点到目标点的距离  // 若不存在路径则return false;
}

int main(){
    int n, m, s, t; // n个节点，m条边
    cin >> n >> m >> s >> t;
    while(m--){
        int u, v, w; // Edge(u, v, w)
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w}); // 无向图时添加
    }
    cout << dijkstra(s, t, n) << endl;
    return 0;
}

bellman-ford算法

  • 时间复杂度 $O(|E|*|V|)$。
  • 适用于有权图(权值有负数)的单源最短路径问题。
  • 思路：对每个节点进行一次松弛操作，直到不能再进行松弛，或松弛次数超过|V|-1次。
    • 松弛操作：对于每条边(u,v)的权值w，如果d[v] > d[u] + w，则更新d[v] = d[u] + w。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <vector>
#include <climits>

using namespace std;

struct Edge{
    int u, v, w;
};

const int N; // 节点个数上限

vector<Edge> edges; // 边集
int d[N]; // 记录每个节点到源点的距离
int n, m, s, t; // n个节点，m条边


// 判断s到t是否存在负权回路
bool bellman_ford(int s, int t){
    fill(d, d+n+1, INT_MAX);
    d[s] = 0;
    for(int i=0; i<n-1; i++){
        for(auto& e : edges){
            int u = e.u, v = e.v, w = e.w;
            if(d[u] != INT_MAX && d[u] + w < d[v]){
                d[v] = d[u] + w;
            }
        }
    }
    for(auto& e : edges){
        int u = e.u, v = e.v, w = e.w;
        if(d[u] != INT_MAX && d[u] + w < d[v]){
            return false; // 边还能松弛则存在负权回路
        }
    }
    return true; // 无负权回路
}

int main(){
    cin >> n >> m >> s>> t;
    while(m--){
        int u, v, w;
        cin >> u >> v >> w;
        edges.push_back({u, v, w});
    }
    // 假设s可达t
    if(bellman_ford(s, t)) cout << d[t]<< endl;
    else cout << "Negative cycle" << endl;
    return 0;
}

spfa算法

  • 最坏时间复杂度 $O(|E|*|V|)$。
  • 适用于有权图(权值有负数)的单源最短路径问题。
  • 基于队列优化bellman-ford算法，通过动态调整松弛操作的顺序，减少不必要的松弛次数。
  • 判断负环：增加一个cnt数组，记录每个节点的松弛次数，若超过|V|-1次则存在负环
    • 注意：因为负环不一定和初始节点连通，所以初始化时需要将所有节点入队， 并且每个节点初始距离为零，即相当于一个虚拟的0号节点到所有点的距离为0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
\\ 和Dijkstra算法类似，但使用队列优化
#include <iostraem>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

typedef pair<int, int> PII;

const int N; // 节点个数上限

vector<PII> adj[N]; // 邻接表表示法
int d[N]; // 记录每个节点到源点的距离
bool inq[N]; // 记录每个节点是否在队列中
int n, m, s, t; // n个节点，m条边

// 判断s到t是否存在最短路径
bool spfa(int s, int t){
    fill(d, d+n+1, INT_MAX);
    fill(inq, inq+n+1, false);
    d[s] = 0;
    queue<int> q;
    q.push(s);
    inq[s] = true;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        inq[u] = false;
        for(auto [v, w] : adj[u]){
            if(d[v] > d[u] + w){
                d[v] = d[u] + w;
                if(!inq[v]){
                    q.push(v);
                    inq[v] = true;
                }
            }
        }
    }
    return d[t] != INT_MAX; // 存在最短路径则返回true;
}

int main(){
    cin >> n>> m>> s>> t;
    while(m--){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w}); // 无向图时添加
    }
    if(spfa(s, t)) cout << d[t]<< endl;
    else cout << "impossible" << endl;
    return 0;
}

floyd算法

  • 时间复杂度 $O(|V|^3)$。
  • 适用于有权图(无负环)的所有源点最短路径问题。
  • 思路：对每个节点对所有节点进行三次松弛操作，即对每个节点i，j，k，如果 $d[i][j] > d[i][k] + d[k][j]$ ，则更新$d[i][j] = d[i][k] + d[k][j]$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <algorithm>
#include <climits>

using namespace std;

const int N = 100010; // 节点个数上限

int n, m, k; // n个节点，m条边, k个询问
int d[N][N]; // 记录每个节点对的距离

void floyd(){
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                if(d[i][k] != INT_MAX && d[k][j] != INT_MAX)
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

int main(){
    cin >> n >> m >> k;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            d[i][j] = i == j ? 0 : INT_MAX; // 自环距离为0，其他距离为无穷大

    while(m--){
        int u, v, w;
        cin >> u >> v >> w;
        d[u][v] = min(d[u][v], w);
    }

    floyd();

    while(k--){
        int s, t;
        cin >> s >> t;
        if(d[s][t] == INT_MAX) cout << "impossible" << endl;
        else cout << d[s][t] << endl;
    }
    return 0;
}

Prim算法

  • 时间复杂度 $O(|E|log|V|)$。
  • 适用于无权图的最小生成树问题。
  • 思路：从未访问的节点中选取权值最小的边，将节点加入最小生成树，并更新未访问节点的邻节点的距离。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <algorithm>
#include <climits>

using namespace std;

const int N = 100010; // 节点个数上限

int n, m; // n个节点，m条边
int g[N][N]; // 邻接矩阵
int d[N]; // 记录每个节点到树的距离
bool vis[N]; // 记录每个节点是否在树中

int prim(){
    fill(d, d+n+1, INT_MAX);
    d[1] = 0; // 保证第一个节点为1号点
    int res = 0; // 记录最小生成树的权重
    for(int i=1; i<=n; i++){
        int t = -1;
        for(int j=1; j<=n; j++)
            if(!vis[j] && (t == -1 || d[j] < d[t])) 
                t = j; // 选择权值最小的边
        if(d[t] == INT_MAX) return INT_MAX;
        res += d[t];
        vis[t] = true;
        for(int j=1; j<=n; j++)
            d[j] = min(d[j], g[t][j]); // 更新距离
    }
    return res;
}

int main(){
    cin >> n >> m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            g[i][j] = i == j ? 0 : INT_MAX;
    while(m--){
        int u, v, w;
        cin >> u>> v>> w;
        g[u][v] = g[v][u] = min(g[u][v], w);
    }
    int res = prim();
    if(res == INT_MAX) cout << "impossible" << endl;
    else cout << res << endl;
    return 0;
}

Kruskal算法

  • 时间复杂度 $O(|E|log|V|)$。
  • 适用于稀疏无权图的最小生成树问题。
  • 思路：对边按权值从小到大排序，每次选取权值最小的边，如果该边加入最小生成树后不形成回路，则将其加入最小生成树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <algorithm>
#include <climits>
#include <vector>

using namespace std;

const int N = 100010, M = 2*N;

struct Edge{
    int u, v, w;
    bool operator < (const Edge& e) const{
        return w < e.w;
    }
};

vector<Edge> edges; // 边集
int p[N]; // 记录每个节点的父节点
int n, m; // n个节点，m条边

int find(int x){
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal(){
    for(int i=1; i<=n; i++) p[i] = i;
    int res = 0, cnt = 0;
    sort(edges.begin(), edges.end());
    for(auto& e : edges){
        int u = e.u, v = e.v, w = e.w;
        int pu = find(u), pv = find(v);
        if(pu != pv){
            res += w;
            cnt++;
            p[pu] = pv;
        }
    }
    if(cnt < n-1) return INT_MAX; // 最小生成树不连通
    return res;
}

int main(){
    cin >> n >> m;
    for(int i=1; i<=m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        edges.push_back({u, v, w});
    }
    int res = kruskal();
    if(res == INT_MAX) cout << "impossible" << endl;
    else cout << res << endl;
    return 0;
}