Tarjan 求问
查看原帖
Tarjan 求问
526017
COsm0s楼主2024/2/26 21:38
const int N = 1e6 + 5;
int n, m, rt = 1;
vector<int> vec[N];
void add(int u, int v) {
	vec[u].emplace_back(v);
}
int dfn[N], low[N], siz[N], ans[N], tot;
void Tarjan(int u) {
	dfn[u] = low[u] = ++ tot;
	siz[u] = 1;
	for (auto v : vec[u]) {
		if (dfn[v]) {
			low[u] = min(low[u], dfn[v]);
			continue;
		}
		Tarjan(v);
		siz[u] += siz[v];
		low[u] = min(low[u], low[v]);
		if (low[v] >= dfn[u]) {
//			if(u == 1) cout << v << ' ' << siz[v] * (n - siz[v] - 1) << '\n';
			ans[u] += siz[v] * (n - siz[v] - 1);
		}
	}
	ans[u] += n - 1;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	cin >> n >> m;
	REP(i, 1, m) {
		int a, b;
		cin >> a >> b;
		add(a, b), add(b, a);
	}
	Tarjan(1);
	REP(i, 1, n) cout << ans[i] * 2 << '\n';
	return 0;
}

本题中为什么这样的写法会导致根节点的 ans1ans_1 会出错呢,求问/kk。

2024/2/26 21:38
加载中...