树是无环连通图
图分为两种，一种是有向图例如a -> b 另外一种是无向图，a-b。
有向图就是记录从a到b的路径，无向图就是从a 到b可以，b到a也行，所以在存储无向图的时候就是存两个有向图，分别是a -> b 和 b -> a。
存储有向图的方法有两个一个是邻接矩阵，就是开一个二维数组，表示从a 到 b的边，如果存在存1，不存在存0，如果有权重就存权重。这种适合存比较稠密的图，比较稀疏的适合用邻接表

另外一种方法是邻接表，就是每个点都开一个单链表，用h[]，表示表头，初始化的时候指向-1，数量级就是N(全部数据的个数)

memset(h, -1, sizeof h); //在头文件cstring中

之后每次存一个边，例如a - > b, 就在表头为a的单链表上从表头处插入b，单链表中存的值就是表头指向的那个点，其中每个单链表都是无序的，这个顺序也没有意义，因为当遍历的时候每次都将遍历到的e[]，值作为一个头节点去遍历，表示的是遍历到的这个点之后指向的其他点，所以单链表是不存路径的，只是存单向边。

插入表头的方法，定义一个idx，表示当前可以用的下标，e[], 表示值，ne[]，表示指向的值（即指向下一个数的指针），e[idx] = x, ne[idx] = h[表头]， h[当前的表头] = idx++. 其中e[], ne[] 数量级可以开两倍的N，防止越界

深度优先遍历（即深搜dfs）

因为一般的题目每个点只会遍历一次，所以要开一个布尔数组st[N], 来存放是否遍历过

void dfs(int u ) // u 表示开始的点
{
    st[u] = true ; // 标记u以及遍历过
    for (int i = h[u]; i != -1; i = ne[i]) // u开始所以作为头节点，ne和h都是表示的是指向下一个数的指针
    {
        j = e[i] // 将值赋给j，j表明下一个遍历到的点，然后判断是否遍历过，若没有则递归dfs
        if (!st[j]) dfs(j);
    }
    
}

例题：

树的重心

给定一颗树，树中包含 n个结点（编号 1∼n）和 n−1 条无向边。
请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。
重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。
输入格式
第一行包含整数 n，表示树的结点数。
接下来 n−1行，每行包含两个整数 a和 b，表示点 a和点 b之间存在一条边。
输出格式
输出一个整数 m，表示将重心删除后，剩余各个连通块中点数的最大值。
数据范围 1≤n≤1e5

输入样例：

9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6

输出样例：

4

思路：
利用dfs，每次都将遍历到的点，删除后，连通块的最大值求出，之后只要是将所有点代表的最大值的最小值求出就行。
如何求每个点删除之后的连通块的最大值，这里先是新建一个变量sum，表示的是这个点所连通的所有点的数量，一开始让 sum = 1, 表示只有一个点，之后让每次dfs完成之后返回一个sum，表示的是从某个点开始到所有可以遍历的点的数量，理论上，一开始是只有一条线，但是由于是有迭代，每个点的sum都加等于那个点之后每条线的点的数量，所以最后返回的sum就是那个点往下所连的点的数量（包括他本身，以及因为他不能向上回溯，只有下面的点回溯到他，所以sum是只包括了他本身，以及之后所连所有点的数量）。再新建一个变量res，这个变量要放在dfs函数中，表示的是每一个有一个单独的res（如果是放到外面，当迭代回溯的时候原来的那个res会变，而res不止比一次，而是有多少个子节点就比几次，所以在内存中这个正在遍历的点的res应该要被保留），当下一次dfs开始时 = 0初始化，表示的是这个点删除之后，最大的联通块所包含的点的数量，很显然，这个连通块分为两个部分，一个是这个点之后的连通块，以及这个点上面的节点所连接的连通块，之后的连通块其实就是dfs的返回值，所以用res = max{res, s},就是用当前的res和后面返回的s进行比较然后更新。
上面的连通块其实就是用全部个个数减去这个节点连接的后面的节点的个数（包括他本身，因为他被删除了），所以用n - sum ，之后就是更新res。完成之后res存的就是当前这个节点的最大连通块的值，之后更新答案只要是比原来的ans小就保存。ans = min(ans, res) // min和max在头文件algorithm中

