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