图论

DFS 深搜 BFS 广搜 DAG 有向无环图 SCC 强连通分量 BCC 双连通分量（一般情况是同点-双连通分量，实际上双连通分量包括点-双连通分量（任意两点至少存在两条“点不重复”的路径）和边-双连通分量（任意两点至少存在两条“边不重复”的路径），下文BCC如不作特殊说明，均代表双连通分量） 割顶：对于无向图删除后一个顶点x后，如果连通分量数目增加。则x称为割顶。 割边：……，删掉一条边后，连通分量数目增加，则该边为割边。 计算BCC，采用DFS（类似Tarjan）： 点BCC：搜索遇到割点就弹栈； 边BCC：搜索遇到割边就弹栈。

—————————华丽分割线—————————— LCA：最近公共祖先 1、采用ST算法的倍增思想，先将待查询点p，q“提”到同一高度，在同时向上“提”。为在线算法，预处理O（nlogn），每次查询O(logn)。 2、采用dfs原理的Tarjan算法。为离线算法，预处理O(n)，每次查询O(1)。

—————————华丽分割线—————————— 生成树相关 增量最小生成树：从包含n个点的空图开始，依次加入m条带权边。每加入一条边，求图的最小生成树（若存在）。 先求一遍最小生成树，之后每加入一条边，会形成一个环，将环上最大权的边删去即可。而路径唯一，随便乱搞。时间：O(nm)。

最小瓶颈路：在无向加权图中求给定u，v间的一条路径使路径上最长边最小《==》最小生成树上的路径。

若干对节点最小瓶颈路：求一遍最小生成树，1、再进行树上倍增可在logn时间求得每组节点。2、dfs，用f(u,v)记录（u，v间最小瓶颈路的最大边长），每次访问一个新节点v，考虑已访问过的所有节点x，对f（x，v）进行更新。So时间为O(n^2)。

次小生成树：求出最小生成树+最小瓶颈路，枚举加入的新边，删去u，v最小瓶颈路最大边即可成为一棵新的生成树，用其权值更新答案。时间：O（n^2）。

有向生成树：见窝的另一篇博文~~~http://blog.csdn.net/moon1125666900/article/details/54885362