【bzoj1123】[POI2008]BLO DFS树

题目描述

Byteotia城市有n个 towns m条双向roads. 每条 road 连接 两个不同的 towns ,没有重复的road. 所有towns连通。

输入

输入n<=100000 m<=500000及m条边

输出

输出n个数,代表如果把第i个点去掉,将有多少对点不能互通。

样例输入

5 5
1 2
2 3
1 3
3 4
4 5

样例输出

8
8
16
14
8


题解

DFS树

Tarjan求点双太暴力了。。。还是选择一个优雅一点的做法——DFS树

考虑在DFS的过程中计算删除每个点的答案。

由于DFS树没有横叉边,只有返祖边,因此一个点把整棵树分为一些部分(下面简称“块”):父树部分、子树部分。

考虑割掉一个点,什么样的“块”是连通的:由于没有横叉边,因此只有可能是子树“块”与父树“块”相连,然后它们可以连通。即只有所有与父树相连的连通块是相互连通的。

那么就相当于把能够连通的“块”看作1个“块”,于是任意两个不同“块”中的点都是不连通的。

于是就可以将总的点对数减去在同一“块”(这里的“块”指合并以后的)得到答案:$ANS_i=C_n^2-\sum C_{si}^2$。

最后答案需要乘以2,因为题目中的点对是有序点对,需要计算2次。

#include <cstdio>
#include <algorithm>
#define N 100010
#define M 1000010
#define C(n) (((ll)(n) * (n - 1)) >> 1)
using namespace std;
typedef long long ll;
struct edge
{
int to , next;
}a[M];
int n , head[N] , cnt , deep[N] , low[N] , si[N] , num[N];
ll sum[N];
inline void add(int x , int y)
{
a[++cnt].to = y , a[cnt].next = head[x] , head[x] = cnt;
}
void dfs(int x , int fa)
{
int i , ts = 0;
si[x] = 1;
for(i = head[x] ; i ; i = a[i].next)
{
if(a[i].to == fa) continue;
if(!deep[a[i].to])
{
deep[a[i].to] = low[a[i].to] = deep[x] + 1 , dfs(a[i].to , x) , low[x] = min(low[x] , low[a[i].to]) , si[x] += si[a[i].to];
if(low[a[i].to] < deep[x]) ts += si[a[i].to];
else sum[x] += C(si[a[i].to]);
}
else low[x] = min(low[x] , deep[a[i].to]);
}
sum[x] += C(ts + n - si[x]);
}
int main()
{
int m , x , y , i;
scanf("%d%d" , &n , &m);
ll s = C(n);
for(i = 1 ; i <= m ; i ++ ) scanf("%d%d" , &x , &y) , add(x , y) , add(y , x);
deep[1] = 1 , dfs(1 , 0);
for(i = 1 ; i <= n ; i ++ ) printf("%lld\n" , (s - sum[i]) << 1);
return 0;
}
上一篇:C# 页面向controller中跳转匹配方法的时候,当controller中有两个重载方法时候,不发生跳转


下一篇:Spring MVC中 controller方法返回值