3、算法

3.1 复杂度分析

算法复杂度分析是指对算法在执行时所需要的计算资源进行量化和评估的过程。通常，我们会关注算法的时间复杂度和空间复杂度两个方面。

时间复杂度描述的是算法执行所需要的时间，常用的表示方法是“大O记法”。具体来说，假设算法的输入规模为n，时间复杂度为T(n)，则可以用O(T(n))来描述算法的时间复杂度。在实际分析中，我们通常关注算法的最坏情况时间复杂度，即算法在所有可能的输入中所需要的最长时间。

空间复杂度描述的是算法在执行时所需要的空间，同样用O记法表示。通常情况下，空间复杂度主要取决于算法所需要的额外存储空间。

算法复杂度分析是衡量算法效率的重要方法。在算法设计中，我们需要综合考虑时间复杂度和空间复杂度，并在这两个指标之间做出权衡和折衷，以满足实际需求。

3.1.1 空间复杂度分析

空间复杂度分析是对算法所占用的内存空间的量化评估。通常用算法所需要的额外空间大小来评估空间复杂度。

算法的空间复杂度一般分为以下几种情况：

常数空间：只需要固定大小的额外空间，与输入数据的规模大小无关。
线性空间：算法需要的额外空间与输入数据的规模线性相关，即 O(n)。
二次方空间：算法需要的额外空间与输入数据的规模平方相关，即 O(n²)。
对数空间：算法需要的额外空间与输入数据的规模的对数相关，即 O(log n)。

对于常见的算法和数据结构，我们可以通过手动计算和分析，或者通过代码实现中使用工具函数来估算其空间复杂度。在实际应用中，我们通常需要对算法进行空间优化，以使其在占用尽可能少的内存的前提下能够满足我们的需求。

3.1.2 时间复杂度分析

时间复杂度是算法效率的一种度量，通常用大O符号表示。它表示算法执行时间随着问题规模n的增长而增长的数量级。具体来说，如果算法在处理规模为n的问题时所需要的基本操作数是f(n)，那么它的时间复杂度就是O(f(n))。

在分析算法的时间复杂度时，通常需要分析算法中每个操作的时间复杂度，并考虑它们执行的次数。常见的操作包括：

基本操作，例如赋值、比较、算术运算等，它们的时间复杂度通常是O(1)。
循环操作，例如for循环、while循环等，它们的时间复杂度取决于循环体内部操作的时间复杂度以及循环次数。
条件分支，例如if语句、switch语句等，它们的时间复杂度取决于条件表达式的计算复杂度以及不同分支的执行次数。
函数调用，例如递归函数、库函数等，它们的时间复杂度取决于函数本身的复杂度以及调用次数。

在分析时间复杂度时，常用的方法包括：

用常数替代运行时间中的常数项。
只保留运行时间中的最高次幂项。
如果运行时间中存在多个最高次幂项，则保留最大的一个。
忽略运行时间中的低次幂项。
忽略运行时间中的常数项。

例如，如果一个算法的时间复杂度是O(n² + n)，那么它的时间复杂度可以简化为O(n²)。

总之，分析算法的时间复杂度是算法设计和优化的重要方法，它可以帮助我们评估算法的效率和性能，从而选择最优的算法解决问题。

3.2 基础算法

3.2.1 分治算法

分治算法是一种基于分而治之思想的算法，它将问题分解成多个子问题，然后将这些子问题递归地求解，最后将这些子问题的解合并起来，得到原问题的解。

分治算法一般适用于问题可分为多个子问题，且子问题与原问题有着相同的解决思路。分治算法常见的应用包括：

归并排序：将数组分成两个部分，分别排序，再将两个有序的子数组合并成一个有序的数组。时间复杂度为O(nlogn)。
快速排序：选定一个基准元素，将数组分成两个部分，小于基准元素的放在左边，大于基准元素的放在右边，再分别对左右两个部分进行递归排序。时间复杂度平均为O(nlogn)，最坏情况为O(n²)。
二分搜索：将有序数组分成两个部分，判断目标值在哪个部分，再在相应的部分进行递归搜索。时间复杂度为O(logn)。
最大子序列和：将数组分成两个部分，分别计算左半部分的最大子序列和、右半部分的最大子序列和和跨越中点的最大子序列和，取三者的最大值。时间复杂度为O(nlogn)。
棋盘覆盖：将棋盘分成四个部分，每个部分再递归地用相同的方式进行覆盖，直到棋盘被完全覆盖。时间复杂度为O(4^n)。
求逆序对：将数组分成两个部分，分别求出左半部分的逆序对数、右半部分的逆序对数和跨越中点的逆序对数，取三者之和即可。时间复杂度为O(nlogn)。
求凸包：将点集分成两个部分，分别求出左半部分的凸包、右半部分的凸包，再将两个凸包合并。时间复杂度为O(nlogn)。
最近点对：将点集按照x坐标排序，分成两个部分，分别求出左半部分的最近点对、右半部分的最近点对和跨越中点的最近点对，取三者中距离最小的即可。时间复杂度为O(nlogn)。
多项式求值：将多项式分成两个部分，分别递归求解左半部分和右半部分，再将两个结果合并。时间复杂度为O(nlogn)。

以上应用仅为分治算法的部分应用，实际上分治算法还有很多其他的应用。

分治算法的基本步骤包括：

分解原问题为若干个子问题。
解决子问题，若子问题规模足够小，则直接求解。
合并子问题的解，得到原问题的解。

分治算法的时间复杂度一般为\(O(nlogn)\)，其中\(n\)为问题的规模。这是因为分治算法的主要时间开销在于将问题分解为子问题以及将子问题的解合并。在每一层递归中，问题的规模会减半，所以分治算法的时间复杂度为\(O(logn)\)。而在每一层递归中，需要将子问题的解合并，这一过程需要\(O(n)\)的时间，所以分治算法的总时间复杂度为\(O(nlogn)\)。

在实际应用中，分治算法的时间复杂度还会受到分解子问题的效率、合并子问题的效率以及递归深度等因素的影响。因此，在实际应用中，需要根据问题的特点和实际情况综合考虑各种因素，确定最适合的算法。

分治算法常见的应用包括归并排序、快速排序、线性时间选择、求逆序对等。下面分别给出这几种算法的C++代码实现。

1.归并排序

归并排序是一种典型的分治算法，其基本思想是将待排序的序列分成若干个子序列，每个子序列都是有序的，然后再将子序列合并成整体有序的序列。

以下是归并排序的代码：

C++
#include <iostream>
#include <vector>

using namespace std;

void merge(vector<int>& nums, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    vector<int> L(n1), R(n2);
    for (int i = 0; i < n1; ++i) {
        L[i] = nums[left + i];
    }
    for (int i = 0; i < n2; ++i) {
        R[i] = nums[mid + i + 1];
    }
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            nums[k++] = L[i++];
        } else {
            nums[k++] = R[j++];
        }
    }
    while (i < n1) {
        nums[k++] = L[i++];
    }
    while (j < n2) {
        nums[k++] = R[j++];
    }
}

void mergeSort(vector<int>& nums, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }
}

int main() {
    vector<int> nums{5, 2, 4, 7, 1, 3, 2, 6};
    mergeSort(nums, 0, nums.size() - 1);
    for (auto num : nums) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

2.快速排序

快速排序也是一种典型的分治算法，其基本思想是通过一趟排序将待排序序列分成两部分，其中一部分的所有元素都比另一部分的元素小，然后再对这两部分分别进行快速排序。

以下是快速排序的代码：

C++
#include <iostream>
#include <vector>

using namespace std;

int partition(vector<int>& nums, int left, int right) {
    int pivot = nums[right];
    int i = left;
    for (int j = left; j < right; ++j) {
        if (nums[j] <= pivot) {
            swap(nums[i++], nums[j]);
        }
    }
    swap(nums[i], nums[right]);
    return i;
}

void quickSort(vector<int>& nums, int left, int right) {
    if (left < right) {
        int pivotIndex = partition(nums, left, right);
        quickSort(nums, left, pivotIndex - 1);
        quickSort(nums, pivotIndex + 1, right);
    }
}

int main() {
    vector<int> nums{5, 2, 4, 7, 1, 3, 2, 6};
    quickSort(nums, 0, nums.size() - 1);
    for (auto num : nums) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

3.线性时间选择

C++
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 寻找中位数的中位数
int findMedian(vector<int>& nums, int l, int r) {
    sort(nums.begin() + l, nums.begin() + r + 1);
    return nums[(l + r) / 2];
}

// 将中位数放到左边第一个位置
int partition(vector<int>& nums, int l, int r, int pivot) {
    int i = l, j = r;
    while (i <= j) {
        while (nums[i] < pivot) i++;
        while (nums[j] > pivot) j--;
        if (i <= j) {
            swap(nums[i], nums[j]);
            i++;
            j--;
        }
    }
    return i - 1;
}

int select(vector<int>& nums, int l, int r, int k) {
    if (l == r) return nums[l];
    int pivot = findMedian(nums, l, r);
    int index = partition(nums, l, r, pivot);
    int count = index - l + 1;
    if (k == count) {
        return nums[index];
    } else if (k < count) {
        return select(nums, l, index - 1, k);
    } else {
        return select(nums, index + 1, r, k - count);
    }
}

int main() {
    vector<int> nums = {5, 1, 3, 2, 4};
    int k = 3;
    int result = select(nums, 0, nums.size() - 1, k);
    cout << "The " << k << "th smallest element is: " << result << endl;
    return 0;
}

该算法的时间复杂度为O(n)，其中n为序列中元素的个数。

4.求逆序对

求逆序对也是一种常见的分治算法，其基本思想是将待排序的序列分成两部分，递归求解每个子问题的逆序对数目，然后合并两个有序子序列，并计算跨越两个子序列的逆序对数目。

以下是求逆序对的代码：

C++
#include <iostream>
#include <vector>

using namespace std;

long long merge(vector<int>& nums, int left, int mid, int right) {
    vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    long long count = 0;
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            temp[k++] = nums[i++];
        } else {
            temp[k++] = nums[j++];
            count += mid - i + 1;
        }
    }
    while (i <= mid) {
        temp[k++] = nums[i++];
    }
    while (j <= right) {
        temp[k++] = nums[j++];
    }
    for (int p = 0; p < temp.size(); ++p) {
        nums[left + p] = temp[p];
    }
    return count;
}

long long mergeSort(vector<int>& nums, int left, int right) {
    if (left >= right) {
        return 0;
    }
    int mid = left + (right - left) / 2;
    long long count = 0;
    count += mergeSort(nums, left, mid);
    count += mergeSort(nums, mid + 1, right);
    count += merge(nums, left, mid, right);
    return count;
}

long long countInversions(vector<int>& nums) {
    return mergeSort(nums, 0, nums.size() - 1);
}

int main() {
    vector<int> nums = {7, 5, 6, 4};
    cout << "The number of inversions is: " << countInversions(nums) << endl;
    return 0;
}

该代码实现了基于归并排序的求逆序对的算法。时间复杂度为 \(O(n\log n)\)，空间复杂度为 \(O(n)\)。其中 merge 函数实现了合并两个有序数组并统计逆序对数量的功能， mergeSort 函数实现了归并排序的过程，并在过程中调用了 merge 函数统计逆序对数量。最后在 countInversions 函数中调用 mergeSort 函数，返回最终的逆序对数量。

3.3 排序算法

3.3.1 归并排序

归并排序（Merge Sort）是一种基于分治策略的排序算法。它将原序列分成若干个子序列，对每个子序列进行排序，然后再将排好序的子序列合并成一个有序序列。归并排序的时间复杂度为 \(O(n \log n)\)，是一种稳定的排序算法。

下面是归并排序的详细步骤及C++代码实现。

将原序列划分为两个子序列，每个子序列包含大约相等数量的元素。
递归地对两个子序列进行归并排序。
将排好序的子序列合并成一个有序序列。

步骤 2 和步骤 3 都是递归执行的，递归的边界条件是序列中只有一个元素或没有元素。

C++代码实现：

C++
#include <iostream>
#include <vector>

using namespace std;

// 合并两个有序序列
void merge(vector<int>& nums, int left, int mid, int right) {
    vector<int> temp(right - left + 1); // 临时数组存储归并后的序列
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            temp[k++] = nums[i++];
        } else {
            temp[k++] = nums[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = nums[i++];
    }
    while (j <= right) {
        temp[k++] = nums[j++];
    }
    for (int p = 0; p < k; ++p) {
        nums[left + p] = temp[p];
    }
}

// 归并排序
void mergeSort(vector<int>& nums, int left, int right) {
    if (left >= right) {
        return;
    }
    int mid = (left + right) / 2;
    mergeSort(nums, left, mid);
    mergeSort(nums, mid + 1, right);
    merge(nums, left, mid, right);
}

int main() {
    vector<int> nums = {3, 5, 1, 6, 2, 4};
    mergeSort(nums, 0, nums.size() - 1);
    for (int num : nums) {
        cout << num << " ";
    }
    return 0;
}

输出结果为：

Text Only
1 2 3 4 5 6

归并排序的时间复杂度为 \(O(n \log n)\)，空间复杂度为 \(O(n)\)。

3.3.2 快速排序

快速排序（Quick Sort）是一种高效的排序算法，它是通过将一个序列分割成两个子序列来进行排序的，也是分治法的一个经典例子。

快速排序的基本思路是：从序列中选择一个元素作为基准（pivot），将序列中所有小于基准的元素放到基准的左边，所有大于基准的元素放到基准的右边，然后对左右两个子序列分别进行递归排序。

具体来说，快速排序的算法过程如下：

选择一个基准元素，将序列分为左右两个子序列。
对左右子序列分别递归调用快速排序，直到序列长度为1或0。
合并左子序列、基准元素和右子序列，得到有序序列。

快速排序的时间复杂度为 \(O(nlogn)\)，空间复杂度为 \(O(logn)\)。

下面是快速排序的 C++ 代码实现：

C++
#include <iostream>
#include <vector>

using namespace std;

int partition(vector<int>& nums, int left, int right) {
    int pivot = nums[left]; // 选取左侧元素为pivot
    int i = left + 1, j = right; // i指向左侧第一个大于pivot的元素，j指向右侧第一个小于等于pivot的元素
    while (i <= j) {
        if (nums[i] <= pivot) { // 如果nums[i]小于等于pivot，则继续向右寻找
            i++;
        } else if (nums[j] > pivot) { // 如果nums[j]大于pivot，则继续向左寻找
            j--;
        } else { // 否则，交换nums[i]和nums[j]的位置
            swap(nums[i], nums[j]);
        }
    }
    swap(nums[left], nums[j]); // 将pivot放在正确的位置上
    return j;
}

