Graph Theory
- priority_queue的bfs相当于使用了dijkstra的思想。
- 拓扑序可以用来判断图中是否有环，方法是在BFS之后看是否有入度不为0的点。
强连通分支
求强连通分支有两种方法，korasaju和tarjan。
korasaju是进行两次dfs覆盖全图（实际上是两种dfs，覆盖全图需要多次dfs），第一次给结点标起始和结束时间，第二次把图反向并从结束时间最大的结点开始dfs，每次dfs所能到达的结点为一个强连通分支。下面来简单讲一下为什么这样做。第二次dfs过程中每次dfs的起点为结束时间最大的点，这样就可以保证是第一次dfs中的某一棵搜索树的根节点。那么从任意一个第一次dfs的根节点开始的对反图的dfs都不可能跨越到在第一次dfs中比该根节点更早的搜索树中。因为假设能跨越，说明反图中晚的搜索树有指向更早搜索树的边，即原图中有从更早搜索树指向晚搜索树的边。那么晚搜索树根本就不会单独成树，与之前假设矛盾。这样就保证了第二次dfs过程中每次dfs只可能在第一次的某一棵子树中进行，不可能跨树搜索。第二次能根u搜到的点v，说明原图中v可以到达u，而第一次v一定是u树中的结点，也就是说u可到达v,从而一定能形成强连通分支。
tarjan算法则是利用一次dfs，整个过程中对每个结点记录两个值，dfn[u]结点的访问时间，low[u]结点及其子节点所能直接访问到的结点v中dfn[v]的最小值。（这里单次返祖和多次返祖是无所谓的）每次把访问到的结点入栈，一旦搜索完某一结点u的所有子节点后发现low[u]==dfn[u]则弹栈直到u被弹出，此过程弹出的点为一个强连通分支。这样也就保证了，栈中所有结点都是可以到达某一父节点的，也就是说一旦某个点可以到达栈中某个点，它一定可以到达某父节点。
2-sat问题
有n组元素，每组两个，从中选出n个，每组选且只选一个。这2n个元素中有些元素之间有矛盾关系，要求选出的n个元素中，任意两个之间都不存在矛盾。问是否存在满足条件的选取方案。这就是2-sat问题。解决方法如下，例如a,b一组，c,d一组，a,c有矛盾，那么选a则不能选c，不选c则必须选d。所以选a就必须选d。同理选c就必须选b。我们引两条边，a->d, c->b。对于所有的矛盾都用类似的方式加边。这样只要从x点可以走到y点，那么选x点就必须选y点。然后对全图求强连通分支。在一个强连通分支中，选了一个点，则必须选强连通分支中的所有点。如果有某两个点属于同一组，且属于同一个强连通分支，则必然无解，否则有解。为什么否则必然有解呢？假设无环仍无解。那么不妨设由a经过很多点最终走向b（ab在同一组）导致了无解。因为原图具有对称性和传递性，那么b必然也能走到a，所以就成了环，与假设矛盾。所以假设不成立。
欧拉路径
1.定理：无向图G有欧拉通路的充分必要条件是G为连通图，并且G仅有两个奇度结点或者无奇度结点。
（1）当G是仅有两个奇度结点的连通图时，G的欧拉通路必以此两个结点为端点。
（2）当G是无奇度结点的连通图时，G必有欧拉回路。
2.一个有向图D具有欧拉通路，当且仅当D是连通的，且除了两个顶点外，其余顶点的入度均等于出度，这两个特殊的顶点中，一个顶点的入度比出度大１，另一个顶点的入度比出度小１．推论：一个有向图D是欧拉图（具有欧拉回路），当且仅当D是连通的，且所有顶点的出度等于入度。
求欧拉回路
对全图进行dfs，从规定起点开始。过程中记录经过了哪些边，以保证每条边只经过一次。当一个点的所有边都遍历完成后，把该点入栈。最后依次弹栈得到的就是欧拉路径。被入栈的点都是走投无路的点，如果存在欧拉路径，第一次出现的走投无路一定是在走回到起点时，因为其他情况无论怎么走只可能略过一些边，而不可能走进死路。
差分约束系统
对于一组类似于xa-xb>=c的不等式求是否有满足的解，用bellman来解，bellman是使得dist[v] <= dist[u] + c。
差分约束是使得A-B>=C即 B<=A+(-C)。所以对于每个这样的不等式我们就从A向B连一条边边的权值为-C。
观察是否有负权回路，没有则有解，有则无解。求得的最短路即为最大解。如果题目没有规定源点的值可以随意，其余点初始化为正无穷，因为差分约束的条件就是各个数字之间的差要满足某些条件。并没有规定某个数字的确定值，所以经过最短路运算后也只能得到相对值。
用spfa做差分约束。不能向bellman一样。还是把差分约束理解为求最长路比较直观。
对于dist[a]-dist[b]>=c，我们可以看作dist[a]>=dist[b]+c，所以我们如果初始化为负无穷，起点初始化为0，并让所有的不等式都满足，那么就是在求一个最长路。
spfa不能处理非连通图，需要加入超级源（一个到所有点都有一条长度为0的边的点），并把超级源作为起点，才能保证在扩展过程中到达每个点。否则差分约束系统的部分内容就不会被检测到。
差分约束系统有两种方式可以求解，最短路和最长路。当我们把不等式整理成d[a]+w<=d[b]时，我们求最长路。整理成d[a]+w>=d[b]时，我们求最短路。当求最短路时，我们通常要把各点距离初始化为正无穷，求最短路，把各点距离逐渐减小，直到符合所有不等式。也就是开始各点不符合条件，后来通过减小变得符合了，所以一定是符合条件的最大值。既然是求最大值，并且是减小各点距离，也就是把各点由数轴的右侧向左侧拉，所以我们一定要选择一个最终在数轴最左侧的点，并初始化为0，把所有正无穷的点拉近到符合不等式。最长路同理。
双连通分支
双连通分支分就是一个极大化（一个点只要加进来之后该分支仍然是双连通分支就加进来）的分支，去掉任意一条边这个分支内部仍然连通。也可以理解为去掉桥之后，每个连通分支就是原图的双连通分支。
注意：北大培训中说有两种双连通（边的和点的），其实只有边的双连通才是双连通的正规定义。所以我们不对点的双连通进行讨论。
求割点和桥可以用tarjan算法，对图进行dfs，记录每个点的第一次到达时间dfn[i]。并记录一个low[i]表示该点及其子孙结点所能到达的dfn最小的点。这个到达并不是普通意义的到达，而是在遍历过程中，通过非树枝边（一定是返祖边，因为是无向图，没有横叉边）能够直接到达的点（而不是连续使用返祖边能到达的）。这样就可以把low总结为low[u] = min(low[v]（v为u的儿子结点）,dfn[v]（v是u通过返祖边能到达的点）,dfn(u));
然后我们可以粗略地认为返祖边可以连同树枝边共同构成一个环。环一定是双连通的（一定不是桥），不在环内的边一定是桥。
这样我们就可以总结为：若边(u,v)，dfn[u] < low[v]（即不在环内），则为桥。
另外有定理，当把边的双连通分支缩点后形成了一个有向无环图，叶子（度为1的点）的个数为n，则需要在原图中添加(n + 1)/2条边，可以使原图变为没有桥的双连通图。
求割点除了tarjan算法，还有一种O(n^2)的算法，就是分别把每个点作为根，进行dfs，看根有几个子结点，如果大于一个则为割点否则不是割点。
我们正常的做法是求桥，删桥，求连通分支，缩点，构建新图，求叶子数。
求边得双连通分支的方法
我们正常的做法是求桥，删桥，求连通分支。
我们有一种简便方法。需要对tarjan算法做一些变化。我们之前规定low[u]是其子孙通过一条返祖边直接到达的点，把这个改成是其子孙可以连续通过多条返祖边所能到达的点。那么low[u]=min(low[v],dfn[u]);
这样做的缺陷是，不能求割点了，多次返祖会导致求割点的错误，在多环两两以单个点相连排成一条线，且每两个连接点间只有一条边的情况中，那些连接点本应是割点，但是在dfs过程中，这些连接点之间的边又恰好不是树枝边的话，low[u]可能会通过多次返祖,从一个割点不断的经过这些割点到达最上边的割点才记录下low[u]。
这样中间的割点就都不符合dfn(u)<=low[v]了。
但是这样做有一个好处，就是所有的对于边的双连通分支都以low标记出来了，即属于同一双连通分支的所有点的low都等于同一个值。因为在不遇到桥的情况下，low可以返祖到该连同分支在遍历树中的最高点（dfn最小的点）。
这样就相当于整理出了所有的对于边的双连通分支。接下来计算新图中每个点的度，我们直接遍历所有的边，观察边的两端点是否属于同一分支，若不属于则把两点在新图中的度数+1。然后看有多少个度数为1的点（即叶子数），再通过公式计算即可。
求点双连通分支的方法
首先，用tarjan算法，dfs遍历全图，用dfs_dep数组记录每个点在遍历过程中的深度，用low_point数组记录每个点的邻居中（不包括父亲）深度最浅的节点，把遍历过程中所有树枝边入栈。我们在遍历过程中，对于一个节点u，如果在遍历完成它的某子节点v之后，发现low_point[v]==dfs_dep[u]则说明u与v及其子孙构成一个点双连通分量，我们不停弹栈直到边(u,v)被弹出，和这些边相关的点构成一个点双连通分量。当我们遍历完点u的所有子孙之后，若发现low_point[u]==dfs_dep[u]，则说明u不会再与其祖宗节点构成点双连通分量，但此时还有一条u的父亲和u的连边存在于栈顶，我们要把它弹出并丢弃。
无向图的最小割
stoer_wagner算法
每次从0点开始，进行一种类似于最大生成树的操作，唯一与最大生成树的区别就是在选择把哪个点加进来的时候，不是根据连到它的边的长度，而是根据它到树的所有边的长度和。然后记录最后两个进树的点合并（缩点），并用这两点间的割来更新最小值。然后不断重复此操作（生成树、缩点、最小值），直到所有点都缩为1点。
树形图中的最长路
求树形图中最长路的方法：任选一结点为根，找最深结点。并以最深结点为根，找最深结点，其深度即为所求。