本文主要是介绍Blockade -tarjan求割点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：https://ac.nowcoder.com/acm/problem/50412
来源：牛客网
题目描述
Byteotia城市有n个城镇，m条双向道路。每条道路连接两个不同的城镇，没有重复的道路，所有城镇连通。
输出n个数，代表如果把第i个点去掉，将有多少对点不能互通。
输入描述
输入n,m及m条边。
输出描述
输出n个数，代表如果把第i个点去掉，将有多少对点不能互通。
分析
tarjan判断割点，和蓝书上面的BLO有点类似，区别就是BLO是去边，这里是去点
首先我们可以判断，如果一个点是不是割点，那么即使这个点去除，也不会影响整张图的连通性，所以仅仅是被删除的点和其他点不能进行连接，答案为2 * (n - 1)
如果一个点是割点的话，那么去掉这个点就可以把这张图分成几个树形结构，任意两个树形结构之间不能进行连接，所以我们只需要求树的大小即可
代码
#include <cstring>
#include <iostream>using namespace std;
typedef long long ll;const int N = 1e5 + 10, M = 1e6 + 10;int n,m;
int h[N],ne[M],e[M],idx;
int dfn[N],low[N],ti;
int root;
ll ans[N];
ll Size[N];
bool st[N];void add(int x,int y){e[idx] = y,ne[idx] = h[x],h[x] = idx++;
}void tarjan(int u){dfn[u] = low[u] = ++ti;int cnt = 0;Size[u] = 1;ll sum = 0;for(int i = h[u];~i;i = ne[i]){int j = e[i];if(!dfn[j]){tarjan(j);Size[u] += Size[j];low[u] = min(low[u],low[j]);if(low[j] >= dfn[u]){cnt++;sum += Size[j];if(u != root || cnt > 1) st[u] = true;ans[u] += Size[j] * (n - Size[j]);}}else low[u] = min(low[u], dfn[j]);}if(!st[u]) ans[u] = 2 * (n - 1);else ans[u] += 1ll * (n - 1) + (n - 1 - sum) * (sum + 1);
}int main(){scanf("%d%d",&n,&m);memset(h,-1,sizeof h);while(m--){int a,b;scanf("%d%d",&a,&b);add(a,b),add(b,a);}for(root = 0;root < n;root++)if(!dfn[root])tarjan(root);for(int i = 1;i <= n;i++)printf("%lld\n",ans[i]);return 0;
}
这篇关于Blockade -tarjan求割点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