void quickSort(vector<int>& nums, int left, int right) {
    if (left >= right) return; // 递归边界
    int pivotIndex = partition(nums, left, right); // 获取pivot的位置
    quickSort(nums, left, pivotIndex - 1); // 对pivot左侧的子数组进行快速排序
    quickSort(nums, pivotIndex + 1, right); // 对pivot右侧的子数组进行快速排序
}

void quickSort(vector<int>& nums) {
    quickSort(nums, 0, nums.size() - 1); // 对整个数组进行快速排序
}

int main() {
    vector<int> nums = {5, 1, 9, 3, 7, 4, 8, 6, 2};
    quickSort(nums);
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

快速排序的时间复杂度为O(nlogn)，其中n为待排序数组的长度。但最坏情况下时间复杂度会退化到O(n²)。

3.3.3 堆排序

堆排序（Heap Sort）是一种基于比较的排序算法，通过维护一个堆来完成排序，堆是一个完全二叉树，它可以被看做是一棵树形的数组。堆排序的时间复杂度为O(nlogn)，空间复杂度为O(1)，是一种高效的排序算法。

堆排序的基本思路如下：

将待排序序列构造成一个大根堆或小根堆；
依次将堆顶元素（最大值或最小值）与堆末元素交换，然后重新调整堆，使其满足堆的性质；
重复步骤2，直到整个序列有序。

在实现上，我们通常采用数组来存储堆，因为堆是一棵完全二叉树，因此可以用数组来表示。对于每个节点i，其左子节点是2i，右子节点是2i+1，父节点是i/2。对于大根堆，堆中每个节点的值都大于或等于其子节点的值；对于小根堆，堆中每个节点的值都小于或等于其子节点的值。

下面是堆排序的C++代码实现：

C++
#include <iostream>
#include <vector>

using namespace std;

// 堆排序
void heap_sort(vector<int>& nums) {
    int n = nums.size();

    // 构建初始堆，从最后一个非叶子节点开始向下调整
    for (int i = n / 2 - 1; i >= 0; i--) {
        int j = i;
        int temp = nums[j];
        int k = 2 * j + 1;
        while (k < n) {
            if (k + 1 < n && nums[k + 1] > nums[k]) k++;
            if (nums[k] > temp) {
                nums[j] = nums[k];
                j = k;
                k = 2 * j + 1;
            } else {
                break;
            }
        }
        nums[j] = temp;
    }

    // 依次将堆顶元素（最大元素）放到序列末尾
    for (int i = n - 1; i >= 1; i--) {
        swap(nums[0], nums[i]);
        int j = 0;
        int temp = nums[j];
        int k = 2 * j + 1;
        while (k < i) {
            if (k + 1 < i && nums[k + 1] > nums[k]) k++;
            if (nums[k] > temp) {
                nums[j] = nums[k];
                j = k;
                k = 2 * j + 1;
            } else {
                break;
            }
        }
        nums[j] = temp;
    }
}

int main() {
    vector<int> nums = {3, 7, 4, 2, 1, 5, 6, 8};
    heap_sort(nums);
    for (int num : nums) {
        cout << num << " ";
    }
    return 0;
}

其中，heap_sort函数表示堆排序的实现，其时间复杂度为\(O(n \log n)\)。在该函数中，先通过循环从最后一个非叶子节点开始向下调整，将数组构建成一个初始的大根堆。然后再依次将堆顶元素（最大元素）放到序列末尾，每次操作后从堆顶开始向下调整，维护大根堆的性质。最后得到有序序列。

3.3.4 树形选择排序（锦标赛排序）

树形选择排序，也叫锦标赛排序（Tournament Sort），是一种排序算法，它使用二叉树的结构进行排序。它的基本思路是，首先将输入序列看作n个二元竞赛的胜者，然后递归地将胜者进行比较，直到只剩下一个胜者为止。这个胜者即为整个序列的最小值。

下面是树形选择排序的具体实现：

C++
#include <iostream>
using namespace std;

const int MAXN = 1 << 20;
int n, m, a[MAXN], b[MAXN];

// 对于一个二元竞赛，找出其胜者的编号
int get_winner(int x, int y) {
    return a[x] < a[y] ? x : y;
}

// 计算比赛的比较轮数
int get_log(int n) {
    int logn = 0;
    while ((1 << logn) < n) {
        logn++;
    }
    return logn;
}

// 进行一轮比赛，将胜者放到下一轮
void play_round(int cur, int nxt) {
    for (int i = 0; i < n; i += 2) {
        int winner = get_winner(a[i], a[i + 1]);
        b[i >> 1] = winner;
    }
    if (n & 1) {
        b[n >> 1] = a[n - 1];
    }
    swap(a, b);
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int logn = get_log(n);
    m = 1 << logn;
    for (int i = n; i < m; i++) {
        a[i] = MAXN;  // 将序列补齐成2的幂次方
    }

    for (int i = 0; i < logn; i++) {
        play_round(i, i + 1);
    }

    cout << a[0] << endl;  // 输出最小值

    return 0;
}

上面的代码实现了树形选择排序算法，其中get_winner函数表示一个二元竞赛的胜者编号，get_log函数计算比赛的比较轮数，play_round函数进行一轮比赛并将胜者放到下一轮，最后输出整个序列的最小值。

3.3.5 桶排序

桶排序是一种基于计数的排序算法，它将元素按照一定的映射函数分配到不同的桶中，然后对每个桶中的元素进行排序，最后按照顺序将每个桶中的元素合并起来。

具体实现时，需要确定映射函数和桶的数量。映射函数可以根据数据分布情况来选择，而桶的数量则取决于数据规模。桶排序的时间复杂度是O(n)，但是它需要额外的空间来存储桶。

以下是一个使用桶排序实现从小到大排序的C++代码示例：

C++
void bucketSort(vector<int>& nums) {
    int n = nums.size();
    if (n <= 1) return;

    int maxVal = *max_element(nums.begin(), nums.end());
    int minVal = *min_element(nums.begin(), nums.end());
    int bucketSize = max(1, (maxVal - minVal) / (n - 1));  // 每个桶的大小

    int bucketNum = (maxVal - minVal) / bucketSize + 1;  // 桶的数量
    vector<vector<int>> buckets(bucketNum);  // 桶

    for (int num : nums) {
        int idx = (num - minVal) / bucketSize;  // 计算应该放在哪个桶中
        buckets[idx].push_back(num);  // 把元素放入桶中
    }

    int idx = 0;
    for (auto& bucket : buckets) {
        sort(bucket.begin(), bucket.end());  // 桶内元素排序
        for (int num : bucket) {
            nums[idx++] = num;  // 把桶中元素合并到原数组中
        }
    }
}

在上述代码中，我们首先计算了桶的数量和每个桶的大小，然后把元素放入对应的桶中，最后对每个桶内的元素进行排序，并把排序后的元素合并到原数组中。

3.3.6 基数排序

基数排序是一种非比较排序算法，它通过将待排序数据按照位数切割成不同的数字，然后按每个位数分别比较。基数排序可以实现稳定排序，适用于整数排序。下面是基数排序的基本思想：

首先找到待排序数组中的最大值，确定需要比较的位数（以位数最多的数为准）；
从最低位开始，按照位数进行排序，对于每个位数，使用稳定排序算法对数据进行排序；
对于每一轮排序后的结果，按照排序结果重新构造待排序数组，继续按照下一位进行排序，直到排序完成。

下面是基数排序的C++代码实现：

C++
// 获取整数num的第d位数上的数字
int getDigit(int num, int d) {
    return (num / static_cast<int>(pow(10, d - 1))) % 10;
}

// 基数排序
void radixSort(vector<int>& nums) {
    if (nums.empty()) {
        return;
    }

    // 获取最大值
    int maxVal = nums[0];
    for (int i = 1; i < nums.size(); ++i) {
        if (nums[i] > maxVal) {
            maxVal = nums[i];
        }
    }

    // 获取最大位数
    int maxDigit = 0;
    while (maxVal > 0) {
        maxVal /= 10;
        ++maxDigit;
    }

    vector<int> temp(nums.size());
    vector<int> count(10);
    int radix = 1;
    for (int i = 1; i <= maxDigit; ++i) {
        // 统计每个桶中元素的个数
        count.assign(10, 0);
        for (int j = 0; j < nums.size(); ++j) {
            int digit = getDigit(nums[j], i);
            ++count[digit];
        }

        // 将桶的索引进行调整
        for (int j = 1; j < 10; ++j) {
            count[j] += count[j - 1];
        }

        // 排序
        for (int j = nums.size() - 1; j >= 0; --j) {
            int digit = getDigit(nums[j], i);
            temp[count[digit] - 1] = nums[j];
            --count[digit];
        }

        // 更新数组
        nums = temp;
    }
}

基数排序的时间复杂度为O(d(n+k))，其中d为位数，k为进制数，n为待排序元素个数。基数排序的空间复杂度为O(n+k)，其中k为进制数。基数排序是一种稳定排序算法，适用于整数排序。

3.4 字符串相关算法

3.4.1 字符串匹配算法——KMP

KMP算法（Knuth-Morris-Pratt算法）是一种字符串匹配算法，能够高效地解决在一个文本串S内查找一个模式串P的问题。

算法步骤如下：

对模式串P进行预处理，得到一个next数组，其中next[i]表示P的前缀子串(包括第一个字符，不包括第i个字符)中，最长的既是前缀又是后缀的字符串的长度。
对文本串S进行匹配。遍历S的每个字符，设当前匹配到S的第i个字符和P的第j个字符，若S[i] == P[j]，则i和j都加1。否则，将j更新为next[j]。

KMP算法的核心在于求解next数组。可以使用动态规划的思想，将问题转化为最长公共前后缀问题。具体地，设P的前缀子串P[0..k]的最长的既是前缀又是后缀的字符串长度为next[k]，则next[k+1] = next[k]+1，若P[next[k+1]] != P[k+1]，则将next[k+1]更新为next[next[k+1]]，直到找到一个位置p，使得P[next[k+1]] == P[k+1]，此时next[k+1] = p+1。

以下是KMP算法的C++代码实现：

C++
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

void get_next(string p, vector<int>& next) {
    int n = p.length();
    next[0] = -1;
    int k = -1, j = 0;
    while (j < n - 1) {
        if (k == -1 || p[j] == p[k]) {
            ++j;
            ++k;
            next[j] = k;
        } else {
            k = next[k];
        }
    }
}

int kmp(string s, string p) {
    int n = s.length();
    int m = p.length();
    vector<int> next(m, 0);
    get_next(p, next);

    int i = 0, j = 0;
    while (i < n && j < m) {
        if (j == -1 || s[i] == p[j]) {
            ++i;
            ++j;
        } else {
            j = next[j];
        }
    }

    if (j == m) {
        return i - j;
    } else {
        return -1;
    }
}

int main() {
    string s = "hello, world!";
    string p = "world";
    int pos = kmp(s, p);
    if (pos != -1) {
        cout << "found " << p << " in " << s << " at position " << pos << endl;
    } else {
        cout << "not found" << endl;
    }
    return 0;
}

其中，函数get_next用于计算模式串的next数组，函数kmp用于在文本串中查找模式串的位置。具体实现可以参考注释。

3.5 搜索算法

搜索算法是一种在某个搜索空间中寻找特定目标的算法。在计算机科学中，搜索算法通常用于解决一些复杂的问题，例如图论、人工智能、博弈等等。

常见的搜索算法包括广度优先搜索、深度优先搜索、A*搜索等。这些算法的具体实现方式和时间复杂度等有所不同，选择合适的搜索算法需要考虑问题的特点和复杂度等方面因素。

以下是几种搜索算法的简要介绍：

1.广度优先搜索（BFS）

广度优先搜索从起点开始，不断扩展当前节点的邻居，直到到达目标节点为止。该算法保证能够找到最短路径，但在某些情况下可能会占用大量的空间。

2.深度优先搜索（DFS）

深度优先搜索从起点开始，不断探索当前节点的所有可能路径，直到找到目标节点或者无法前进为止。该算法通常使用递归或栈来实现，具有空间复杂度较小的优点，但不能保证找到最短路径。

3.A*搜索

A*搜索是一种启发式搜索算法，利用一个估价函数（heuristic function）来评估每个节点的价值，选择当前最有可能导致解决方案的节点进行探索。该算法能够在更快的时间内找到最优解，但是需要选择合适的估价函数，否则可能会得到次优解。

4.二分搜索

二分搜索是一种高效的搜索算法，通常用于在有序数组中查找特定元素。该算法通过不断缩小搜索范围来定位目标元素，具有时间复杂度为 O(log n) 的优点。

3.5.1 搜索的剪枝优化

搜索算法的一个重要问题是如何进行剪枝优化以减少搜索空间，提高算法效率。以下是几种常见的搜索剪枝优化技术：

回溯法剪枝：回溯法是一种基于递归的搜索算法，当搜索到某一层时，如果发现当前状态已经不满足条件，就可以直接剪枝，回溯到上一层，不再继续搜索。
双向搜索：双向搜索是一种从起点和终点同时进行搜索的算法，通过在两个方向上同时进行搜索，可以减少搜索的时间和空间复杂度。
启发式搜索：启发式搜索是一种通过启发函数来指导搜索方向的算法，通过估计每个状态到目标状态的距离，优先搜索距离较近的状态，从而减少搜索空间。
前向星剪枝：前向星是一种用于存储稀疏图的数据结构，通过将图中每个点的出边存储为链表，可以减少空间复杂度。在搜索时，可以根据前向星的特点，选择从度数较大的点开始搜索，从而减少搜索空间。
双向广搜剪枝：双向广搜是一种双向搜索的变体，通过在正反两个方向上同时进行广度优先搜索，可以减少搜索空间。同时，在搜索过程中，可以根据搜索的路径长度和当前状态的估价函数值来进行剪枝，提高搜索效率。
A算法：A 算法是一种启发式搜索算法，通过综合考虑当前状态到目标状态的距离和当前状态的估价函数值，选择具有最小期望值的状态进行扩展，从而优化搜索效率。

这些搜索剪枝优化技术都是基于不同的思路来实现的，具体的实现方法和优化效果也不同。在实际应用中，需要根据具体的问题和场景选择合适的剪枝方法，以达到最优的搜索效果。

以下是常见的搜索剪枝优化技术的C++代码示例：

1.前向星+DFS+剪枝：

C++
int head[MAXN], ver[MAXM], nxt[MAXM], cnt = 1;
bool vis[MAXN];
int ans = 0;

void add(int x, int y) {
    ver[++cnt] = y;
    nxt[cnt] = head[x];
    head[x] = cnt;
}

void dfs(int u, int num) {
    if (num == 5) {  // 剪枝条件，num为当前深度
        ans++;
        return;
    }
    vis[u] = true;
    for (int i = head[u]; i; i = nxt[i]) {
        int v = ver[i];
        if (!vis[v]) {
            dfs(v, num + 1);
        }
    }
    vis[u] = false;
}

int main() {
    int n, m;
    cin >> n >> m;
    while (m--) {
        int x, y;
        cin >> x >> y;
        add(x, y);
        add(y, x);
    }
    for (int i = 1; i <= n; i++) {
        dfs(i, 1);
    }
    cout << ans / 10 << endl;
    return 0;
}

2.以下是双向BFS+剪枝的C++代码实现，用于解决从起点到终点的最短路径问题：

C++
#include <iostream>
#include <queue>
#include <unordered_set>

using namespace std;

// 双向BFS+剪枝求解最短路径
int biBFS(string beginWord, string endWord, unordered_set<string>& wordList) {
    if (beginWord == endWord) return 1; // 特判
    unordered_set<string> visited1, visited2, *visitedPtr1, *visitedPtr2; // 两个方向的visited集合
    visited1.insert(beginWord);
    visited2.insert(endWord);
    int step = 1;
    while (!visited1.empty() && !visited2.empty()) {
        if (visited1.size() > visited2.size()) { // 优化：始终选择访问节点数量较少的那一方，减少搜索的深度
            visitedPtr1 = &visited2;
            visitedPtr2 = &visited1;
            swap(beginWord, endWord);
        } else {
            visitedPtr1 = &visited1;
            visitedPtr2 = &visited2;
        }
        unordered_set<string> tmpSet; // 记录新访问的节点
        for (auto it = visitedPtr1->begin(); it != visitedPtr1->end(); it++) {
            string currWord = *it;
            for (int i = 0; i < currWord.size(); i++) { // 逐个修改当前单词的每一个字符
                char tmp = currWord[i];
                for (char c = 'a'; c <= 'z'; c++) { // 对每一个字符，枚举26个字母
                    currWord[i] = c;
                    if (visitedPtr2->count(currWord)) return step + 1; // 如果另一个方向的visited集合已包含该单词，即找到了公共节点，返回答案
                    if (wordList.count(currWord) && !visitedPtr1->count(currWord)) { // 如果wordList中包含该单词且还未被visited访问，加入tmpSet
                        tmpSet.insert(currWord);
                        visitedPtr1->insert(currWord);
                    }
                }
                currWord[i] = tmp; // 恢复当前单词的第i个字符
            }
        }
        visitedPtr1->swap(tmpSet); // 优化：用swap交换visited集合和tmpSet，避免拷贝visited集合
        step++; // 更新步数
    }
    return 0; // 未找到路径
}

int main() {
    string beginWord = "hit";
    string endWord = "cog";
    unordered_set<string> wordList = {"hot", "dot", "dog", "lot", "log"};
    cout << biBFS(beginWord, endWord, wordList) << endl; // 输出最短路径长度
    return 0;
}

以下是一个基于A*算法的启发式搜索的C++代码示例：

C++
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>

using namespace std;

const int N = 10010;

struct Point {
    int x, y;
    int f, g, h;  // f = g + h，g表示从起点到当前点的实际代价，h表示从当前点到终点的估计代价
};

struct HeapNode {
    int d;
    int x, y;

    bool operator< (const HeapNode& t) const {
        return d > t.d;  // 小根堆，距离越小优先级越高
    }
};

int n, m;
char g[N][N];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
bool st[N][N];
Point q[N * N];
priority_queue<HeapNode> heap;  // A*算法中的堆优化，存储所有待扩展的点

int manhattan(int x, int y, Point& t) {  // 曼哈顿距离
    return abs(x - t.x) + abs(y - t.y);
}

int a_star(Point start, Point end) {
    start.f = 0;
    start.g = 0;
    start.h = manhattan(start.x, start.y, end);

    heap.push({start.f, start.x, start.y});

    while (heap.size()) {
        auto t = heap.top();
        heap.pop();

        int x = t.x, y = t.y;

        if (st[x][y]) continue;
        st[x][y] = true;

        if (x == end.x && y == end.y) return t.d;  // 找到终点

        for (int i = 0; i < 4; i++) {
            int a = x + dx[i], b = y + dy[i];

            if (a < 0 || a >= n || b < 0 || b >= m) continue;
            if (g[a][b] == '#') continue;

            Point next = {a, b};
            next.g = start.g + 1;
            next.h = manhattan(a, b, end);
            next.f = next.g + next.h;

            heap.push({next.f, a, b});
        }
    }

    return -1;  // 无法到达终点
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> g[i];

    Point start = {0, 0}, end = {0, 0};
    cin >> start.x >> start.y >> end.x >> end.y;

    int distance = a_star(start, end);

    cout << distance << endl;

    return 0;
}

在上述代码中，我们定义了两个结构体，Point表示二维平面上的一个点，其中f表示该点的估价函数值，g表示该点到起点的实际代价，h表示该点到终点的估计代价。HeapNode表示堆优化算法中的堆节点，其中d表示该节点的估价。

以下是一个使用A*算法的启发式搜索的C++代码示例，用于求解八数码问题：

C++
#include <bits/stdc++.h>
using namespace std;

const int N = 3;  // N为八数码的边长

struct Board {
    int b[N][N];   // 存放八数码的矩阵
    int space;     // 存放0的位置
    int score;     // 估价函数的值
    int step;      // 当前的步数

    // 计算估价函数的值
    void calc_score() {
        int h = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (b[i][j] == 0) continue;
                int x = (b[i][j] - 1) / N;
                int y = (b[i][j] - 1) % N;
                h += abs(i - x) + abs(j - y);
            }
        }
        score = h + step;
    }

    bool operator < (const Board& o) const {
        return score > o.score;   // 优先队列的比较函数
    }
};

