求调,第一次做蓝题
查看原帖
求调,第一次做蓝题
1047303
OTOI2025楼主2025/1/19 20:59
#include<cstdio>
#include<algorithm>

using namespace std;

const int maxn = 5000000;
struct Edge {
	int u, v, next;
} e[maxn << 1];

int len, head[maxn];
void insert(int u, int v) {
	e[++len] = {u, v, head[u]};
	head[u] = len;
}

int n, m;
void input() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		int u, v;
		scanf("%d %d", &u, &v);
		insert(u, v);
		insert(v, u);
	}
}

int low[maxn], dfn[maxn], time;
int size[maxn], ans[maxn];
void Tarjan(int u) {
	int sum = 0;
	size[u] = 1;
	low[u] = dfn[u] = ++time;
	for (int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		if (dfn[v] == 0) {
			Tarjan(v);
			size[u] += size[v];
			if (low[v] >= dfn[u]) {
				ans[u] += size[v] * sum;
				sum += size[v];
			}
			low[u] = min(low[u], low[v]);
		} else {
			low[u] = min(low[u], dfn[v]);
		}
	}
	ans[u] += n - 1;
	ans[u] += (n - sum - 1) * sum;
}

int main() {
	input();
	for (int i = 1; i <= n; ++i) {
		if (dfn[i] == 0) {
			Tarjan(i);
		}
	}
	for (int i = 1; i <= n; ++i) {
		printf("%d\n", ans[i] * 2);
	}
	return 0;
}

BLO

2025/1/19 20:59
加载中...