搜索与图论

                       数据结构    空间
    
    (俗称暴搜) 即某一道题目的所有方案全部遍历一遍(比较方便)
1.深度优先搜索 DFS      stack       O(n)        不具有最短路性质
    重点: 到底是用什么样的顺序来遍历这个方案
    两个重要概念：
    1) 回溯
    2) 剪枝
    
    凡是算法思路比较奇怪的 一般都用DFS来做 或者是对空间要求比较高的
2.宽度优先搜索 BFS      queue       O(2^n)      最短路
                所以凡是最小步数 最短距离 最少操作几次 基本都是BFS
3.树与图的存储 
    树是一种特殊的图 树是无环连通图 所以这里只讲图就可以了
    图分为两种
        1.有向图    指边是有方向的              如果给定 a 和 b 这条边的话 意味着我们可以从 a 走到 b 即 a->b
        2.无向图    指边是无方向的（都有方向）  如果给定 a 和 b 这条边的话 意味着我们可以从 a 走到 b 也可以从 b 走到 a 即 a->b b->a
            因此我们在算法题里 如果有个图是无向图的话 我们建两条边就可以了 建一条 a->b 的 再建一条 b->a 就可以了
            因此无向图就是一种特殊的有向图 我们只需要考虑有向图就可以了
        
        有向图的存储一般有两大类
        1.邻接矩阵
            开个二维数组 g[a, b] 存储 a->b 这条边的信息
                如果有权重的话 g[a, b]就是这个权重 
                如果没有权重的话 g就是一个bool值 true的话就表示有边 false的话就表示没有边
            如果有重边的话 邻接矩阵是不能存储重边的 如果有重边的话 就只能保留一条
                如果要求最短路的话 就保留一条最短的边
            
            邻接矩阵用的比较少 因为比较浪费空间 它的空间复杂度是 n^2 的
                比较容易存储稠密图 稀疏图的话就不是很好存了
                
        2.用的最多的是邻接表
            邻接表就是之前讲过的单链表 跟之前讲的拉链法的哈希表是一模一样的
                拉链法的哈希表是开了n个单链表 每一个位置都有一个单链表
                邻接表存储有向图也是一样的 有n个点每个点上都有一个单链表
                
                每个点上的单链表存的是这个点可以走到哪儿个点
                    单链表内部的点的次序是无关紧要的 只需要存下来就可以
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10, M = N * 2;

int h[N], e[M], ne[M], idx;
// h 存的是 n 个链表的链表头 e 存的是每一个节点的值是多少 ne 存的是每一个节点的 next 指针是多少 idx 存的是现在维护的是啥

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

int main(){
    memset(h, -1, sizeof h);
    //单链表的初始化就是让头节点指向-1 我们现在是有n个头节点 所以只要让n个头节点全部指向-1就可以了
}
// cin 和 scanf 只有在输入输出在100w的时候 才必须用 scanf 不然100w以下的数据区别都不是很大的
// 邻接表的话可以用vector来存 但是不如数组模拟的快 vector效率稍微低一些

4.树与图的深度优先遍历
图的深度优先遍历
    因为无向图也是一种特殊的有向图 所以只需要考虑有向图是如何遍历的就可以了
    而且树也是一种特殊的图 所以只需要考虑图是怎么遍历的就可以了
5.树与图的宽度优先遍历
6.拓扑排序

                   数据结构    空间

(俗称暴搜) 即某一道题目的所有方案全部遍历一遍(比较方便)

1. 深度优先搜索 DFS stack O (n) 不具有最短路性质
重点：到底是用什么样的顺序来遍历这个方案
两个重要概念：
1) 回溯
2) 剪枝

凡是算法思路比较奇怪的 一般都用 DFS 来做 或者是对空间要求比较高的

2. 宽度优先搜索 BFS queue O (2^n) 最短路
所以凡是最小步数最短距离最少操作几次基本都是 BFS
3. 树与图的存储
树是一种特殊的图树是无环连通图所以这里只讲图就可以了
图分为两种
1. 有向图指边是有方向的如果给定 a 和 b 这条边的话意味着我们可以从 a 走到 b 即 a->b
2. 无向图指边是无方向的（都有方向）如果给定 a 和 b 这条边的话意味着我们可以从 a 走到 b 也可以从 b 走到 a 即 a->b b->a
因此我们在算法题里如果有个图是无向图的话我们建两条边就可以了建一条 a->b 的再建一条 b->a 就可以了
因此无向图就是一种特殊的有向图我们只需要考虑有向图就可以了

    有向图的存储一般有两大类
    1.邻接矩阵
        开个二维数组 g[a, b] 存储 a->b 这条边的信息
            如果有权重的话 g[a, b]就是这个权重
            如果没有权重的话 g 就是一个 bool 值 true 的话就表示有边 false 的话就表示没有边
        如果有重边的话 邻接矩阵是不能存储重边的 如果有重边的话 就只能保留一条
            如果要求最短路的话 就保留一条最短的边

        邻接矩阵用的比较少 因为比较浪费空间 它的空间复杂度是 n^2 的
            比较容易存储稠密图 稀疏图的话就不是很好存了

    2.用的最多的是邻接表
        邻接表就是之前讲过的单链表 跟之前讲的拉链法的哈希表是一模一样的
            拉链法的哈希表是开了 n 个单链表 每一个位置都有一个单链表
            邻接表存储有向图也是一样的 有 n 个点每个点上都有一个单链表

            每个点上的单链表存的是这个点可以走到哪儿个点
                单链表内部的点的次序是无关紧要的 只需要存下来就可以

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10, M = N * 2;

int h[N], e[M], ne[M], idx;
//h 存的是 n 个链表的链表头 e 存的是每一个节点的值是多少 ne 存的是每一个节点的 next 指针是多少 idx 存的是现在维护的是啥

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

int main(){
memset(h, -1, sizeof h);
// 单链表的初始化就是让头节点指向 - 1 我们现在是有 n 个头节点所以只要让 n 个头节点全部指向 - 1 就可以了
}
//cin 和 scanf 只有在输入输出在 100w 的时候才必须用 scanf 不然 100w 以下的数据区别都不是很大的
// 邻接表的话可以用 vector 来存但是不如数组模拟的快 vector 效率稍微低一些

4. 树与图的深度优先遍历
图的深度优先遍历
因为无向图也是一种特殊的有向图所以只需要考虑有向图是如何遍历的就可以了
而且树也是一种特殊的图所以只需要考虑图是怎么遍历的就可以了
5. 树与图的宽度优先遍历
6. 拓扑排序

浮点数二分

介绍下stl用法