const int dx[] = {-1, 0, 1, 0};  // 用于计算空格的邻居位置
const int dy[] = {0, 1, 0, -1};

Board start, goal;
unordered_map<string, int> vis;   // 存放已经访问过的状态
priority_queue<Board> q;          // 优先队列

// 判断当前状态是否合法
bool is_valid(int x, int y) {
    return x >= 0 && x < N && y >= 0 && y < N;
}

// 计算当前状态的哈希值
string get_hash(const Board& b) {
    string res;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            res += char(b.b[i][j] + '0');
        }
    }
    return res;
}

// A*算法
void A_star() {
    start.step = 0;
    start.calc_score();
    q.push(start);
    vis[get_hash(start)] = 1;

    while (!q.empty()) {
        Board u = q.top(); q.pop();
        if (u.score > vis[get_hash(u)]) continue;

        if (get_hash(u) == get_hash(goal)) {
            cout << u.step << endl;
            return;
        }

        int sx = u.space / N, sy = u.space % N;
        for (int i = 0; i < 4; i++) {
            int nx = sx + dx[i], ny = sy + dy[i];
            if (!is_valid(nx, ny)) continue;

            Board v = u;
            v.b[sx][sy] = v.b[nx][ny];
            v.b[nx][ny] = 0;
            v.space = nx * N + ny;
            v.step++;
            v.calc_score();

            if (vis[get_hash(v)] && v.score >= vis[get_hash(v)]) continue;
            q.push(v);
            vis[get_hash(v)] = v.score;
        }
    }
}

3.5.2 记忆化搜索

记忆化搜索是一种常用的优化搜索算法，也被称为“记忆化递归”或“自顶向下的动态规划”。

其核心思想是，对于重复的状态，不必重复计算，而是把计算结果保存下来，等到需要的时候再次使用，从而避免了重复计算，提高了效率。

在实现时，通常采用递归的方式进行搜索，并在递归函数中使用一个数组或哈希表等数据结构来保存已经计算过的状态及其对应的结果。

下面是一个使用记忆化搜索解决斐波那契数列问题的简单示例代码：

C++
#include <iostream>
#include <unordered_map>

using namespace std;

unordered_map<int, long long> memo;

long long fib(int n) {
    if (n < 2) return n;
    if (memo.count(n)) return memo[n];
    memo[n] = fib(n-1) + fib(n-2);
    return memo[n];
}

int main() {
    int n = 50;
    cout << "Fibonacci(" << n << ") = " << fib(n) << endl;
    return 0;
}

在上述代码中，我们定义了一个全局变量 memo 来保存已经计算过的斐波那契数列中的每个值。在递归函数 fib() 中，我们首先判断当前需要计算的状态 n 是否已经存在于 memo 中，如果是，则直接返回 memo[n] 对应的结果；如果不是，则计算并保存到 memo 中，并返回结果。这样，在后续的计算中，如果需要用到相同的状态，就可以直接从 memo 中获取结果，避免了重复计算。

值得注意的是，在使用记忆化搜索时，由于需要用到额外的空间来存储已经计算过的状态及其结果，因此可能会带来一定的空间开销。此外，对于一些特殊的问题，可能并不适合使用记忆化搜索来进行优化，需要根据具体情况进行选择。

3.5.3 启发式搜索

启发式搜索是一种智能化的搜索算法，通过启发式函数对搜索空间进行评估，以此来指导搜索方向，提高搜索效率。其基本思路是在搜索过程中，每次选择当前状态下启发函数值最小的节点进行扩展，以期望能够快速地找到最优解或者近似最优解。常见的启发式搜索算法包括A 算法、IDA算法、D *算法等。

A 算法是一种较为经典的启发式搜索算法，其基本思路是在搜索过程中维护每个节点的启发函数值和代价值，并选取当前启发函数值和代价值之和最小的节点进行扩展。具体而言，A 算法通过评估每个节点到目标状态的距离（启发函数值），结合已经走过的路径长度（代价值），预估到达目标状态的代价，以此指导搜索方向，加速搜索过程。

IDA * 算法则是一种启发式深度优先搜索算法，其基本思路是将A*算法的启发式函数值作为深度限制，每次深度优先搜索到指定深度后进行回溯，将深度限制加一，并在新的深度限制下继续搜索，直到找到最优解为止。

D * 算法是一种增量式的启发式搜索算法，其基本思路是在搜索过程中通过更新代价函数来动态地调整启发函数值，以此更新搜索方向，提高搜索效率。D*算法主要用于在动态环境中进行路径规划，能够适应地图的变化，具有较好的实时性和效率。

下面是A*算法的C++代码实现：

C++
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAX_N = 100;
const int INF = 1e9;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};

struct State {
    int x, y, cost;
    bool operator < (const State& other) const {
        return cost > other.cost;
    }
};

int N, M;
int sx, sy, gx, gy;
char maze[MAX_N][MAX_N];
int d[MAX_N][MAX_N];

int astar() {
    priority_queue<State> pq;
    memset(d, INF, sizeof(d));
    pq.push({sx, sy, 0});
    d[sx][sy] = 0;

    while (!pq.empty()) {
        State s = pq.top();
        pq.pop();
        if (s.x == gx && s.y == gy) return s.cost;

        for (int i = 0; i < 4; i++) {
            int nx = s.x + dx[i], ny = s.y + dy[i];
            if (nx >= 0 && nx < N && ny >= 0 && ny < M && maze[nx][ny] != '#' &&
                d[nx][ny] > s.cost + 1) {
                int heuristic = abs(nx - gx) + abs(ny - gy);  // 曼哈顿距离
                pq.push({nx, ny, s.cost + 1 + heuristic});
                d[nx][ny] = s.cost + 1;
            }
        }
    }
    return -1;
}

int main() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> maze[i][j];
            if (maze[i][j] == 'S') {
                sx = i;
                sy = j;
            } else if (maze[i][j] == 'G') {
                gx = i;
                gy = j;
            }
        }
    }

    int ans = astar();
    cout << ans << endl;
    return 0;
}

该代码使用了优先队列，每次从队列中取出最小的状态，并扩展出所有相邻的状态，计算它们的代价，然后将其加入优先队列中。每个状态的代价是由其已经走的步数和到目标点的曼哈顿距离（即横向距离加上纵向距离）组成的。

该算法的时间复杂度是 \(O(E\log E)\)，其中 \(E\) 是状态的数量，即矩阵的大小。实际上，当矩阵很大时，这个时间复杂度是非常高的，因为需要计算每个状态到目标点的曼哈顿距离。但是，如果采用一些优化，比如使用双向A*算法，或者使用启发式搜索来加快计算距离的速度，那么可以大大提高算法的效率。

3.5.4 双向宽度优先搜索

双向宽度优先搜索（Bidirectional Breadth-First Search，简称双向 BFS）是一种基于 BFS 的优化算法。它是将 BFS 从一个方向扩展到两个方向的一种算法。

双向 BFS 的基本思想是同时从起点和终点开始搜索，直到两个搜索的边界出现交叉，也就是中间遇到了共同的状态。在搜索过程中，每次从当前搜索队列中选择状态数目较少的一端进行扩展，这样可以减少搜索的状态数，从而提高搜索效率。

双向 BFS 在一些搜索问题中可以极大地减少搜索时间，但是对于某些问题，其时间复杂度可能不会有太大改进。因此，在使用双向 BFS 时需要仔细分析问题特点，以确定是否适用。

以下是双向 BFS 的 C++ 代码实现：

C++
#include <iostream>
#include <queue>
#include <unordered_map>

using namespace std;

int bidirectional_bfs(unordered_map<int, int>& dict1, unordered_map<int, int>& dict2, int target) {
    queue<int> q1, q2;
    q1.push(0);
    q2.push(target);
    dict1[0] = 0;
    dict2[target] = 0;
    int steps = 0;
    while (!q1.empty() && !q2.empty()) {
        ++steps;
        if (q1.size() > q2.size()) {
            swap(q1, q2);
            swap(dict1, dict2);
        }
        int n = q1.size();
        for (int i = 0; i < n; ++i) {
            int cur = q1.front();
            q1.pop();
            for (int j = 1; j <= 6; ++j) {
                int next = cur + j;
                if (next > target) break;
                if (dict2.count(next)) return steps;
                if (!dict1.count(next)) {
                    dict1[next] = steps;
                    q1.push(next);
                }
            }
        }
    }
    return -1;
}

int main() {
    int target = 30;
    unordered_map<int, int> dict1, dict2;
    cout << bidirectional_bfs(dict1, dict2, target) << endl;
    return 0;
}

