记算法思路，不只是模板

连通图：所有点都可以走通的图
生成树：最小边个树的连通图
最小生成树：生成树里边的权重最小的
边正负无所谓
生成树性质为不能存在自环

最小生成树
一般都为无向图

prim算法(像digikstra)
    稠密图：朴素版prim算法 o(n^2)
        核心：掌握算法流程

        算法流程：
            1. 将所有距离初始化为正无穷
            2. n次迭代
                i. 找到不在集合中的距离最小的点t，集合指在当前连通块中的所有点
                ii. 用t更新其他点到**集合**的距离
                iii. st[t] = true; 将t加到集合中去
                (点到集合的距离定义为这个点连到集合内部的某条长度最小的边)
                （选中t距离对应的边）
                (digi一上来就选中了一个点，所以只需要迭代n - 1次，而prim一开始无点需要迭代n次)

    稀疏图：堆优化版prim o(mlogn) （不常用，麻烦，蛇皮，略过）

Kruskal算法 o(mlogm)
    算法步骤
        1. 将所有边按权重从小到大排序 (O(mlogm) 算法瓶颈(不过排序时间复杂度常数小，实际kruskal挺快)
        2. 从小到大枚举每条边a, b, 权重c
            ifa, b不连通 then将这条边加入到集合中 (在a和b之间连一条边) 并查集的简单应用
            （参考https://www.acwing.com/activity/content/problem/content/886/ 连通块中点的数量）


稠密冲朴素版prim算法， 稀疏用Kruskal算法

二分图
如何判别是否为二分图
如果一个图可以被分为两类，且所有边在集合之间而不在集合内部则此图为二分图
一个图是二分图当且仅当图中不含奇数环（环中边的数量是一个奇数）
dfs - 染色法 o(n + m)
只要染色过程中没有矛盾，则一定不含奇数幻，图一定为二分图

        思路：
            从前往后遍历每个点
                if（i未染色) dfs(i) (将此连通块所有点都染一遍)

求二分图最大匹配
    给定二分图，求匹配成功最大的边的数量
        *匹配：不存在两条边共用一个点
    匈牙利算法（草原算法） 最坏o(mn)，实际一般远小于mn
        核心find操作
            当x发现y心有所属时，就看y前男友有没有新女友，ntr一下