• 注册
当前位置：1313e > 默认分类 >正文

无向图的割顶和桥、无向图的双连通分量、有向图的强连通分量

总结自《算法竞赛入门经典——训练指南》（刘汝佳），具体分析请详见书中解析。

 

时间戳：说白了就是记录下访问每个结点的次序。假设我们用 pre 保存，那么如果 pre[u] > pre[v]， 那么就可以知道先访问的 v ，后访问的 u 。

现在给定一条边， (u, v)， 且 u 的祖先为 fa, 如果有 pre[v] < pre[u] && v != fa, 那么 (u, v) 为一条反向边。

无向图的割顶和桥：

求割顶：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include using namespace std;const int maxn = 1000;vector<int> G[maxn];
int pre[maxn], dfs_clock, low[maxn], n;
bool iscut[maxn];void init(){for(int i=0; i) G[i].clear();memset(iscut, false, sizeof(iscut));memset(pre, 0, sizeof(pre));dfs_clock = 0;
}int dfs(int u, int fa){ //u在DFS树中的父结点是faint lowu = pre[u] = ++dfs_clock;int child = 0; //子结点数目for(int i=0; i){int v = G[u][i];if(!pre[v]){    //没有访问过v, 没有必要用vis标记了child++;int lowv = dfs(v, u);lowu = min(lowu, lowv); //用后代的 low 函数更新 u 的 low 函数if(lowv >= pre[u]){iscut[u] = true;}}else if(pre[v] < pre[u] && v != fa){ //(u,v)为反向边lowu = min(lowu, pre[v]);   //用反向边更新 u 的 low 函数
        }if(fa < 0 && child == 1) iscut[u] = false;}low[u] = lowu;return lowu;
}int main(){int m, u, v;scanf("%d%d", &n, &m);init();for(int i=0; i){cin>>u>>v;G[u].push_back(v);G[v].push_back(u);}for(int i=0; iif(!pre[i]){dfs(i, -1);}for(int i=0; i//将割点输出if(iscut[i]) printf("%d ", i);}putchar('\n');return 0;
}
View Code

桥：

如果v的后代只能连回 v 自己（即 low(v) > pre[u)), 只需删除(u, v)一条边就可以让图G非连通了，满足这个条件的边称为桥。换句话说，我们不仅知道结点u是割顶，还知道了（u，v）是桥。

样例：

12 12
0 1
0 4
4 8
8 9
4 9
2 3
2 7
2 6
6 7
3 7
10 7
7 11

无向图的双连通分量：

割顶的bccno无意义：割点的bccno会被多次赋值，所以它的值无意义。

调用结束后， S保证为空：

 

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include using namespace std;const int maxn = 1000+10;int pre[maxn], iscut[maxn], bccno[maxn], dfs_clock, bcc_cnt;
vector<int> G[maxn], bcc[maxn];struct Edge{int u, v;
};stack S;int dfs(int u, int fa){int lowu = pre[u] = ++dfs_clock;int child = 0;for(int i=0; i){int v = G[u][i];Edge e = (Edge){u, v};if(!pre[v]){S.push(e);child++;int lowv = dfs(v, u);lowu = min(lowu, lowv);if(lowv >= pre[u]){iscut[u] = true;bcc_cnt++; bcc[bcc_cnt].clear();for(;;){Edge x = S.top(); S.pop();if(bccno[x.u] != bcc_cnt) {bcc[bcc_cnt].push_back(x.u);bccno[x.u] = bcc_cnt;}if(bccno[x.v] != bcc_cnt) {bcc[bcc_cnt].push_back(x.v);bccno[x.v] = bcc_cnt;}if(x.u == u && x.v == v) break;}}}else if(pre[v] < pre[u] && v != fa){S.push(e);lowu = min(lowu, pre[v]);}}if(fa < 0 && child == 1) iscut[u] = 0;return lowu;
}void find_bcc(int n){memset(pre, 0, sizeof(pre));memset(iscut, 0, sizeof(iscut));memset(bccno, 0, sizeof(bccno));dfs_clock = bcc_cnt = 0;for(int i=0; i){if(!pre[i]) dfs(i, -1);}
}int main(){int m, u, v, n;scanf("%d%d", &n, &m);for(int i=0; i){cin>>u>>v;G[u].push_back(v);G[v].push_back(u);}find_bcc(n);printf("%d\n", bcc_cnt);    //双连通分量的个数for(int i=1; i<=bcc_cnt; i++){  //输出每个双连通分量for(int j=0; j){printf("%d ", bcc[i][j]);}putchar('\n');}return 0;
}
View Code

样例：

5 6
0 1
0 2
1 2
2 3
2 4
3 4

有向图的强连通分量：

 运行完DFS栈为什么始终为空：

换种说法， w->u->v->e, e->u, 将u, v, e 找出后，什么时候弹出的 w ？ 因为 对于 w, 它的 lowlink 和 pre 相等，因此 w 作为一个 SCC， 会被弹出。

#include 
#include 
#include 
#include 
#include using namespace std;const int maxn = 2000;
int pre[maxn], lowlink[maxn], sccno[maxn], dfs_clock, scc_cnt;
vector<int> G[maxn];
stack<int> S;void dfs(int u){pre[u] = lowlink[u] = ++dfs_clock;S.push(u);for(int i=0; i){int v = G[u][i];if(!pre[v]){dfs(v);lowlink[u] = min(lowlink[u], lowlink[v]);}else if(!sccno[v]){lowlink[u] = min(lowlink[u], pre[v]);}}if(lowlink[u] == pre[u]){scc_cnt++;for(;;){int x = S.top(); S.pop();sccno[x] = scc_cnt;if(x == u) break;}}
}
void find_scc(int n){//栈始终为空，不用初始化dfs_clock = scc_cnt = 0;memset(sccno, 0, sizeof(sccno));memset(pre, 0, sizeof(pre));for(int i=0; i){if(!pre[i]) dfs(i);}
}
int main(){int n, m, u, v;scanf("%d%d", &n, &m);for(int i=0; i) G[i].clear();for(int i=0; i){scanf("%d%d", &u, &v);G[u].push_back(v);}find_scc(n);for(int i=1; i<=scc_cnt; i++){for(int j=0; jif(sccno[j] == i) printf("%d ", j);putchar('\n');}return 0;
}
View Code

样例：

12 17

0 1
1 2
1 3
1 4
2 5
4 1
4 5
4 6
5 2
5 7
6 7
6 9
7 10
8 6
9 8
10 11
11 9

 

转载于:https://www.cnblogs.com/tanhehe/archive/2013/05/20/3089765.html

本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 162202241@qq.com 举报，一经查实，本站将立刻删除。

最新评论

欢迎您发表评论:

请登录之后再进行评论

登录
相关推荐
Copyright © 2023 - 2024 1313e All Rights Reserved