这里使用两个哈希表来分别记录从起点和终点出发的已访问状态。每次从状态数目较少的一端进行扩展，如果在另一个方向的哈希表中已经出现过当前状态，则说明找到了中间交叉点，返回搜索步数。

3.5.5 迭代加深搜索

迭代加深搜索是一种在深度优先搜索的基础上进行优化的算法，它可以在不增加空间复杂度的前提下，尽可能地接近广度优先搜索的效果。该算法的基本思想是逐步增加搜索的深度，直到找到目标节点为止。

具体来说，迭代加深搜索将深度限制从1开始逐渐增加，每次只搜索深度不超过当前深度限制的节点。在每次深度限制的增加过程中，使用深度优先搜索的方式进行遍历，并在搜索过程中记录访问过的节点。如果找到目标节点，则返回解决方案；如果到达深度限制而没有找到目标节点，则增加深度限制重新搜索。

迭代加深搜索的优点是空间复杂度低，可以避免无限制地扩展搜索树的问题，同时又能够在时间上接近广度优先搜索的效果。它适用于状态空间较小、搜索深度较深的问题，比如一些博弈问题和人工智能的搜索问题等。

以下是迭代加深搜索的C++代码示例：

C++
#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 100; // 最大状态数
int N; // N代表状态中的某个参数，具体含义根据实际情况而定
bool vis[MAXN]; // vis[i] 表示状态 i 是否被搜索过

// 深度优先搜索函数，返回值为是否搜到目标状态
bool dfs(int u, int depth, int target) {
    if (depth == 0) return u == target; // 达到最大深度
    vis[u] = true;
    bool res = false;
    // 枚举 u 的所有邻接状态
    for (int i = 0; i < N; i++) {
        if (!vis[i]) { // 状态 i 没有被搜索过
            // 这里需要根据实际情况来判断状态 u 和状态 i 是否连通
            if (状态 u 和状态 i 连通) {
                res = dfs(i, depth - 1, target);
                if (res) break;
            }
        }
    }
    vis[u] = false; // 回溯，标记状态 u 为未搜索过
    return res;
}

// 迭代加深搜索函数，返回值为是否搜到目标状态
bool iddfs(int start, int target, int max_depth) {
    // 枚举深度
    for (int depth = 0; depth <= max_depth; depth++) {
        memset(vis, false, sizeof(vis)); // 每次搜索前需要初始化 vis 数组
        if (dfs(start, depth, target)) return true;
    }
    return false; // 搜索失败
}

int main() {
    // 这里需要读入初始状态和目标状态等参数，具体根据实际情况而定
    int start = 0, target = 0, max_depth = 10;
    bool res = iddfs(start, target, max_depth);
    if (res) cout << "Found!" << endl;
    else cout << "Not found!" << endl;
    return 0;
}

以上代码中，dfs() 函数为深度优先搜索函数，iddfs() 函数为迭代加深搜索函数。在 dfs() 函数中，每次搜索到一个状态时，需要判断该状态是否已经被搜索过（即 vis 数组的值），并且需要根据实际情况判断该状态和当前状态是否连通，如果连通，则继续搜索该状态。

在 iddfs() 函数中，首先枚举搜索深度 depth，然后每次调用 dfs() 函数时将 depth 减一，并且将当前状态标记为已搜索过。如果在某个深度下搜到了目标状态，则直接返回；否则，继续枚举下一个深度。如果枚举到最大深度 max_depth 还没有搜到目标状态，则搜索失败。

3.5.6 搜索对象的压缩存储

搜索对象的压缩存储是指在搜索算法中对搜索对象进行压缩，以减小存储空间和提高搜索效率。在搜索算法中，搜索对象通常是状态或图结构，为了避免占用过多的内存空间，需要对其进行压缩存储。

在状态搜索中，可以使用哈希表等数据结构进行状态压缩存储。具体做法是将状态转换为一个唯一的整数，然后将整数作为哈希表的键进行存储。在搜索过程中，可以通过哈希表快速查找状态，从而避免重复搜索。

在图搜索中，可以使用邻接表等数据结构进行压缩存储。具体做法是将图结构转换为邻接表的形式，然后只保存必要的信息，如节点的出边和入边，以减小存储空间。

压缩存储可以有效地减小存储空间，提高搜索效率。但是，压缩存储也会带来额外的开销，如哈希表的查找和更新操作。因此，在实际应用中需要权衡存储空间和搜索效率之间的关系，选择合适的存储方式。

以下是搜索对象压缩存储的示例代码，假设我们要存储一个棋盘上的状态，其中有 \(N \times N\) 个位置，每个位置可以是空，也可以是放置了一个棋子。

首先，我们可以用一个二维数组 board 来存储这个棋盘状态，其中 board[i][j] 表示棋盘上第 \(i\) 行第 \(j\) 列的位置。如果这个位置为空，我们可以用一个特殊的字符（比如 .）表示。如果这个位置放置了一个棋子，我们可以用另一个字符（比如 X）表示。

那么对于一个 \(N \times N\) 的棋盘，我们需要 \(O(N^2)\) 的空间来存储。如果 \(N\) 很大，这个空间占用就会很大。

为了减少空间占用，我们可以采用压缩存储的方式。一种常见的方式是采用位压缩，即用一个整数（比如 unsigned int）来表示一行的状态，其中每个二进制位表示该位置是否有棋子。具体实现如下：

C++
const int MAXN = 100;
const int MAXN_BIT = 6;  // 假设 MAXN <= 64

unsigned int compress(int* row, int n) {
    unsigned int res = 0;
    for (int i = 0; i < n; i++) {
        if (row[i]) {
            res |= (1 << i);
        }
    }
    return res;
}

void decompress(unsigned int state, int* row, int n) {
    for (int i = 0; i < n; i++) {
        row[i] = (state >> i) & 1;
    }
}

其中，compress 函数用来将一行棋盘状态压缩为一个整数，decompress 函数用来将一个整数解压为一行棋盘状态。具体的实现中，我们假设棋盘的大小不超过 \(64\)，因此用一个 unsigned int 来存储一行状态，每个位置用一个二进制位表示是否有棋子。

通过上述压缩方式，我们将一行棋盘状态从需要 \(O(N)\) 的空间压缩到了需要 \(O(1)\) 的空间。因此，整个棋盘的状态可以用一个 \(N\) 元组来表示，其中每个元素都是一个 unsigned int 类型的整数，表示该行的棋盘状态。这种压缩方式可以有效地减少空间占用。

3.6 图论算法

3.6.1 Prim和kruskal等求最小生成树算法

Prim和Kruskal算法都是求解最小生成树的经典算法。最小生成树是指在一个连通无向图中，生成一个树形结构的子图，使得该子图中所有边的权值之和最小。

Prim算法是基于贪心策略的算法。它从任意一个顶点开始，每次选择距离已经生成的树最近的顶点，并将该顶点加入生成树中，直到所有的顶点都被加入为止。

具体步骤如下：

随机选择一个点作为起点，将该点加入生成树中，同时将该点到其他点的距离存入优先队列（小根堆）中。
从优先队列中取出距离生成树最近的点，将其加入生成树中，并将其到其他点的距离存入优先队列中。如果优先队列中已经存在该点，更新该点到其他点的距离。
重复第二步，直到生成树中包含所有点。

下面是Prim算法的C++代码实现：

C++
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int INF = 0x3f3f3f3f;

struct Edge {
    int to;
    int weight;
    Edge(int t, int w) : to(t), weight(w) {}
    bool operator<(const Edge& e) const {
        return weight > e.weight; // 小根堆
    }
};

vector<vector<Edge>> graph;

int prim(int start) {
    int n = graph.size();
    vector<int> dist(n, INF); // 存储到已生成树的距离
    vector<bool> visited(n, false); // 标记是否已加入生成树
    dist[start] = 0;
    priority_queue<Edge> pq;
    pq.push(Edge(start, 0));
    int result = 0;
    while (!pq.empty()) {
        int u = pq.top().to;
        pq.pop();
        if (visited[u]) {
            continue;
        }
        visited[u] = true;
        result += dist[u];
        for (auto& e : graph[u]) {
            int v = e.to;
            int w = e.weight;
            if (!visited[v] && w < dist[v]) {
                dist[v] = w;
                pq.push(Edge(v, w));
            }
        }
    }
    return result;
}

int main() {
    int n, m;
    cin >> n >> m;
    graph.resize(n);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back(Edge(v, w));
        graph[v].push_back(Edge(u, w));
    }
    int result = prim(0);
    cout << result << endl;
    return 0;
}

Kruskal算法是另一种求解最小生成树的贪心算法。它的基本思路是：将图中的所有边按照权值从小到大排序，然后按照从小到大的顺序依次选取边，如果选取的边不会形成环，则将其加入最小生成树中，否则抛弃该边。

Kruskal算法的具体步骤如下：

将图中的所有边按照权值从小到大排序；
创建一个并查集，用于判断选取的边是否形成环；
依次选取排序后的边，如果该边的两个端点不在同一个集合中，则将其加入最小生成树中，否则舍弃该边；
重复步骤3，直到选取的边数达到n-1个，其中n为图中的节点数。

下面是Kruskal算法的C++代码实现：

C++
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

// 定义边结构体
struct Edge {
    int from; // 边的起点
    int to; // 边的终点
    int weight; // 边的权值
    // 重载小于运算符，用于sort函数排序
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

const int MAX_N = 1000; // 最大节点数
int parent[MAX_N]; // 记录节点的父节点
int rank[MAX_N]; // 记录节点的深度，用于优化查找操作

// 查找节点的祖先节点
int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // 路径压缩优化
    }
    return parent[x];
}

// 合并两个节点所在的集合
void merge(int x, int y) {
    int px = find(x), py = find(y);
    if (px != py) {
        if (rank[px] < rank[py]) {
            swap(px, py);
        }
        parent[py] = px;
        if (rank[px] == rank[py]) {
            rank[px]++;
        }
    }
}

// Kruskal算法求最小生成树
int kruskal(vector<Edge>& edges, int n) {
    // 初始化节点的父节点和深度
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        rank[i] = 0;
    }

    int mst_weight = 0; // 最小生成树的权值和
    int num_edges = 0; // 已选取的边的数量

    sort(edges.begin(), edges.end()); // 将边按权值排序

    for (Edge e : edges) {
        if (num_edges == n - 1) { // 边数达到n-1，已形成一棵树
            break;
        }
        if (find(e.from) != find(e.to)) { // 判断是否形成环
            merge(e.from, e.to); // 合并两个节点
            mst_weight += e.weight; // 累加边权值
            num_edges++; // 已选取的边数+1
        }
    }

    return mst_weight;
}

int main() {
    int n, m; // n:节点数，m:边数
    cin >> n >> m;

    vector<Edge> edges(m); // 存储所有的边

    for (int i = 0; i < m; i++) {
        int from, to, weight;
        cin >> from >> to >> weight;
        edges[i] = {from, to, weight}; // 将边存入vector中
    }

    int mst_weight = kruskal(edges, n); // 计算最小生成树的权值和

    cout << mst_weight << endl;

    return 0;
}

3.6.2 求次小生成树算法

求次小生成树是在一张无向图中，求解除去最小生成树之后，权值次小的生成树。常见的算法有两种：Kruskal算法变种和Prim算法变种。

Kruskal算法变种：

首先按照Kruskal算法求出最小生成树，然后对每一条边进行判断，如果该边两端点不在同一棵树中，那么将这条边加入生成树，并记录其权值，直到加入一条边后，该生成树的边数等于点数减一。然后对记录下来的边按照权值排序，然后对每条边进行判断，如果该边两端点在同一棵树中，那么忽略这条边；否则，将这条边的权值加入到次小生成树的权值之中，然后将这条边加入次小生成树，直到加入的边数等于点数减一或者所有的边都被判断完毕。

以下是一个基于Kruskal算法变种的C++代码实现，用于求解次小生成树：

C++
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105, MAXM = 10005;

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

int n, m;
int fa[MAXN];

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

int kruskal() {
    for (int i = 1; i <= n; i++) fa[i] = i;

    sort(edges, edges + m);

    int ans = 0, cnt = 0, minw = INT_MAX;

    for (int i = 0; i < m; i++) {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        int fu = find(u), fv = find(v);
        if (fu != fv) {
            ans += w;
            fa[fu] = fv;
            cnt++;
            if (cnt == n - 1) break;
        }
    }

    for (int i = 0; i < m; i++) {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        for (int j = 1; j <= n; j++) fa[j] = j;
        int sum = 0, cnt = 0;
        for (int j = 0; j < m; j++) {
            if (i == j) continue;
            int fu = find(edges[j].u), fv = find(edges[j].v);
            if (fu != fv) {
                sum += edges[j].w;
                fa[fu] = fv;
                cnt++;
                if (cnt == n - 1) break;
            }
        }
        if (cnt == n - 1 && sum < minw && find(u) != find(v)) minw = sum + w;
    }

    return minw == INT_MAX ? -1 : minw;
}

int main() {
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges[i] = {u, v, w};
    }

    int ans = kruskal();

    cout << ans << endl;

    return 0;
}

这里使用Kruskal算法求解最小生成树，并在求解过程中记录边权最小的未被使用的边的权值，同时在每次枚举到一条边之后重新构建并查集求解当前边权次小的生成树。最后输出记录的次小边权即可。

Prim算法的变种主要有两种：Prim-Dijkstra算法和Prim-SL算法。

Prim-Dijkstra算法：在Prim算法的基础上，引入了堆优化的Dijkstra算法的思想，使用堆来存储候选边，每次取出堆顶元素（即最小的候选边），并更新与该边相连的点的候选边。这样可以有效减少Prim算法的时间复杂度。

Prim-SL算法：在Prim算法的基础上，引入了空间和时间双重优化。具体来说，该算法维护两个集合：T表示当前生成树，S表示T的补图（即所有未加入T的点）。算法的核心思想是，每次从S中选择一个离T最近的点，将其加入T，并更新其邻接点的最短距离。同时，将S中的点分为两个部分：外部点和内部点。外部点表示离T最近的点的邻接点，而内部点则表示离T最近的点之前加入T的点的邻接点。这样，每次加入一个点时，只需要更新外部点的距离即可，大大减少了时间和空间复杂度。

下面是Prim-Dijkstra算法和Prim-SL算法的C++代码实现（假设图用邻接矩阵表示）：

Prim-Dijkstra算法的C++代码实现：

C++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int INF = 0x3f3f3f3f;

