树和图的存储以及dfs和bfs的应用

树是无环连通图
图分为两种，一种是有向图例如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