求图的割点，割边（啊哈算法）

     时间戳：深度优先遍历时，访问每个节点的先后顺序从 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; }

总结

以上是生活随笔为你收集整理的求图的割点，割边（啊哈算法）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。