int prim_dijkstra(int n, vector<vector<int>>& graph) {
    int res = 0;
    vector<int> dist(n, INF);  // 存储当前点到最小生成树的距离
    vector<bool> used(n, false);  // 存储当前点是否已加入最小生成树
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;  // 存储候选边的堆

    dist[0] = 0;
    q.push(make_pair(0, 0));  // 将起点加入候选边

    while (!q.empty()) {
        pair<int, int> p = q.top(); q.pop();
        int v = p.second;
        if (used[v]) continue;  // 已加入最小生成树，跳过

        used[v] = true;
        res += p.first;  // 将该边加入最小生成树
        for (int i = 0; i < n; ++i) {
            if (!used[i] && graph[v][i] != INF && graph[v][i] < dist[i]) {
                dist[i] = graph[v][i];
                q.push(make_pair(dist[i], i));  // 将候选边加入堆
            }
        }
    }

    return res;
}

Prim-SL算法的C++代码实现：

C++
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int INF = 0x3f3f3f3f; // 无穷大

int n, m; // n个点，m条边
vector<pair<int, int>> edges[1001]; // 邻接表存图
int vis[1001]; // 标记点是否在U集合中
int dist[1001]; // 存储U到各个点的最短距离

struct Node {
    int u, d; // u表示点的编号，d表示该点到U的最短距离
    bool operator < (const Node& other) const {
        return d > other.d; // 按最短距离从小到大排序
    }
};

// Prim-SL算法
int prim() {
    memset(vis, 0, sizeof(vis));
    memset(dist, 0x3f, sizeof(dist)); // 初始化为无穷大
    dist[1] = 0; // 选取1号点为起点
    priority_queue<Node> q; // 用优先队列维护到U的最短距离
    q.push({1, 0}); // 初始将1号点加入U集合
    int res = 0; // 存储最小生成树的边权和
    while (!q.empty()) {
        Node node = q.top();
        q.pop();
        int u = node.u;
        if (vis[u]) continue; // 如果该点已经在U集合中，则跳过
        vis[u] = 1; // 标记该点已在U集合中
        res += node.d; // 将该点与U集合的边权加入最小生成树的边权和中
        for (int i = 0; i < edges[u].size(); i++) {
            int v = edges[u][i].first;
            int w = edges[u][i].second;
            if (!vis[v] && w < dist[v]) {
                dist[v] = w;
                q.push({v, w});
            }
        }
    }
    return res;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges[u].push_back({v, w});
        edges[v].push_back({u, w});
    }
    int res = prim();
    cout << res << endl;
    return 0;
}

3.6.3 Dijkstra、bellman_ford、SPFA等求单源最短路算法

单源最短路问题是指在一个加权有向图或无向图中，从源点出发到其它各个顶点的最短路径问题。其中，加权有向图或无向图中，每条边都有一个权值或长度，源点是给定的一个顶点，求从源点到其它每个顶点的最短路径。

常见的求解单源最短路的算法有 Dijkstra 算法、Bellman-Ford 算法和 SPFA 算法。

Dijkstra 算法是一种贪心算法，它依次确定从源点到各个顶点的最短路径。Bellman-Ford 算法是一种动态规划算法，它通过对每一条边进行松弛操作，逐步减小源点到各个顶点的最短距离的估计值，最终得到每个顶点的最短距离。SPFA 算法是一种基于 Bellman-Ford 算法的优化算法，通过维护一个队列和一个数组，可以有效减少不必要的松弛操作。

下面分别介绍这三种算法的详细实现及其 C++ 代码。

以下是Dijkstra算法的C++实现代码及注释：

C++
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

const int INF = 0x3f3f3f3f; //定义无穷大
const int maxn = 1000; //定义最大顶点数

struct node {
    int to; //边的目标节点
    int w;  //边的权值
};

vector<node> G[maxn]; //使用邻接表存储图
int dis[maxn]; //存储源点到各点的最短距离
bool vis[maxn]; //标记各点是否已经确定最短距离
int n, m, s; //n表示节点数，m表示边数，s表示源点

void dijkstra() {
    memset(dis, INF, sizeof(dis)); //初始化dis数组为INF
    dis[s] = 0; //源点到自己的距离为0
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    //小根堆pq存储每个节点以及当前到源点的最短距离
    pq.push(make_pair(dis[s], s));
    while (!pq.empty()) {
        int u = pq.top().second; //堆顶为距离最小的节点
        pq.pop();
        if (vis[u]) continue; //该节点已经确定最短距离
        vis[u] = true; //标记该节点已经确定最短距离
        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u][i].to; //v为u的后继节点
            int w = G[u][i].w; //u到v的边权值
            if (!vis[v] && dis[v] > dis[u] + w) { //若v未确定最短距离，且从u到v的距离更短
                dis[v] = dis[u] + w; //更新源点到v的最短距离
                pq.push(make_pair(dis[v], v)); //加入到小根堆中
            }
        }
    }
}

int main() {
    cin >> n >> m >> s;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back({v, w}); //建图
    }
    dijkstra();
    for (int i = 1; i <= n; i++) {
        cout << dis[i] << " "; //输出源点到每个节点的最短距离
    }
    return 0;
}

下面是bellman_ford算法的C++实现代码：

C++
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int INF = 0x3f3f3f3f; // 定义无穷大

struct Edge {
    int from, to, weight;
};

int n, m; // n个点，m条边
vector<Edge> edges; // 存储所有边的信息
int dist[1005]; // 存储源点到各个点的最短距离

void bellman_ford(int s) {
    memset(dist, INF, sizeof(dist)); // 初始化距离为无穷大
    dist[s] = 0; // 源点到自己的距离为0

    for (int i = 1; i < n; i++) { // 执行n-1轮松弛操作
        for (auto& e : edges) { // 遍历所有边
            if (dist[e.from] != INF && dist[e.to] > dist[e.from] + e.weight) { // 松弛操作
                dist[e.to] = dist[e.from] + e.weight;
            }
        }
    }

    // 检查是否存在负环路
    for (auto& e : edges) {
        if (dist[e.from] != INF && dist[e.to] > dist[e.from] + e.weight) {
            cout << "存在负环路！" << endl;
            return;
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int from, to, weight;
        cin >> from >> to >> weight;
        edges.push_back({from, to, weight});
    }

    int s; // 源点编号
    cin >> s;

    bellman_ford(s);

    for (int i = 1; i <= n; i++) {
        cout << dist[i] << " ";
    }
    cout << endl;

    return 0;
}

该算法的时间复杂度为\(O(nm)\)，其中\(n\)为点数，\(m\)为边数。需要注意的是，如果存在负环路，则最短路不存在。在上面的代码中，我们通过检查所有边，判断是否存在负环路。如果存在，则输出提示信息，并结束程序。

以下是 SPFA（Shortest Path Faster Algorithm）算法的 C++ 实现代码：

C++
#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 1005;

int n, m;
int head[MAXN], dist[MAXN], vis[MAXN], cnt[MAXN];

struct Edge {
    int to, next, w;
} edge[MAXN * MAXN];

void add_edge(int u, int v, int w) {
    edge[++m].to = v;
    edge[m].next = head[u];
    edge[m].w = w;
    head[u] = m;
}

bool spfa(int s) {
    memset(dist, INF, sizeof(dist));
    memset(vis, 0, sizeof(vis));
    memset(cnt, 0, sizeof(cnt));
    queue<int> q;
    dist[s] = 0;
    vis[s] = 1;
    cnt[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].to;
            int w = edge[i].w;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!vis[v]) {
                    q.push(v);
                    vis[v] = 1;
                    cnt[v]++;
                    if (cnt[v] >= n) return false;
                }
            }
        }
    }
    return true;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        add_edge(u, v, w);
        add_edge(v, u, w); // 无向图，反向边
    }
    if (spfa(1)) {
        for (int i = 2; i <= n; i++) {
            cout << dist[i] << " ";
        }
        cout << endl;
    } else {
        cout << "存在负环" << endl;
    }
    return 0;
}

注释如下：

INF 表示一个很大的数，这里取 \(0x3f3f3f3f\)。
MAXN 表示图中最多有多少个节点。
head 数组存储每个节点的第一条边，值为该边在 edge 数组中的下标。
dist 数组存储起点到各个节点的最短距离。
vis 数组标记节点是否在队列中。
cnt 数组表示每个节点进队列的次数。
Edge 结构体表示一条边，包含终点 to、下一条边的下标 next 和权值 w。
add_edge 函数用于向图中添加一条边。
spfa 函数实现 SPFA 算法，参数 s 表示起点，返回值为 bool 类型，表示图中是否存在负环。

3.6.4 求单源次短路径算法

求单源次短路径问题是指给定一个带权有向图以及起点 \(s\)，求出从 \(s\) 出发到达其他各个顶点的次短路径（即权值仅次于最短路径的路径）。

在 Dijkstra 算法的基础上，维护一个次小距离和次小距离路径，同时利用堆优化来实现。

具体思路：

对于每个点，维护 \(dis1\) 表示到起点 \(s\) 的最短距离，\(dis2\) 表示到起点 \(s\) 的次短距离，\(p1\) 表示到 \(s\) 的最短路径，\(p2\) 表示到 \(s\) 的次短路径。
初始时，\(dis1\) 全部赋值为 \(\infty\)，\(dis2\) 全部赋值为 \(\infty\)，\(p1\) 和 \(p2\) 均为空。
每次选取堆中 \(dis1\) 最小的点 \(u\) 进行松弛操作，如果松弛后 \(dis1[v]\) 更新，则 \(dis2[v]=dis1[v]\)，\(p2[v]=p1[v]\)，同时将 \(v\) 加入堆中。如果 \(dis1[v]\) 不更新，但松弛后 \(dis2[v]\) 更新，则将 \(p1[v]\) 和 \(p2[v]\) 合并到 \(p2[v]\) 中。
最终，\(dis2\) 数组中存储的就是从 \(s\) 出发到达各个顶点的次短路径长度。

时间复杂度：\(O((m+n)\log n)\)

以下是Dijkstra算法+堆优化的C++代码实现，可以在求解单源最短路时使用堆优化以减少时间复杂度。

C++
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int INF = 0x3f3f3f3f;

struct Edge {
    int to, w;
    Edge(int _to, int _w) : to(_to), w(_w) {}
};

vector<Edge> G[10005]; // 邻接表存图
int d[10005];          // 最短路数组
bool vis[10005];       // 是否已经确定最短路
int n, m;              // 点数、边数

