文章

25

粉丝

0

获赞

0

访问

244743

头像
Tarjan-无向图的割点
经验总结
发布于2020年4月18日 00:46
阅读数 9044

B城:

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e6 + 200;
long long h[N], e[N], next_pos[N], idx, n, m, time_num, ans[N], root, dfn[N], low[N], size[N];
bool cut[N];//是不是割点

void add(int a, int b){
	e[++idx] = b;
	next_pos[idx] = h[a];
	h[a] = idx;
}

void tarjan(int x){
	dfn[x] = low[x] = ++time_num;
	size[x] = 1;
	int child = 0, sum = 0;
	for (int i = h[x]; i; i = next_pos[i]){
		int j = e[i];
		if (!dfn[j]){
			tarjan(j);
			size[x] += size[j];
			low[x] = min(low[x], low[j]);
			if (low[j] >= dfn[x]){
				child++;
				ans[x] += size[j] * (n - size[j]);
				sum += size[j];
				if (child > 1 || x != root){
					cut[x] = true;
				}
			}
		}
		else{
			low[x] = min(low[x], dfn[j]);
		}
	}
	if (cut[x]){
		ans[x] += (n - sum - 1)*(sum + 1) + n - 1;
	}
	else{
		ans[x] = 2 * (n - 1);
	}
}

int main(){
	cin >> n >> m;
	memset(cut, false, sizeof cut);
	for (int i = 1; i <= m; i++){
		int x, y;
		cin >> x >> y;
		add(x, y);
		add(y, x);
	}

	root = 1;//根节点为1
	tarjan(1);
	for (int i = 1; i <= n; i++){
		cout << ans[i] << endl;
	}

	return 0;
}

 



登录后发布评论

暂无评论,来抢沙发