重边 指的是有两个或多个重复的边，例如a -> b 有两个
自环 指的是一个元素的一条边指向自己，例如 a -> a
所有边的长度都是1，指的就是可以用宽搜来求最短路，否则可能要用动态规划（DP）

广度优先遍历（bfs）

和之前的bfs思路一致，用到的数据结构是队列，只不过是在图中进行的。
先是用邻接表来存图，

int h[N], e[N], ne[N], idx;
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

bfs中队列还是用数组来模拟

int d[N]; //表示的是起始点到某个点的距离
bool st[N]; //第一次遍历为最小值，所有要加一个判断
int q[N]; //模拟的队列

int bfs()
{
    int hh = 0, tt = -1;
    q[++tt] = 1; //看题目要求加入起始点
    st[1] = true;
    memset(d, -1, sizeof d) //初始化d,表示还没开始计算距离
    d[1] = 0; //初始化
    while(hh <= tt)
    {
        int t = q[hh++]; //取队头
        // 这边如果是矩阵的话就是要遍历四个点，但这个用的是邻接表，所以也要用邻接表的遍历方法来遍历,判断条件一样也是在遍历之后，如果符合条件就放到队列中，之后就是循环继续从上一个最先放进去的点开始，表示进行到下一层
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(!st[j])
            {
                st[j] = true;
                d[j] = d[t] + 1;
                q[++tt] = j;
            }
        }
    }
    return d[n]
}

例题：

图中点的层次

给定一个 n个点 m条边的有向图，图中可能存在重边和自环。
所有边的长度都是 1，点的编号为 1∼n。
请你求出 1号点到 n号点的最短距离，如果从 1号点无法走到 n号点，输出 −1。
输入格式
第一行包含两个整数 n和 m。
接下来 m行，每行包含两个整数 a和 b，表示存在一条从 a走到 b的长度为 1 的边。
输出格式
输出一个整数，表示 1号点到 n号点的最短距离。
数据范围 1≤n,m≤1e5
输入样例：

4 5
1 2
2 3
3 4
1 3
1 4

输出样例：

1

思路：求最短距离，然后所有边的长度为1，所以可以用广度优先遍历bfs。在输入的时候要记得，读入的是边，不是点。

在读双边的时候数据大小应该差不多是4N,因为单边是2N,双边差不多有两倍所以占4N.

拓扑序列，针对有向图，定义是每一条边x, y ，x都在y前面，就是说对于一个拓扑序列来讲，每一条边都是从前指向后的 ，例如1 -> 2, 1 -> 3, 2 -> 3 ，则说1 -> 2 -> 3 是一个拓扑序列
可以证明一个有向无环图一定存在一个拓扑序列（拓扑序一定是全部的点参与，只是排列的顺序或许会不同），所以有向无环图又被称为拓扑图

度数 ， 一个数的入度指的是有几条边指向自己，出度指的是有几条指向其他点的边

一个有向无环图一定至少存在一个入度为0的点，一个有向无环图的拓扑序不一定是唯一的，拓扑序不一定就是值是从小到大排序，也可能是乱序，关键是从第一个头节点开始都是指向后，中间没有一个节点指向前，例如： 1 -> 2 ,1 - > 3 在这个图中 1 -> 2 -> 3 是拓扑序 1 - > 3 - > 2 也是拓扑序，他和上面那个例子的区别是上面有 2 -> 3，根据拓扑排序的定义，2因为指向3，所以他必须排在3之前，所以，只能是 1， 2， 3 ，而在这个例子中 2没有指向3，所以只要1同时满足在2和3之前就是拓扑序