void dijkstra(int s) {
    memset(d, 0x3f, sizeof(d)); // 初始化为极大值，防止被更新
    memset(vis, false, sizeof(vis));
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    // 小根堆，第一维为到源点的距离，第二维为顶点编号
    d[s] = 0;
    pq.push(make_pair(d[s], s));
    while (!pq.empty()) {
        int v = pq.top().second; // 取出堆顶顶点编号
        pq.pop();
        if (vis[v]) continue; // 如果已经确定最短路，则继续下一次循环
        vis[v] = true;        // 标记为已经确定最短路
        for (auto e : G[v]) { // 遍历该顶点的所有邻接边
            if (d[e.to] > d[v] + e.w) {
                d[e.to] = d[v] + e.w; // 更新最短路
                pq.push(make_pair(d[e.to], e.to));
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back(Edge(v, w));
        G[v].push_back(Edge(u, w));
    }
    dijkstra(1);
    cout << d[n] << endl;
    return 0;
}

注：该代码中用了C++11的新特性，需要编译时加上参数 -std=c++11。

3.6.5 Floyd-Warshall算法求任意两点间的最短路和传递闭包

Floyd-Warshall算法是用于求任意两点之间的最短路的一种算法，同时也可以用于计算传递闭包。该算法采用动态规划的思想，其时间复杂度为 \(O(n^3)\)。

Floyd-Warshall算法的核心思想是对于每一对顶点 \((i, j)\)，尝试将其经过顶点 \(k\) 连接，判断是否能够获得更短的路径。具体而言，设 \(dist[i][j]\) 表示从顶点 \(i\) 到顶点 \(j\) 的最短路径长度，算法过程如下：

初始化：\(dist[i][j]=w_{ij}\)，其中 \(w_{ij}\) 表示顶点 \(i\) 到顶点 \(j\) 的边权值，若不存在该边，则为无穷大。
对于每一个顶点 \(k\)，尝试将顶点 \(i\) 到顶点 \(j\) 的路径中间插入顶点 \(k\)，更新 \(dist[i][j]\) 的值：

\(dist[i][j]\) = min(\(dist[i][j]\) + \(dist[i][k]\) +\(dist[k][j]\))

算法结束后，\(dist[i][j]\) 的值即为顶点 \(i\) 到顶点 \(j\) 的最短路径长度。

在计算传递闭包时，若存在一条从顶点 \(i\) 到顶点 \(j\) 的路径，则将 \(closure[i][j]\) 置为 1。具体而言，设 \(closure[i][j]\) 表示从顶点 \(i\) 是否可以到达顶点 \(j\)，算法过程如下：

初始化：\(closure[i][j]=1\)，若存在边 \((i,j)\)，否则 \(closure[i][j]=0\)。
对于每一个顶点 \(k\)，若顶点 \(i\) 到顶点 \(j\) 的路径经过顶点 \(k\)，则将 \(closure[i][j]\) 置为 1。

最终，\(closure[i][j]\) 的值即为顶点 \(i\) 是否可以到达顶点 \(j\)。

以下是Floyd-Warshall算法的C++代码实现（以求任意两点之间的最短路为例）：

C++
const int INF = 0x3f3f3f3f;

int dist[MAX_V][MAX_V]; // 距离矩阵
int n; // 顶点数

// Floyd-Warshall算法求所有点对之间的最短路
void floyd_warshall() {
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
}

// 判断有向图中是否存在负环
bool has_negative_cycle() {
    for (int i = 1; i <= n; ++i) {
        if (dist[i][i] < 0) {
            return true;
        }
    }
    return false;
}

其中，dist是一个二维数组，表示任意两点之间的距离，n为顶点数，INF表示正无穷。函数floyd_warshall用于求所有点对之间的最短路，函数has_negative_cycle用于判断有向图中是否存在负环。

3.6.6 有向无环图的拓扑排序算法

拓扑排序是指将有向无环图（DAG）中所有的节点排成一个线性序列，使得对于任意一对节点 u 和 v，如果存在一条从 u 到 v 的有向边，那么在序列中 u 必须出现在 v 的前面。可以理解为将 DAG 中的节点“排序”。

拓扑排序的算法流程如下：

统计所有节点的入度（即有多少条边指向该节点），初始入度为 0 的节点加入一个队列；
取出队首节点，将该节点加入结果序列中，并将该节点指向的所有节点入度减 1；
如果入度减为 0，将该节点加入队列；
重复 2、3 步骤，直到队列为空。

拓扑排序算法的时间复杂度为 O(n+m)，其中 n 为节点数，m 为边数。

下面是一个实现拓扑排序的 C++ 代码示例：

C++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 1000;
int N, M; // N表示图中的节点数，M表示图中的边数
vector<int> G[MAXN+1]; // 邻接表存储图
int in_degree[MAXN+1]; // 记录每个节点的入度
vector<int> topological_order; // 记录拓扑排序结果

void topological_sort()
{
    // 初始化入度数组
    for(int i = 1; i <= N; i++)
        in_degree[i] = 0;
    for(int i = 1; i <= N; i++)
        for(int j = 0; j < G[i].size(); j++)
            in_degree[G[i][j]]++;

    // 利用优先队列实现拓扑排序
    priority_queue<int, vector<int>, greater<int>> pq;
    for(int i = 1; i <= N; i++)
        if(in_degree[i] == 0)
            pq.push(i);
    while(!pq.empty())
    {
        int u = pq.top();
        pq.pop();
        topological_order.push_back(u);
        for(int i = 0; i < G[u].size(); i++)
        {
            int v = G[u][i];
            in_degree[v]--;
            if(in_degree[v] == 0)
                pq.push(v);
        }
    }
}

int main()
{
    // 读入图中的节点数和边数
    cin >> N >> M;
    // 读入图中的边
    for(int i = 0; i < M; i++)
    {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
    }
    // 对图进行拓扑排序
    topological_sort();
    // 输出拓扑排序结果
    for(int i = 0; i < topological_order.size(); i++)
        cout << topological_order[i] << " ";
    cout << endl;
    return 0;
}

3.6.7 求欧拉道路和欧拉回路算法

欧拉道路和欧拉回路是图论中常见的概念。欧拉道路是指经过图中每条边恰好一次的路径，而欧拉回路则是指经过图中每条边恰好一次的回路（起点和终点重合）。

Hierholzer算法是一种求解欧拉回路和欧拉道路的经典算法，时间复杂度为\(O(m)\)。以下是该算法的步骤：

任选一个点作为起点，随意选择一个与该点相邻的点，并走过这条边。
如果这个点还有未走过的边，则重复步骤1；否则将该点加入到一个栈中，并返回到上一个点。
如果上一个点还有未走过的边，则重复步骤1；否则将该点加入到栈中，并返回到上一个点。
重复步骤3，直到返回到起点。
栈中的点就是欧拉回路的路径。

需要注意的是，如果图中存在欧拉道路，我们只需保证起点和终点的度数分别为奇数和偶数即可。如果图中不存在欧拉回路或欧拉道路，则算法无法求解。

以下是使用 Hierholzer 算法求欧拉回路的 C++ 代码实现：

C++
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

void dfs(vector<vector<int>>& graph, int cur, vector<bool>& visited, stack<int>& stk) {
    visited[cur] = true;
    for (int i = 0; i < graph[cur].size(); ++i) {
        int next = graph[cur][i];
        if (!visited[next]) {
            dfs(graph, next, visited, stk);
        }
    }
    stk.push(cur);
}

vector<int> findEulerPath(vector<vector<int>>& graph, int start) {
    vector<int> res;
    if (graph.empty()) return res;

    // 统计每个节点的入度和出度
    vector<int> inDegree(graph.size()), outDegree(graph.size());
    for (int i = 0; i < graph.size(); ++i) {
        for (int j = 0; j < graph[i].size(); ++j) {
            int next = graph[i][j];
            ++outDegree[i];
            ++inDegree[next];
        }
    }

    // 判断是否存在欧拉回路
    int numStartNodes = 0, numEndNodes = 0;
    for (int i = 0; i < graph.size(); ++i) {
        if (inDegree[i] == outDegree[i]) {
            continue;
        } else if (inDegree[i] == outDegree[i] + 1) {
            ++numEndNodes;
            start = i;
        } else if (inDegree[i] + 1 == outDegree[i]) {
            ++numStartNodes;
        } else {
            return res;
        }
    }
    if (numStartNodes > 1 || numEndNodes > 1) {
        return res;
    }

    // Hierholzer算法求欧拉回路
    stack<int> stk;
    vector<bool> visited(graph.size(), false);
    dfs(graph, start, visited, stk);
    while (!stk.empty()) {
        int cur = stk.top();
        stk.pop();
        res.push_back(cur);
    }
    reverse(res.begin(), res.end());
    return res;
}

其中 findEulerPath 函数接受邻接表形式的图和起始节点 start，返回欧拉回路的节点序列。如果给定的图不存在欧拉回路，则返回空序列。

Fleury算法是求解欧拉道路和欧拉回路的一种经典算法，其基本思想是贪心地选择一个尽可能“独立”的边进行扩展，直到无法扩展为止。

具体实现如下：

从任意一个顶点开始，进行深度优先搜索（DFS）；
每次选择一条未被访问过的边进行扩展，如果这条边不是桥边（从连通图中删除后，图不再连通），则选择该边，否则跳过；
如果无法选择边进行扩展，则回溯到上一个顶点，并退回到上一个顶点的搜索状态，重新开始选择边进行扩展，直到搜索完成。

C++
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 510;

int n, m;
int g[N][N];  // 存储图的邻接矩阵
int degree[N];  // 存储每个点的度数
bool st[N];  // 存储每个点是否已经被遍历

vector<int> ans;  // 存储欧拉回路/欧拉道路

void dfs(int u)
{
    for (int v = 1; v <= n; v ++ )
        if (g[u][v] && !st[g[u][v]])
        {
            st[g[u][v]] = true;  // 标记边已经被访问
            dfs(v);
        }
    ans.push_back(u);  // 将节点加入路径中
}

bool check()
{
    int cnt = 0;
    for (int i = 1; i <= n; i ++ )
        if (degree[i] & 1)
            cnt ++ ;
    if (cnt == 0 || cnt == 2) return true;
    return false;
}

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= m; i ++ )
    {
        int a, b;
        cin >> a >> b;
        g[a][b] = g[b][a] = i;  // 存储无向图的边编号
        degree[a] ++ , degree[b] ++ ;  // 更新每个点的度数
    }

    if (!check()) puts("0");  // 如果不满足欧拉回路/欧拉道路的条件，输出0
    else
    {
        for (int i = 1; i <= n; i ++ )  // 枚举每个连通块
            if (degree[i] & 1 || i == 1)  // 找到一个奇点或者是起点
            {
                dfs(i);
                break;
            }

        reverse(ans.begin(), ans.end());  // 由于我们是从起点开始遍历的，所以需要将路径翻转一下

        for (int i = 0; i < ans.size() - 1; i ++ )  // 判断路径中的每一条边是否是欧拉边
        {
            int a = ans[i], b = ans[i + 1];
            if (g[a][b]) printf("%d ", g[a][b]);  // 如果是，输出这条边的编号
        }
    }

    return 0;
}

3.6.8 二分图的构造及其判定算法

二分图是一种特殊的图，它的所有顶点可以被分成两组，使得同组中的点之间没有边相连，不同组中的点之间只有横跨两组的边相连。二分图的判定和构造问题是图论中的经典问题，常常用于实际应用中，如社交网络中的好友推荐和广告投放等。

1、二分图的判定

二分图的判定可以用染色法来实现。具体做法如下：

将任意一个顶点染成红色。
将与这个顶点相邻的顶点染成蓝色。
将与这些蓝色顶点相邻的顶点染成红色。
重复步骤2和3，直到所有的顶点都被染色。
判断染色是否合法。如果所有的边都连接了不同颜色的两个顶点，则这个图是二分图；否则不是二分图。

具体实现时，可以使用广度优先搜索（BFS）或深度优先搜索（DFS）来完成染色过程。在BFS或DFS的遍历过程中，使用一个颜色数组来记录每个顶点的颜色，初始值设为0表示未染色，1表示红色，-1表示蓝色。遍历到一个顶点时，将其染成与相邻顶点颜色不同的颜色。如果相邻顶点已经被染成了同样的颜色，则说明这个图不是二分图。

2、二分图的构造

常见的二分图构造方法之一是将图中的点划分成两组，然后在两组之间随机连边，直到得到一个满足条件的二分图。这种方法的缺点是无法保证构造出来的二分图是最大的。
另一种常见的二分图构造方法是使用匈牙利算法（也叫二分图最大匹配算法），它可以找到二分图的最大匹配，并且可以构造出一个完美匹配。具体做法是从一个点开始，依次遍历与其相邻的点，如果这些点还没有被匹配，则将它们和这个点匹配，如果已经被匹配，则尝试和匹配它的点匹配。如果成功匹配，则增加匹配数。如果无法匹配，则重新选择一个未匹配的点，重复上述过程，直到所有点都被匹配为止。
另外还有一些特殊的二分图，可以使用特殊的构造方法来构造。
基于染色法的构造方法

染色法是一种简单有效的二分图构造方法，其基本思想是给图中的每个顶点染上黑色或白色两种颜色，使得同一颜色的顶点之间没有边相连，不同颜色的顶点之间有边相连。

具体实现方法如下：

从任意一个未染色的顶点开始，将其染成黑色，并将其所有邻居染成白色。

对于所有未染色的顶点，重复上述步骤，直到所有顶点都被染色为止。

如果在染色的过程中发现某个顶点的染色冲突，即和其邻居颜色相同，则说明该图不是二分图。

代码示例：

C++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 100;  // 最大顶点数

int n, m;  // 顶点数和边数
vector<int> G[MAXN];  // 邻接表存储图
int color[MAXN];  // 存储每个顶点的颜色（1 或 -1）

// 使用染色法判断图是否为二分图
bool isBipartite() {
    // 初始化所有顶点的颜色为0
    for (int i = 0; i < n; i++) {
        color[i] = 0;
    }
    // 从每个未染色的顶点开始染色
    for (int i = 0; i < n; i++) {
        if (color[i] == 0) {
            color[i] = 1;
            queue<int> q;
            q.push(i);
            while (!q.empty()) {
                int u = q.front();
                q.pop();
                for (int j = 0; j < G[u].size(); j++) {
                    int v = G[u][j];
                    if (color[v] == 0) {
                        color[v] = -color[u];
                        q.push(v);
                    } else if (color[v] == color[u]) {
                        return false;  // 颜色冲突，不是二分图
                    }
                }
            }
        }
    }
    return true;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    if (isBipartite())
        cout << "是二分图";
    else
        cout << "不是二分图";
    return 0;
}

3.6.9 最近公共祖先

最近公共祖先（Lowest Common Ancestor，简称LCA）是指在一颗有根树上，节点p和q的LCA是指一个最深的节点，它同时是p和q的祖先节点。LCA问题常常在计算机科学中用于解决树的相关问题。

常见的LCA算法有：

倍增算法
树剖算法
Tarjan算法

这些算法都有各自的特点和适用场景。以下是倍增算法和树剖算法的简介和示例代码。

1.倍增算法

倍增算法的核心思想是先对每个节点预处理出它往上走 \(2^k\) 步所能到达的祖先节点，然后在查询时利用二进制拆分，快速跳到两个节点所在的深度相同的位置，然后往上跳直到两个节点重合，这个重合点就是它们的LCA。

下面是使用倍增算法求最近公共祖先的 C++ 代码示例：

C++
const int MAXN = 100005;  // 最大结点数
const int MAXLOG = 20;    // log2(MAXN) + 1
int n;                    // 结点数
int fa[MAXN][MAXLOG];     // fa[i][j] 表示 i 的 2^j 级祖先

// 建树（以 1 为根节点）
void buildTree() {
    // ...
}

// 预处理 fa 数组
void preProcess() {
    for (int j = 1; j < MAXLOG; j++) {
        for (int i = 1; i <= n; i++) {
            if (fa[i][j - 1] != -1) {
                fa[i][j] = fa[fa[i][j - 1]][j - 1];
            }
        }
    }
}

// 查询 u 和 v 的最近公共祖先
int LCA(int u, int v) {
    // 将 u 和 v 向上跳到同一深度
    if (dep[u] < dep[v]) {
        swap(u, v);
    }
    int diff = dep[u] - dep[v];
    for (int j = 0; j < MAXLOG; j++) {
        if (diff & (1 << j)) {
            u = fa[u][j];
        }
    }
    // 如果此时 u = v，则直接返回
    if (u == v) {
        return u;
    }
    // 一起向上跳
    for (int j = MAXLOG - 1; j >= 0; j--) {
        if (fa[u][j] != fa[v][j]) {
            u = fa[u][j];
            v = fa[v][j];
        }
    }
    // 返回它们的父亲节点
    return fa[u][0];
}

int main() {
    // 读入 n 和建树
    // ...
    // 初始化 fa 数组
    memset(fa, -1, sizeof(fa));
    // 预处理 fa 数组
    preProcess();
    // 查询最近公共祖先
    int u, v;
    while (cin >> u >> v) {
        cout << LCA(u, v) << endl;
    }
    return 0;
}

其中，dep 数组表示每个节点的深度。buildTree 函数用于建树，preProcess 函数用于预处理 fa 数组，LCA 函数用于查询两个节点的最近公共祖先。

2.树剖算法

以下是树剖算法的C++代码实现，代码中涉及到了树的建立和树剖算法的实现：

C++
#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100005;
int n, q, root = 1, cnt, head[MAXN], dep[MAXN], fa[MAXN], sz[MAXN], son[MAXN], top[MAXN], dfn[MAXN], end[MAXN];
vector<int> G[MAXN];

void addEdge(int u, int v) {
    G[u].push_back(v);
    G[v].push_back(u);
}

void dfs1(int u, int p) {
    dep[u] = dep[p] + 1;
    fa[u] = p;
    sz[u] = 1;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (v != p) {
            dfs1(v, u);
            sz[u] += sz[v];
            if (sz[v] > sz[son[u]]) {
                son[u] = v;
            }
        }
    }
}

void dfs2(int u, int p) {
    dfn[u] = ++cnt;
    end[cnt] = u;
    if (!top[u]) {
        top[u] = u;
    }
    if (son[u]) {
        top[son[u]] = top[u];
        dfs2(son[u], u);
        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u][i];
            if (v != p && v != son[u]) {
                dfs2(v, u);
            }
        }
    }
}

int lca(int u, int v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) {
            swap(u, v);
        }
        u = fa[top[u]];
    }
    return dep[u] < dep[v] ? u : v;
}

