割点
对于一个无向图 G ,如果把一个点 u 删除后这个图的极大连通分量数增加了,那么这个点就是这个图的割点(又称割顶)。
题目描述
给出一个 n 个点, m 条边的无向图,求图的割点。
输入格式
第一行输入两个正整数 n,m 。
下面 m 行每行输入两个正整数 x,y 表示 x 到 y 有一条边。
输出格式
第一行输出割点个数。
第二行按照节点编号从小到大输出节点,用空格隔开。
输入输出样例
输入
1 2 3 4 5 6 7 8
| 6 7 1 2 1 3 1 4 2 5 3 5 4 5 5 6
|
输出
说明/提示
对于全部数据, 1≤n≤2×104 , 1≤m≤1×105 。
点的编号均大于 0 小于等于 n 。
tarjan 图不一定联通。
Tarjan 算法求割点
解决这类连通性相关的图论问题通常都要请出 Tarjan 算法。关于 Tarjan 算法的基本实现思路可以参考这里。
思路
在无向图中使用 Tarjan 算法遍历图时,若对于某个点 u ,若有dfn[u]=low[u]
,说明从 u 向下 DFS 无法回到其祖先节点,这意味着以 u 为根的 DFS 生成子树下的所有节点和 u 的祖先节点之间的路全都经过 u ,若去掉 u 则图将不连通,说明 u 就是割点。
解决方案
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80
| #include<iostream> #include<cstdio> #include<algorithm> #include<cstdlib> #include<cstring> using namespace std; const int maxn = 100500; int n, m, cnt = -1, cc; int head[maxn], dfn[maxn], low[maxn], fa[maxn], sum; bool ans[maxn]; struct Node { int to, next; } edge[maxn*2]; void addedge(int u, int v) { ++cnt; edge[cnt].to = v; edge[cnt].next = head[u]; head[u] = cnt; } void tarjan(int u) { int son = 0, root; ++cc; dfn[u] = cc; low[u] = cc; for(int i=head[u]; ~i; i=edge[i].next) { int v = edge[i].to; if(fa[u]!=v) { if(!dfn[v]) { fa[v] = u; tarjan(v); low[u] = min(low[u], low[v]); if(low[v]>=dfn[u]) { ans[u] = true; if(fa[u]==u) { root = u; son++; } } } else low[u] = min(low[u], dfn[v]); } } if(son==1) ans[root] = false; } int main() { scanf("%d %d", &n, &m); memset(head, -1, sizeof(head)); for(int i=1; i<=m; i++) { int u, v; scanf("%d %d", &u, &v); fa[u] = u; fa[v] = v; addedge(u, v); addedge(v, u); } for(int i=1; i<=n; i++) { if(!dfn[i]) tarjan(i); } for(int i=1; i<=n; i++) { if(ans[i]) sum++; } printf("%d\n", sum); for(int i=1; i<=n; i++) { if(ans[i]) printf("%d ", i); } return 0; }
|
请参见