???? 時間戳：深度優先遍歷時，訪問每個節點的先后順序從 1到n；
??? 使用 num[] 來記錄每個頂點的先后順序；
??? 滿足割點的條件：子節點 v 不經過父節點 u 是不能達到u的祖宗節點的（也就是已經被訪問
??? 的那些節點）；
??? 使用 low[] 來記錄每個節點不經過父節點能到達的最早頂點的時間戳；
??? 因此滿足割點的結點是： low[v] >= num[u] ；意思是子節點v不經過父節點u能到達的最早時間
??? 戳也不過是u，那么把u去掉，不就能把圖分成兩部分了；但是這也僅僅是來檢測非根節點的方法，
??? 根節點是否為割點還要特判，如果根節點的子節點有兩個孩子，且兩個孩子不能相互到達，那么
??? 根節點就是割點；

/**時間戳：深度優先遍歷時，訪問每個節點的先后順序從 1到n；使用 num[] 來記錄每個頂點的先后順序；滿足割點的條件：子節點 v 不經過父節點 u 是不能達到u的祖宗節點的（也就是已經被訪問的那些節點）；使用 low[] 來記錄每個節點不經過父節點能到達的最早頂點的時間戳；因此滿足割點的結點是： low[v] >= num[u] ；意思是子節點v不經過父節點u能到達的最早時間戳也不過是u，那么把u去掉，不就能把圖分成兩部分了；但是這也僅僅是來檢測非根節點的方法，根節點是否為割點還要特判，如果根節點的子節點有兩個孩子，且兩個孩子不能相互到達，那么根節點就是割點； *//**data:6 71 41 34 23 22 52 65 6 *//** #include <iostream> #include <algorithm> #include <vector>using namespace std;const int maxn = 1e5+10; vector<int> Adj[maxn]; ///鄰接表 int num[maxn] , low[maxn] ; ///時間戳 int flag[maxn]; ///頂點編號是割點則記為1，否則為0； int root , index; ///root為根節點，index為時間戳void dfs(int u,int fath) ///fath為u的父節點 {int child = 0; ///u的子節點數目++index; ///時間戳加一num[u] = index;low[u] = index; ///最開始時間戳就是自己for(int i=0;i<Adj[u].size();++i){int v = Adj[u][i];if(num[v] == 0) ///如果v還沒被訪問過{++child; ///將v歸為u的子節點，子節點數目加一dfs(v,u); ///遞歸low[u] = min(low[u] , low[v]); ///要將u的時間戳（是low，不是num）更新if(u != root && low[v] >= num[u]) ///如果u不是根節點，并且滿足割點的條件flag[u] = 1;///如果u是根節點且孩子節點也有兩個，那么根節點就是割點；///并且我們能證明出兩個孩子節點一定不能通過若干結點中轉相互到達；///假設能相互到達，那么這兩個孩子節點一定不能共同車成為u的孩子節點，///因為一個孩子節點進行遞歸以后，會把該孩子節點能夠連通且沒有被訪問的結點///進行訪問；if(u == root && child == 2)flag[u] = 1;}///如果v已經被訪問過且是u的祖宗節點（并不是父節點），則更新當前節點 u 能否///訪問到最早頂點的時間戳；else if(v != fath)low[u] = min(low[u] , num[v]);} }int main() {int n,m;cin >> n >> m;for(int i=0;i<m;++i){int u,v;cin >> u >> v;Adj[u].push_back(v);Adj[v].push_back(u);}root = 1;dfs(1,root);for(int i=1;i<=n;++i)if(flag[i] == 1)cout << i << endl;return 0; } */

2）割邊：
??? 滿足割邊的條件：子節點 v 不經過父節點 u 是不能達到u的祖宗節點的（也就是已經被訪問
??? 的那些節點）；并且不能經過其點到達父節點；即：low[v] > num[u]；

/** 2）割邊：滿足割邊的條件：子節點 v 不經過父節點 u 是不能達到u的祖宗節點的（也就是已經被訪問的那些節點）；并且不能經過其點到達父節點；即：low[v] > num[u]； *//**dtta:6 61 41 34 23 22 55 6 */#include <iostream> #include <algorithm> #include <vector>using namespace std;const int maxn = 1e5+10; vector<int> Adj[maxn]; ///鄰接表 int num[maxn] , low[maxn] ; ///時間戳、 int root , index; ///root為根節點，index為時間戳void dfs(int u,int fath) ///fath為u的父節點 {++index; ///時間戳加一num[u] = index;low[u] = index; ///最開始時間戳就是自己for(int i=0;i<Adj[u].size();++i){int v = Adj[u][i];if(num[v] == 0) ///如果v還沒被訪問過{dfs(v,u); ///遞歸low[u] = min(low[u] , low[v]); ///要將u的時間戳（是low，不是num）更新if(low[v] > num[u]) ///如果滿足割邊的條件printf("%d---->%d\n",u,v);}///如果v已經被訪問過且是u的祖宗節點（并不是父節點），則更新當前節點 u 能否///訪問到最早頂點的時間戳；else if(v != fath)low[u] = min(low[u] , num[v]);} }int main() {int n,m;cin >> n >> m;for(int i=0;i<m;++i){int u,v;cin >> u >> v;Adj[u].push_back(v);Adj[v].push_back(u);}root = 1;dfs(1,root);return 0; }

總結

以上是生活随笔為你收集整理的求图的割点，割边（啊哈算法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。