求拓扑序的思路：
新建一个数组d[],在读入的时候，对于指向的边例如b，让其d[b] ++,之后bfs中先是把入度为0的边加入到队列中，然后就是和正常的dfs差不多了，遍历拓展的节点，然后让其入度减1，之后判断入度是否为0如果为0则加入到队列中，之后在这个头节点的子节点都拓展之后，就取下一个头节点（上一个被弹出）。之后在循环跑完之后判断tt == n - 1，tt初始化是为 - 1，一共n个点，如果n个点都加入，则说明没有环，（环形图没有突破口使其入度减一，环上的所有点最后的结果一定是形成孤立的环），所以输出拓扑序，否则输出-1，
输出拓扑序的方式，因为队列是只有在入度为0的时候才会加入，所以队列中从前往后的顺序一定是一个拓扑序，假如某个点在入度为0时被加入队列，则他有可能会有出度，然后指向后方，所以入队顺序就是一个拓扑序，因为是用数组来模拟，所以在输出的时候可以从0开始遍历到n - 1.

例题：

拓扑排序

给定一个 n个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。
若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x 在 A 中都出现在 y之前，则称 A是该图的一个拓扑序列。
输入格式
第一行包含两个整数 n和 m。
接下来 m 行，每行包含两个整数 x 和 y，表示存在一条从点 x 到点 y 的有向边 (x,y)。
输出格式
共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。
否则输出 −1。
数据范围 1≤n,m≤1e5
输入样例：

3 3
1 2
2 3
1 3

输出样例：

1 2 3

我发现我现在发文章越来越依靠ai了，这导致我自己的思想在文章当中的占比很少，这对我的成长也不是很好，所以我以后的文章会尽量的少使用ai，除非就是那种排版，以及图片之类的，总的内容还是要自己去输出。

bfs就是宽度优先搜索，用到队列来保持一个先入先出的结构，队列开的长度应该是边长的平方表示的是全部点的个数，存的是位置，所以可以是用pair<int, int> 来存，

其中用组数模拟队列的方法就是定义两个指针，hh、tt ,hh = 0, tt = -1,存入元素时，++tt ,表示向后退一格，弹出队头时hh++，表示同时退后一个元素，同时原来的索引就不用管了，为的是节约时间，但是可以浪费一点内存

这样是为了，在后面加入的元素时可以优先把前面先加入的元素进行宽搜，为了标记位置是否已经来过，需要一个bool二维数组来储存，同时用一个int类型的二维数组来储存每一个点是第几个经过的点，当这个点是终点时，也就是成了从初始点到终点的距离，所以显然，初始点的值为0，表示还没有开始走，也就是头节点。因为是对没有个节点进行标记，所以第一次到达终点时，就是最短的路径，因为有队列在保持后面相同同一层的点，假如某一点要再走两格才可以到达，但是第一个点，就是我们拿出来的头节点可以在下一次的遍历中就到达终点，并给终点上了个标记，所以很显然就是，这个第一次经过的终点距离是最短的。

用来模拟向四个方向走可以新建两个数组，表示偏移量，例如dx = {-1，0，1，0}，dy = {0，1，0，-1}，分别表示（-1，0）、（0，1）、（1，0）、（0，-1），即向上，向右，向下，向左
之后只要for循环4次，表示四个坐标，同时加上限制条件（边界或其他），如果满足条件，则那个点的路径数为前面的路径数 + 1，然后将其放到对列中

所以为了保持这个最短的性质，每次再加入队列之前先进行判断是不是已经经过了，如果已经经过了就没有必要再经过一遍，所以就不用加入队列，从而有了一个循环结束的标志，就是当队列中没有元素时，即没有新的元素加入，然后老元素也已经全部走完时，就是表示表格中的所有元素都被走过了，此时输出终点的路径数就是最短路径数

关于输入以及边界判断，如果主要是看题目，来看是从1开始还是从0开始。以及对应的终点的坐标是否要减1

关于如何输出路径，可以再新建一个类型为pair<int, int> 类型的二维数组pre，来存放每个点之前的坐标，然后在输出的时候，可以用一个while循环来表示，while(x || y) 表示当x或y有一个不为0时，循环就继续，即如果x和y都为0时循环就结束，在逻辑上就是起始点没有前一个点，然后在每次进行扩张的时候都将当前点的上一个存入pre。

思考：这个时候如果已经知道了终点的坐标，而且只有一个询问，是不是可以在当循环遍历到终点时就return，但是如果是有多组询问，或许应该就是要让他bfs跑完，这样的话每次查询的时间复杂度就是O(1)的了。