int main() {
    cin >> n >> q;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
    }
    dfs1(root, 0);
    dfs2(root, 0);
    for (int i = 1; i <= q; i++) {
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) << endl;
    }
    return 0;
}

在上述代码中，我们首先定义了全局变量n、q、root，分别表示树的节点数、询问数和根节点编号。然后，我们定义了一个邻接表G，用于存储树的边信息。在读入树的边信息后，我们通过dfs1函数预处理出树的一些基本信息，包括深度dep、父亲节点fa、子树大小sz和重儿子son。接下来，我们通过dfs2函数实现树剖算法，预处理出每个节点的dfn、end、重链顶部top和节点所在的重链。最后，在主函数中，我们对每个询问使用lca函数求出对应的最近公共祖先节点编号。

3.6.10 求强联通分量算法

求强联通分量是指在有向图中，如果存在一条从顶点 \(u\) 到顶点 \(v\) 的路径，则也一定存在一条从顶点 \(v\) 到顶点 \(u\) 的路径，那么顶点 \(u\) 和顶点 \(v\) 强联通。

常用的求解强联通分量的算法包括 Tarjan 算法和 Kosaraju 算法，下面介绍这两种算法的原理和实现。

1.Tarjan算法

Tarjan 算法采用深度优先搜索遍历整个图，在搜索的过程中对每个节点进行标记，用“时间戳”（时间戳是指在遍历中第几个被访问到的节点）记录每个节点第一次被访问的时间戳 \(dfn_i\) 和可以回溯到的最早的时间戳 \(low_i\)。如果 \(low_i=dfn_i\)，则该节点及其后继节点构成一个强连通分量。

具体实现中，需要使用一个栈记录搜索的路径，每次访问一个节点时，先将该节点入栈，并将时间戳设为当前时间戳。然后遍历该节点的后继节点，如果后继节点没有被访问，则继续对该节点进行深度优先搜索，如果后继节点已经被访问过并且还在栈中，那么更新该节点的 \(low\) 值为该节点和后继节点的 \(dfn\) 值中的最小值。如果后继节点已经被访问过并且不在栈中，那么该节点和后继节点之间的路径不包含环，因此更新该节点的 \(low\) 值为后继节点的 \(dfn\) 值。

最后，当节点的 \(low\) 值等于 \(dfn\) 值时，从该节点开始，一直出栈到当前节点，并将这些节点作为一个强连通分量。具体来说，如果出栈的节点是 \(u\)，则将 \(u\) 标记为当前强连通分量的编号，并将所有出栈的节点加入该强连通分量中。

以下是Tarjan算法的C++代码实现，用于寻找无向图中的强连通分量（SCC）：

C++
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

const int MAXN = 1e5 + 5;

vector<int> adj[MAXN]; // 邻接表存图
stack<int> stk; // Tarjan算法中的栈
bool in_stk[MAXN]; // 记录某个节点是否在栈中
int dfn[MAXN]; // 某个节点的访问时间戳
int low[MAXN]; // 某个节点能到达的最小时间戳
int scc_id[MAXN]; // 某个节点所属的强连通分量的编号
int scc_cnt = 0; // 当前已找到的强连通分量个数
int timestamp = 0; // 时间戳

void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;
    stk.push(u);
    in_stk[u] = true;
    for (int v : adj[u]) {
        if (!dfn[v]) { // 如果节点v还没被访问过
            tarjan(v); // 继续往下递归
            low[u] = min(low[u], low[v]);
        } else if (in_stk[v]) { // 如果节点v已经被访问过且在栈中
            low[u] = min(low[u], dfn[v]);
        }
    }
    // 如果节点u是某个强连通分量的根节点
    if (dfn[u] == low[u]) {
        int v;
        ++scc_cnt;
        do {
            v = stk.top();
            stk.pop();
            in_stk[v] = false;
            scc_id[v] = scc_cnt;
        } while (v != u);
    }
}

int main() {
    // 读入无向图
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 从任意一个未被访问过的节点出发
    for (int i = 1; i <= n; ++i) {
        if (!dfn[i]) {
            tarjan(i);
        }
    }

    // 输出每个节点所属的强连通分量的编号
    for (int i = 1; i <= n; ++i) {
        cout << "Node " << i << " belongs to SCC " << scc_id[i] << endl;
    }

    return 0;
}

以上代码实现了Tarjan算法，可以在O(n + m)的时间内找到无向图中的所有强连通分量。

2.Kosaraju算法

Kosaraju 算法包括两个步骤：首先，对原图进行一次深度优先搜索，得到每个节点的出度为0的反图；然后，对反图进行深度优先搜索，得到每个节点的强连通分量。

具体实现中，首先对原图进行深度优先搜索，得到所有节点的完成时间。然后构造反图，对反图进行深度优先搜索，根据节点的完成时间顺序，从后往前搜索得到强连通分量。

下面是Kosaraju算法的C++实现代码，主要包括两个函数，dfs和kosaraju函数。其中dfs函数是进行深度优先遍历的函数，kosaraju函数则是Kosaraju算法的主函数，用于求解强联通分量。

C++
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

const int MAXN = 100005;

vector<int> graph[MAXN];
vector<int> reverse_graph[MAXN];
bool visited[MAXN];
stack<int> order;  // 用于存储dfs遍历的顺序
int scc[MAXN];     // 用于存储每个点所属的强联通分量编号
int scc_count = 0; // 记录强联通分量的数量

// 深度优先遍历函数
void dfs(int u) {
    visited[u] = true;
    for (int i = 0; i < graph[u].size(); i++) {
        int v = graph[u][i];
        if (!visited[v]) {
            dfs(v);
        }
    }
    order.push(u);
}

// Kosaraju算法函数，求解强联通分量
void kosaraju(int n) {
    // 第一遍dfs，将节点按遍历顺序入栈
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            dfs(i);
        }
    }

    // 初始化visited数组
    for (int i = 1; i <= n; i++) {
        visited[i] = false;
    }

    // 第二遍dfs，倒序从栈中取出节点进行遍历，得到强联通分量
    while (!order.empty()) {
        int u = order.top();
        order.pop();
        if (!visited[u]) {
            scc_count++;
            stack<int> component;
            component.push(u);
            visited[u] = true;
            while (!component.empty()) {
                int v = component.top();
                component.pop();
                scc[v] = scc_count;
                for (int i = 0; i < reverse_graph[v].size(); i++) {
                    int w = reverse_graph[v][i];
                    if (!visited[w]) {
                        component.push(w);
                        visited[w] = true;
                    }
                }
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    // 读入有向图
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        reverse_graph[v].push_back(u);
    }

    // 求解强联通分量
    kosaraju(n);

    // 输出每个点所属的强联通分量编号
    for (int i = 1; i <= n; i++) {
        cout << i << " " << scc[i] << endl;
    }

    return 0;
}

以上是Kosaraju算法的C++实现代码，使用时可以直接输入有向图的节点数和边数，然后逐条输入边的起点和终点。最后输出每个节点所属的强联通分量编号即可。

3.6.11 强连通分量的缩点算法

强连通分量的缩点算法（Tarjan算法的改进版）是一种常用的图算法，用于将有向图中的强连通分量缩成一个点，得到一个新的DAG。它的时间复杂度为 \(O(n+m)\)。下面是该算法的C++代码实现：

C++
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

const int MAXN = 1005;

int n, m, cnt, scc_cnt;
int head[MAXN], low[MAXN], dfn[MAXN], scc[MAXN], in_degree[MAXN];
bool vis[MAXN];
stack<int> st;

struct Edge {
    int v, next;
} edge[MAXN * MAXN];

void add_edge(int u, int v) {
    edge[cnt].v = v;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}

void tarjan(int u) {
    low[u] = dfn[u] = ++cnt;
    vis[u] = true;
    st.push(u);

    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].v;

        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (vis[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }

    if (dfn[u] == low[u]) {
        scc_cnt++;
        int v;

        do {
            v = st.top();
            st.pop();
            scc[v] = scc_cnt;
            vis[v] = false;
        } while (u != v);
    }
}

void solve() {
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            tarjan(i);
        }
    }

    for (int u = 1; u <= n; u++) {
        for (int i = head[u]; i != -1; i = edge[i].next) {
            int v = edge[i].v;

            if (scc[u] != scc[v]) {
                in_degree[scc[v]]++;
            }
        }
    }

    int ans = 0;

    for (int i = 1; i <= scc_cnt; i++) {
        if (!in_degree[i]) {
            ans++;
        }
    }

    cout << ans << endl;
}

int main() {
    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
    }

    solve();

    return 0;
}

这里使用了Tarjan算法求出强连通分量，然后遍历每个强连通分量的点，把指向其他强连通分量的边的入度加一。最后统计入度为0的强连通分量的数量即为缩点后的DAG中的起始节点数量。

3.6.12 求割点、割边算法

求割点、割边是图论中的一个重要问题，下面分别介绍两个算法。

1.求割点算法

求割点的算法一般采用深度优先搜索（DFS）实现。具体来说，对于无向图 \(G=(V,E)\)，定义 \(dfn[u]\) 为结点 \(u\) 第一次被访问到的时间，\(low[u]\) 表示 \(u\) 能够到达的结点在 DFS 树上的最小 \(dfn\) 值，\(fa[u]\) 表示 \(u\) 在 DFS 树上的父结点，\(cnt\) 表示 DFS 树上的结点数量。

求割点的步骤如下：

初始化 \(dfn\) 和 \(low\) 数组为 \(0\)，令 \(cnt=0\)。
从一个未被访问的结点 \(u\) 开始进行 DFS，每访问到一个新结点 \(v\)，令 \(dfn[v]=low[v]=++cnt\)。
对于结点 \(v\) 的每个子结点 \(w\)，如果 \(w\) 没有被访问过，就将其作为起点进行 DFS，并更新 \(low[v]=\min{low[v], low[w]}\)。
如果 \(w\) 已经被访问过，且 \(w\) 不是 \(v\) 的父结点，那么更新 \(low[v]=\min{low[v], dfn[w]}\)。
如果 \(v\) 是根结点，判断其是否有两个或以上的子结点，如果有，则 \(v\) 是割点。否则如果结点 \(w\) 满足 \(dfn[w]>dfn[v]\) 且 \(low[w]\ge dfn[v]\)，则 \(v\) 是割点。
重复步骤 2 到 5，直到所有结点都被访问过。

下面是求割点的 C++ 代码实现：

C++
const int MAXN = 10005;

vector<int> G[MAXN];
int dfn[MAXN], low[MAXN], fa[MAXN], cnt;

