关于割点的问题
查看原帖
关于割点的问题
1219662
wwxxbb楼主2024/11/28 19:00

为什么我判割点的时候像模板题一样写就过不了。

#include <bits/stdc++.h>
using namespace std;

const int N = 100010, M = 500010;

int n, m;
int idx, h[N];
struct Edge {int to, ne;} e[M << 1];
void add(int u, int v) {e[idx] = {v, h[u]}, h[u] = idx ++;}

int dfn[N], low[N], tot, siz[N];
bitset<N> iscut;
long long ans[N];
void tarjan(int u, int fa) {
	dfn[u] = low[u] = ++ tot;
	siz[u] = 1;
	int child = 0, sum = 0;
	for (int i = h[u]; ~i; i = e[i].ne) {
		int v = e[i].to;
		if (v == fa) continue;
		if (!dfn[v]) {
			++ child;
			tarjan(v, u);
			siz[u] += siz[v];
			low[u] = min(low[u], low[v]);
			if (/*!iscut[u] && u != fa &&*/ low[v] >= dfn[u]) {
                // 这个地方!!!
				iscut[u] = 1;
				sum += siz[v];
				ans[u] += 1ll * siz[v] * (n - siz[v]);
			}
		}
		else low[u] = min(low[u], dfn[v]);
	}
	if (iscut[u] || (!iscut[u] && u == fa && child >= 2)) {	
		iscut[u] = 1;
		ans[u] += 1ll * (sum + 1) * (n - (sum + 1)) + n - 1;
	}
	else ans[u] = n - 1 << 1;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	memset(h, -1, sizeof h);
	cin >> n >> m;
	for (int i = 1, u, v; i <= m; i ++) {
		cin >> u >> v;
		add(u, v), add(v, u);
	}
	tarjan(1, 1);
	for (int i = 1; i <= n; i ++)
		cout << ans[i] << '\n';
	return 0;
}

为什么上面注释的代码去掉就可以过,我看题解都是这么写的,但都没有说。

我还发现下面这组数据我过不了(就是根是割点的情况):

5 4
1 2
1 3
1 4
1 5

输出:

20
8
8
8
8

我上面代码(加上注释)输出的是:

8
8
8
8
8

不知道哪个地方出了问题。

蒟蒻求解qwq

2024/11/28 19:00
加载中...