洛谷 [P3496] BLO

割点

首先 tarjan 求割点,

对于不是割点的点, 答案是 2 * (n-1) 有序，所以要乘 2

对于是割点的点, 答案是删去该点后所有连通块的个数加上 n-1 在乘 2

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

#define ll long long

using namespace std;

const int MAXN = 1000005;

ll ans[MAXN];

int head[MAXN], n, m, nume, dfn[MAXN], low[MAXN], ind, siz[MAXN];

bool f[MAXN];

struct edge{

	int to, nxt;

}e[MAXN];

void adde(int from, int to) {

	e[++nume].to = to;

	e[nume].nxt = head[from];

	head[from] = nume;

}

int init() {

	int rv = 0, fh = 1;

	char c = getchar();

	while(c < '0' || c > '9') {

		if(c == '-') fh = -1;

		c = getchar();

	}

	while(c >= '0' && c <= '9') {

		rv = (rv<<1) + (rv<<3) + c - '0';

		c = getchar();

	}

	return fh * rv;

}

void tarjan(int u) {

	dfn[u] = low[u] = ++ind;siz[u] = 1;

	int flag = 0, sum = 0;

	for(int i = head[u]; i; i = e[i].nxt) {

		int v = e[i].to;

		if(!dfn[v]) {

			tarjan(v);

			siz[u] += siz[v];

			low[u] = min(low[u], low[v]);

			if(low[v] >= dfn[u]) {

				flag++;

				ans[u] += (ll) siz[v] * (n - siz[v]);

				sum += siz[v];

				if(u != 1 || flag > 1) {

					f[u] = 1;

				}

			}

		}else low[u] = min(low[u], dfn[v]);

	}

	if(f[u]) ans[u] += (ll) (n - sum - 1) * (sum + 1) + n - 1;

	else ans[u] = 2 * n - 2;

}

int main() {

	n = init(); m = init();

	for(int i = 1; i <= m; i++) {

		int u = init(), v = init();

		if(u == v) continue;

		adde(u, v); adde(v, u);

	}

	tarjan(1);

	for(int i = 1; i <= n; i++) printf("%lld\n", ans[i]);

	return 0;

}

巴特西

洛谷 [P3496] BLO

割点

最新文章

热门文章