在算法竞赛中，堆常被用来处理需要动态维护最小值或最大值的操作。本文介绍一种基于最小堆的数据结构，支持插入、删除、修改和查询最小值的操作，并且针对每个插入操作进行编号，以便实现按插入顺序删除和修改的功能。

题目描述

我们需要维护一个集合，初始时集合为空，支持如下几种操作：

• I x，插入一个数 x；
• PM，输出当前集合中的最小值；
• DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；
• D k，删除第 k 个插入的数；
• C k x，修改第 k 个插入的数，将其变为 x。

要求进行 N 次操作，并对于所有 PM 操作，输出当前集合的最小值。

输入格式

• 第一行包含整数 N；
• 接下来 N 行，每行包含一个操作指令，操作指令为 I x，PM，DM，D k 或 C k x 中的一种。

输出格式

对于每个 PM 操作，输出当前集合的最小值，每个结果占一行。

数据范围

• 1 ≤ N ≤ 10^5
• -10^9 ≤ x ≤ 10^9
• 数据保证合法。

输入样例：

8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM

输出样例：

-10
6

思路分析

为了在 O(log n) 时间内实现插入、删除和修改操作，同时支持按插入顺序的删除和修改，我们需要用到最小堆，并且引入两个额外的数组来维护插入顺序与堆中元素位置的映射关系。

核心数据结构

• h[]: 最小堆，存储实际的堆元素；
• ph[]: 插入元素编号到堆位置的映射，即第 k 个插入的元素当前在堆中的哪个位置；
• hp[]: 堆中元素的下标对应的插入编号，表示堆中第 i 个位置存储的是第 k 个插入的元素。

这两个数组互为反函数，即 ph[hp[i]] = i，hp[ph[k]] = k。

操作实现

1. 插入操作 I x：

   • 将新元素插入堆，并更新插入编号和堆中的位置。
   • 调用 up() 函数对堆进行上浮操作。

2. 输出最小值 PM：

   • 直接输出堆顶元素，即 h[1]。

3. 删除最小值 DM：

   • 将堆顶元素与堆末尾元素交换，然后删除堆末尾元素。
   • 调用 down() 函数对堆顶进行下沉操作。

4. 删除第 k 个插入的数 D k：

   • 找到第 k 个插入的元素在堆中的位置，进行删除操作。
   • 调用 down() 和 up() 函数对该位置进行调整。

5. 修改第 k 个插入的数 C k x：

   • 修改第 k 个插入的元素的值，并进行上下调整，保持堆的性质。

代码实现

#include <iostream>

using namespace std;

const int N = 1e6 + 10;
int h[N], s = 0, hp[N], ph[N]; // ph[]是对应编号元素的下标，hp[]是元素的插入编号，h[]是堆

void heap_swap(int x, int y)
{
    swap(ph[hp[x]], ph[hp[y]]);
    swap(hp[x], hp[y]);
    swap(h[x], h[y]);
}

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

void up(int x)
{
    while (x / 2 && h[x / 2] > h[x])
    {
        heap_swap(x / 2, x);
        x /= 2;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k, x, m = 0; // m 表示第几个插入
    string op;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> op;
        if (op == "I")
        {
            cin >> x;
            h[++s] = x;
            hp[s] = ++m;
            ph[m] = s; 
            up(s);
        }
        else if (op == "PM")
        {
            cout << h[1] << '
';
        }
        else if (op == "DM")
        {
            h[1] = h[s--];
            down(1);
        }
        else if (op == "D")
        {
            cin >> k;
            heap_swap(ph[k], s--);
            down(ph[k]), up(ph[k]);
        }
        else if (op == "C")
        {
            cin >> k >> x;
            h[ph[k]] = x;
            down(ph[k]), up(ph[k]);
        }
    }
    return 0;
}

关键点说明

• heap_swap()：用于交换两个堆元素的位置，同时维护 ph[] 和 hp[] 的映射关系。
• down()：下沉操作，确保最小堆性质。若子节点比当前节点小，则将当前节点下沉。
• up()：上浮操作，确保最小堆性质。若父节点比当前节点大，则将当前节点上浮。
• ph[] 和 hp[] 的作用：这两个数组使得我们可以快速定位并删除或修改任意编号的元素，而无需遍历整个堆。