void tarjan(int u) {
    dfn[u] = low[u] = ++cnt;
    int child = 0;
    for (int i = 0; i < G[u].size(); ++i) {
        int v = G[u][i];
        if (!dfn[v]) {
            ++child;
            fa[v] = u;
            tarjan(v);
            low[u] = min(low[u], low[v]);
            if (fa[u] == 0 && child >= 2) {
                printf("%d is cut vertex\n", u);
            } else if (fa[u] != 0 && low[v] >= dfn[u]) {
                printf("%d is cut vertex\n", u);
            }
        } else if (v != fa[u]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

2.求割边算法

求割边算法，也称为桥（Bridge）问题，是指在无向连通图中，删除一条边之后，该图不再连通，则称这条边为割边或桥。

求解割边问题的基本思路是利用 DFS 遍历整张图，以边为搜索基础，每次搜到一条边时，判断该边连接的两个节点是否在同一 DFS 树中。如果是，判断是否为树边；如果不是，则说明找到了一条连接不同 DFS 树的边，即为割边。

具体实现时，可以利用 DFS 过程中记录每个节点的时间戳（即第一次访问该节点的时间），以及每个节点能够回溯到的最早的时间戳（即它所能够到达的节点中最小的时间戳），这样就可以判断每条边是否为割边。

下面是求解割边的 C++ 代码实现，其中使用了 DFS 和时间戳的思想：

C++
#include <iostream>
#include <vector>

using namespace std;

const int N = 100010;

vector<int> g[N];
int dfn[N], low[N], timestamp;

void dfs(int u, int p)
{
    dfn[u] = low[u] = ++timestamp;
    for (auto v : g[u]) {
        if (!dfn[v]) {
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) cout << u << " - " << v << " is a bridge\n";
        } else if (v != p) {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

int main()
{
    int n, m;
    cin >> n >> m;

    while (m--) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) dfs(i, -1);
    }

    return 0;
}

上述代码中，dfn[u] 表示节点 u 的时间戳，low[u] 表示节点 u 能够回溯到的最早的时间戳。在 DFS 遍历过程中，对于每个节点 u，首先将其时间戳和回溯时间戳都设为当前时间戳，并遍历 u 的所有邻居节点 v。如果节点 v 没有被访问过，就递归访问它，并更新 u 的回溯时间戳。如果回溯时间戳 low[v] 大于节点 u 的时间戳 dfn[u]，则说明边 (u, v) 是一条割边。如果节点 v 已经被访问过，并且它不是节点 u 的父节点，那么就更新 u 的回溯时间戳。

3.7 动态规划

3.7.1 树型动态规划

树型动态规划(Tree DP)是一种基于树型数据结构的动态规划算法，主要用于解决一些涉及树型结构的问题，如树的重心、树的直径、树的最长链、树的最大匹配等问题。该算法的核心思想是以节点为中心，递归计算节点的子树信息，进而推导出整棵树的信息。

常见的树型DP问题有：

求树的重心
求树的直径
求树的最长链
求树的最大匹配

等等。

树型DP算法的核心思想是：对于树中的每个节点，将其当作一个状态，通过转移方程计算出该节点对应的状态值，并将该节点的状态值传递给其父节点，最终得到整棵树的状态值。在计算节点的状态值时，通常需要考虑该节点的子节点的状态值以及该节点与其父节点之间的关系。

下面是一个树的重心的例子，介绍一下树型DP的具体实现过程。

假设有一棵树，节点编号为 1~n，要求求出该树的重心，即将树划分为多个连通块，使得每个连通块中的最大子树大小最小。

首先，考虑使用深度优先搜索（DFS）遍历树，计算每个节点的子树大小，并求出以每个节点为根的子树中，大小最大的子树的大小，即最大子树大小。

定义 \(dp[i]\) 表示以节点 \(i\) 为根的子树中，大小最大的子树大小，\(size[i]\) 表示以节点 \(i\) 为根的子树大小，\(f[i]\) 表示以节点 \(i\) 为根的子树中，大小最大的子树的大小。

则可以得到转移方程：

\[ dp[i] = size[i] + \sum_{j \in son(i)} dp[j] \]

其中 \(son(i)\) 表示节点 \(i\) 的子节点集合，即 \(i\) 的所有儿子节点。

得到 \(dp[i]\) 后，可以遍历每个节点 \(i\)，计算删掉该节点后，子树大小最大的子树的大小，即 \(f[i]\)，具体地，对于每个节点 \(i\)，计算

\[ f[i] = max({dp[j], size[1]-size[i]}), j \in son(i) \]

其中 \(size[1]\) 表示整棵树的大小，即根节点的子树大小。最终，树的重心为满足 \(f[i]\) 最小的节点 \(i\)。

1.求树的重心

树的重心是指树中的一个节点，如果将该节点删除后，剩余各个连通块中节点数的最大值最小，那么这个节点就是树的重心。

下面是树的重心的C++代码实现：

C++
#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 100010;

vector<int> g[MAXN];
int n, sz[MAXN], max_subtree[MAXN], ans = MAXN;

void dfs(int u, int fa) {
    sz[u] = 1;
    max_subtree[u] = 0;
    for (auto v : g[u]) {
        if (v != fa) {
            dfs(v, u);
            sz[u] += sz[v];
            max_subtree[u] = max(max_subtree[u], sz[v]);
        }
    }
    max_subtree[u] = max(max_subtree[u], n - sz[u]);
    ans = min(ans, max_subtree[u]);
}

int main() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1, 0);

    cout << "The centroid of the tree is/are: ";
    for (int i = 1; i <= n; i++) {
        if (max_subtree[i] == ans) {
            cout << i << " ";
        }
    }

    return 0;
}

该代码的时间复杂度为\(O(n)\)，其中\(n\)是树的节点数。

2.求树的直径

求树的直径的算法有两种，一种是基于树的深度优先搜索（DFS）的算法，另一种是基于树的广度优先搜索（BFS）的算法。

基于DFS的算法思路如下：

任选树上一个节点u，以它为起点进行一次深度优先遍历，找到离u最远的节点v。
以节点v为起点进行一次深度优先遍历，找到离v最远的节点w，那么v到w的距离就是树的直径。

基于BFS的算法思路如下：

任选树上一个节点u，以它为起点进行一次广度优先遍历，找到离u最远的节点v。
以节点v为起点进行一次广度优先遍历，找到离v最远的节点w，那么v到w的距离就是树的直径。

以下是基于 DFS 的求树直径的 C++ 代码实现：

C++
#include <iostream>
#include <vector>

using namespace std;

const int N = 100010;

vector<int> g[N];
int d[N], f[N];

void dfs(int u, int fa)
{
    for (auto v : g[u])
    {
        if (v == fa) continue;
        dfs(v, u);
        if (d[v] + 1 > d[u]) d[u] = d[v] + 1, f[u] = v;
    }
}

int main()
{
    int n;
    cin >> n;

    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    dfs(1, -1);

    int t = f[1];
    d[1] = 0;
    dfs(t, -1);

    cout << d[t] << endl;

    return 0;
}

这里使用了一个 dfs 函数，它接受两个参数：当前遍历到的节点 u 和它的父节点 fa。在函数内部，我们遍历 u 的所有子节点，对每个子节点 v 递归调用 dfs 函数。同时，我们还要记录 u 到它的某个子孙节点的最大距离 d[u] 和这个子孙节点 f[u]。递归回溯时，我们更新 d[u] 和 f[u]。

具体地，在遍历子节点 v 时，我们首先排除父节点 fa，然后递归调用 dfs 函数，得到 v 的 d[v] 和 f[v]。如果 d[v] + 1 大于 d[u]，我们就更新 d[u] 和 f[u]。最后，我们通过 f[1] 找到树的直径的一端 t，再从 t 开始进行一次 dfs，得到树的直径长度 d[t]。

时间复杂度为 O(n)。

以下是基于 BFS 的求树直径的 C++ 代码实现：

C++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 10005; // 最大结点数

vector<int> tree[MAXN]; // 存储树的邻接表表示
bool visited[MAXN]; // 标记结点是否被访问
int dis[MAXN]; // 存储每个结点到起点的距离

// 从指定起点开始进行 BFS，求出离起点最远的结点和距离
void bfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < tree[u].size(); i++) {
            int v = tree[u][i];
            if (!visited[v]) {
                visited[v] = true;
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
    }
}

int main() {
    int n;
    cin >> n;

    // 读入树的边
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    // 从结点 1 开始进行 BFS，求出离结点 1 最远的结点和距离
    bfs(1);
    int max_dis = -1, max_node = 0;
    for (int i = 1; i <= n; i++) {
        if (dis[i] > max_dis) {
            max_dis = dis[i];
            max_node = i;
        }
        visited[i] = false;
        dis[i] = 0;
    }

    // 从离结点 1 最远的结点开始进行 BFS，求出树的直径
    bfs(max_node);
    max_dis = -1;
    for (int i = 1; i <= n; i++) {
        if (dis[i] > max_dis) {
            max_dis = dis[i];
        }
    }

    cout << max_dis << endl;
    return 0;
}

该算法先从任意结点开始进行 BFS，求出离该结点最远的结点和距离，然后从该离开始结点再次进行 BFS，求出树的直径长度。

该算法的时间复杂度为 \(O(n)\)，其中 \(n\) 是树的结点数。

3.求树的最长链

求树的最长链（又称树的直径）是指在一棵无根树中，找到最长的一条简单路径，该路径可以看作是树中两个节点之间的距离。

求解树的最长链可以通过两次遍历树来实现：

以任意一个节点为起点，通过 DFS 或 BFS 遍历整棵树，找到离该节点最远的节点 u。
以 u 为起点，再次通过 DFS 或 BFS 遍历整棵树，找到离 u 最远的节点 v，即树的直径就是 u 到 v 的路径。

以下是基于 DFS 的求树的最长链的 C++ 代码实现：

C++
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 1e5 + 5;

vector<int> g[MAXN]; // 存储树
int ans = 0; // 最长链的长度
int farthest_node = 0; // 最远的节点

void dfs(int u, int fa, int dep) {
    if (dep > ans) { // 更新最长链的长度和最远的节点
        ans = dep;
        farthest_node = u;
    }
    for (int v : g[u]) {
        if (v == fa) continue;
        dfs(v, u, dep + 1);
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1, 0, 0); // 从任意节点开始搜索，更新最长链的长度和最远的节点

    ans = 0;
    dfs(farthest_node, 0, 0); // 从最远的节点开始搜索，得到最长链的长度

    cout << ans << endl;

    return 0;
}

以上代码中，使用 vector<int> g[MAXN] 存储树的结构，使用 dfs 函数进行深度优先搜索。在搜索的过程中，记录当前节点到根节点的深度 dep，若当前深度比最长链的长度 ans 还要长，就更新 ans 和最远的节点 farthest_node。最后，从 farthest_node 开始再进行一次深度优先搜索，得到的深度即为树的最长链的长度。

下面是基于 BFS 的求树最长链的 C++ 代码实现：

C++
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
vector<int> g[N];   // 存储树的邻接表表示
bool vis[N];        // 标记节点是否已经被访问
int dist[N];        // 存储每个节点到树的根节点的距离
int start, _max;    // 记录最长链的起点和终点

void bfs(int u) {
    queue<int> q;
    q.push(u);
    dist[u] = 0;
    vis[u] = true;
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        for (auto v : g[t]) {
            if (!vis[v]) {
                dist[v] = dist[t] + 1;
                vis[v] = true;
                q.push(v);
            }
        }
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    bfs(1); // 随便选取一个点为根节点，计算每个节点到根节点的距离
    _max = -1;
    for (int i = 1; i <= n; i++) {
        if (dist[i] > _max) {
            _max = dist[i];
            start = i;
        }
    }
    fill_n(vis, n + 1, false);
    fill_n(dist, n + 1, 0);
    bfs(start); // 从最长链的起点开始重新计算每个节点到根节点的距离
    _max = -1;
    for (int i = 1; i <= n; i++) {
        _max = max(_max, dist[i]);
    }
    cout << _max << endl;
    return 0;
}

该算法的思路是首先任选一点为根节点，利用 BFS 计算每个节点到根节点的距离，然后找到距离最远的节点作为最长链的一个端点。接着从最长链的起点重新开始 BFS，计算每个节点到根节点的距离，最终距离的最大值即为最长链的长度。

4.求树的最大匹配

求树的最大匹配可以使用树的匹配理论来解决。树的匹配理论主要有两个定理：一个是匹配的大小不会超过树的大小的一半，另一个是如果树上存在完美匹配，则该树的大小必须为偶数。因此，可以使用递归方法求解树的最大匹配。

具体来说，可以使用贪心的策略：从根节点开始，按深度优先搜索的顺序依次处理每个节点，对于每个节点，先递归处理它的所有子节点，然后再对该节点进行匹配。

对于每个节点的匹配，可以分为两种情况：

匹配该节点和它的子节点的最大匹配：如果该节点没有子节点，则匹配为空；否则，将该节点的所有子节点两两匹配，得到子节点的最大匹配大小，然后将该节点与子节点的匹配数量相加，得到该节点的最大匹配大小。
不匹配该节点和它的子节点的最大匹配：将该节点不匹配，并将该节点的子节点递归匹配。

递归到叶子节点时，返回匹配大小为0的空匹配。最终，根节点的最大匹配大小即为所求。

以下是基于 DFS 求树的最大匹配的 C++ 代码实现：

C++
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int MAXN = 1005;
vector<int> G[MAXN];
bool used[MAXN];
int match[MAXN];

bool dfs(int v) {
    used[v] = true;
    for (int i = 0; i < G[v].size(); i++) {
        int u = G[v][i], w = match[u];
        if (w < 0 || !used[w] && dfs(w)) {
            match[v] = u;
            match[u] = v;
            return true;
        }
    }
    return false;
}

int bipartite_matching(int n) {
    int res = 0;
    memset(match, -1, sizeof(match));
    for (int v = 0; v < n; v++) {
        if (match[v] < 0) {
            memset(used, 0, sizeof(used));
            if (dfs(v)) res++;
        }
    }
    return res;
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v + n);
        G[v + n].push_back(u);
    }
    int ans = bipartite_matching(n + m);
    cout << ans << endl;
    return 0;
}

其中，G 为图的邻接表表示，match 记录每个点匹配的点的编号，如果某个点还没有匹配，则其对应的 match 值为 -1。函数 dfs 用于递归搜索增广路，并返回是否找到了增广路，函数 bipartite_matching 用于计算最大匹配数。

在 main 函数中，先读入输入，然后将二分图转化为单向边的有向图，调用 bipartite_matching 函数求解最大匹配数，最后输出结果。

3.7.2 状态压缩动态规划

状态压缩动态规划是一类常用于处理状态空间非常大的问题的动态规划算法。通常情况下，状态空间是指由一系列状态构成的集合，而状态压缩动态规划则是将每个状态用一个二进制数表示，从而将一个巨大的状态空间压缩成了一个较小的状态空间。在实现过程中，需要使用位运算技巧来处理状态的转移和计算。状态压缩动态规划广泛应用于图论、计算几何等领域，比如旅行商问题、背包问题等。

一般来说，状态压缩动态规划的基本流程如下：

设计状态：将每个状态用一个二进制数表示，其中二进制数的每一位表示一个状态。
初始化：初始化第一个状态，通常为0或1。
状态转移：用位运算技巧进行状态的转移，并更新每个状态的最优解。
输出答案：输出最终状态的最优解。

下面是一个状态压缩动态规划的例子，以0-1背包问题为例。

问题描述：

有一个容量为C的背包和N个物品，每个物品有一个重量w[i]和一个价值v[i]。现在需要选择若干个物品放入背包中，使得它们的重量不超过背包容量，同时价值之和最大。请设计一个算法，求出最大价值。

具体代码如下：

C++
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 20;
int n, m;
int w[N], v[N];
int f[1 << N];

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> w[i] >> v[i];

    memset(f, 0xcf, sizeof f);
    f[0] = 0;

    for (int i = 0; i < n; i ++ )
        for (int j = (1 << m) - 1; j >= 0; j -- )
            for (int k = j; k; k = (k - 1) & j)
                if (w[i] <= k)
                    f[j] = max(f[j], f[j - k] + v[i]);

    cout << f[(1 << m) - 1] << endl;

    return 0;
}

其中，\(f[i]\)表示当前状态为\(i\)时，所能得到的最大价值。由于0-1背包问题的状态只与前一个状态有关，因此可以使用滚动数组来优化空间。对于状态\(i\)，枚举它的子集\(k\)，然后更新状态\(f[i]\)即可。需要注意的是，在更新\(f[i]\)之前，要先判断当前物品是否能放入到背包中，即\(w[j]\leq k\)。同时，由于背包容量比较小，因此可以使用位运算来加速枚举子集的过程。

3.7.3 动态规划的常用优化

动态规划是解决复杂问题的一种有效算法，但是在实际应用中，有些问题的状态转移方程可能比较复杂，导致算法的时间复杂度较高。因此，为了优化动态规划算法，常常采用以下几种方法：

状态压缩：对于状态空间比较大的问题，可以使用状态压缩技术来降低状态空间的维度，从而减少计算量。例如，在0-1背包问题中，可以使用位运算来表示状态，从而将二维数组优化为一维数组，减少空间复杂度。
记忆化搜索：在递归调用时，如果存在大量的重复计算，可以将计算结果存储下来，以便下一次直接查询结果，从而减少重复计算。例如，在斐波那契数列问题中，可以使用记忆化搜索来减少递归调用的次数。
贪心策略：在某些情况下，可以使用贪心策略来简化问题，从而减少计算量。例如，在活动选择问题中，可以按照结束时间对活动进行排序，然后依次选择结束时间最早的活动。
优化状态转移方程：对于状态转移方程比较复杂的问题，可以通过优化方程的形式来降低时间复杂度。例如，在最长公共子序列问题中，可以使用滚动数组来优化状态转移方程，从而减少空间复杂度。
剪枝：对于一些无用的状态，可以提前进行剪枝，从而减少计算量。例如，在旅行商问题中，可以通过计算当前路径的长度是否已经大于已知的最短路径长度来进行剪枝，从而减少不必要的计算。
降维打击：在状态空间比较大的问题中，可以通过将状态空间分组，然后对每组状态进行计算，最后再将结果合并，从而减少计算量。例如，在数位DP问题中，可以将数位划分为高位和低位，分别进行计算，然后将结果合并。

这些方法不仅可以优化动态规划算法，还可以应用于其他算法的优化中。

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用