bzoj1123
题目描述：给定n个城市，m条边，每条边连接两个不同的城市，没有重复的路，所有的城市相连。
输入格式：输入n<=100000 m<=500000 及 m 条边
输出格式：输出 n 个数，代表如果把第 i 个点去掉，将有多少对点不能互通。
输入样例： 5 5 1 2 2 3 1 3 3 4 4 5
输出样例： 8 8 16 14 8
解析：把每个点去掉，对答案的贡献就是每个被分割出的联通块的的大小之积 + (n - 1) 再乘2 关键在于如何快速求出每个联通块的大小。 可以在求割点时求出联通块的大小，最后答案累加即可。
代码如下:
#include<cstdio> #include<algorithm> #define ll long long using namespace std; const int maxn = 500005; int n, m, dfn[maxn], low[maxn], num, size[maxn]; int cnt, nxt[maxn * 2], hed[maxn * 2], to[maxn * 2]; ll ans[maxn]; int read(void) { char c; while (c = getchar(), c < '0' || c >'9'); int x = c - '0'; while (c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; return x; } void add(int x, int y) { nxt[++ cnt] = hed[x]; hed[x] = cnt; to[cnt] = y; } void tarjan(int u) { dfn[u] = low[u] = ++ num; size[u] = 1; int tot = 0; for (int i = hed[u]; i ; i = nxt[i]) { int v = to[i]; if (!dfn[v]) { tarjan(v); size[u] += size[v]; //统计子树大小 low[u] = min(low[u], low[v]); if (low[v] >= dfn[u]) { //如果这棵子树会被该点隔断，就统计答案 ans[u] += 1ll * tot * size[v]; tot += size[v]; } } else low[u] = min(low[u], dfn[v]); } ans[u] += 1ll * tot *(n - tot - 1); //其它所有点也是一个联通块 } int main() { n = read(); m = read(); for (int i = 1; i <= m; ++ i) { int x = read(), y = read(); add(x, y); add(y, x); } tarjan(1); for (int i = 1; i <= n; ++ i) printf("%lld\n", (ans[i] + n - 1) << 1); return 0; }转载于:https://www.cnblogs.com/Gaxc/p/9960211.html
相关资源：JAVA上百实例源码以及开源项目