bzoj 1123: [POI2008]BLO（Trajan求割点）-白红宇

bzoj 1123: [POI2008]BLO（Trajan求割点）

阅读量：2143 次

发布时间：2019-04-30

本文共 1160 字，大约阅读时间需要 3 分钟。

Time Limit: 10 Sec

Memory Limit: 162 MB

Submit: 1468

Solved: 678

[ ][ ][ ]

Description

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

Input

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

Output

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

Sample Input

5 5

1 2

2 3

1 3

3 4

4 5

Sample Output

被删掉的点要算进答案，并且(u, v)和(v, u)属于不同点对

模板题

#include
   
    #include
    
     #include
     
      using namespace std;#define LL long longvector
      
        G[100005];int n, cnt, cut[100005], time[100005], low[100005], id[100005], vis[100005];LL ans[100005];void Tarjan(int u, int p){	int i, v, temp, size, child = 0;	vis[u] = 1, low[u] = time[u] = ++cnt;	temp = cnt, size = 0;	for(i=0;i
       
        1 || p!=0 && low[v]>=time[u])			{				cut[u] = 1;				ans[u] += (LL)(cnt-temp)*(n-1-cnt+temp);				size += cnt-temp;			}			temp = cnt;		}		else			low[u] = min(low[u], time[v]);	}	if(cut[u])		ans[u] += (LL)size*(n-1-size);}int main(void){	int m, i, x, y;	scanf("%d%d", &n, &m);	for(i=1;i<=m;i++)	{		scanf("%d%d", &x, &y);		G[x].push_back(y);		G[y].push_back(x);	}	for(i=1;i<=n;i++)		ans[i] = (n-1)*2;	Tarjan(1, 0);	for(i=1;i<=n;i++)		printf("%lld\n", ans[i]);	return 0;}