总结

通过最小堆结合 ph[] 和 hp[] 两个数组，我们能够高效地完成插入、删除、修改和查询最小值的操作。对于每个操作，插入、删除和修改的时间复杂度都是 O(log n)，而查询最小值的操作则为 O(1)。

这类问题广泛应用于需要动态维护有序集合的场景，比如优先队列、任务调度等。

在这篇文章中，我们将深入探讨两个常见的基础算法概念：递归 和 并查集。这两者在计算机算法中非常重要，理解它们的核心思想和应用场景将极大地帮助你解决许多常见的问题。

递归的核心思想

什么是递归？

递归是一种算法思想，它通过函数调用自身来实现重复操作。每次递归调用时，问题的规模都会逐步减小，直到满足特定的条件（基准条件，base case）来结束递归。

递归与循环的关系

很多人会将递归与 while 或 for 循环混淆，因为它们都用于实现某种形式的重复操作。实际上，递归可以看作是通过函数调用实现的循环结构。

递归通常使用 if 语句来检查递归的终止条件，而 while 则是基于显式的条件判断持续运行。递归与循环的本质区别在于，递归是通过函数的调用栈实现的，而循环是显式的控制流程。

递归的例子：斐波那契数列

int fibonacci(int n) {
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}

在这个例子中，递归通过 if 语句检查基准条件（n == 0 和 n == 1），并在这些条件满足时返回结果。这避免了无限递归的发生。

递归的注意点

递归虽然直观，但如果不注意基准条件或者优化，可能会导致性能问题或栈溢出。常见的优化技巧包括尾递归和动态规划。

并查集简介

什么是并查集？

并查集是一种数据结构，主要用于处理动态连通性问题。它能够高效地管理并查找多个不相交集合，支持合并（union） 和 查找（find） 操作。

在并查集中，每个元素最初都是一个独立的集合，其集合的代表是元素的祖先节点（根节点）。通过两个优化手段——路径压缩 和 按秩合并，并查集能够以接近常数时间（几乎是 O(1)）的复杂度执行合并和查找操作。

并查集的基本操作

1. 查找（Find）：
   查找元素的祖先节点（根节点），根节点是集合的唯一标识符。
2. 合并（Union）：
   将两个集合合并，实际上是将一个集合的根节点连接到另一个集合的根节点上。

并查集的实现

并查集的实现非常简洁。每个元素的根节点作为其集合的标识。当需要合并两个集合时，首先找到它们的根节点，然后根据根节点是否相同来决定是否需要合并。

并查集的代码实现

class UnionFind {
public:
    UnionFind(int n) : parent(n), rank(n, 1) {
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    // 查找操作（带路径压缩）
    int find(int p) {
        if (parent[p] != p) {
            parent[p] = find(parent[p]);  // 路径压缩
        }
        return parent[p];
    }

    // 合并操作（按秩合并）
    void unionSets(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);

        if (rootP != rootQ) {
            if (rank[rootP] > rank[rootQ]) {
                parent[rootQ] = rootP;
            } else if (rank[rootP] < rank[rootQ]) {
                parent[rootP] = rootQ;
            } else {
                parent[rootQ] = rootP;
                ++rank[rootP];
            }
        }
    }

private:
    std::vector<int> parent;
    std::vector<int> rank;
};

在这个实现中，我们使用了路径压缩（find 函数中的递归调用）和按秩合并（unionSets 函数中的秩判断），这确保了查找和合并操作都能高效地执行。

并查集的应用场景

并查集广泛应用于解决以下问题：

• 组团问题：判断两个元素是否属于同一组。
• 连通性问题：在图论中判断节点是否连通。
• 动态连通性问题：如社交网络中的好友关系。

总结

• 递归 是通过函数调用自身并基于 if 语句来实现重复操作的算法，适用于问题规模可以递归分解的场景。
• 并查集 是一种高效的数据结构，主要用于处理动态连通性问题，通过根节点代表集合，并支持合并和查找操作。

通过掌握递归与并查集的基本原理和实现方式，你将能够解决许多常见的算法问题。