【POI 2008, BLO】Cut Point

题目描述

有n个点mA graph of edge undirected connected graphs,保证没有重边和自环.对于每个点,The output removes all edges from this point,How many point pairs cannot be connected to each other.The point pairs here are in order,也就是(u,v)和(v,u)need to be counted twice.

输入格式

第一行包含两个数n,m(1≤n≤105,1≤m≤5×105).

接下来m行,每行两个整数u,v表示一条无向边.

输出格式

n行,每行一个整数,表示答案.

样例输入

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

样例输出

8
8
16
14
8

思路

对于每一个点,如果这个点是割点,Then after deleting him, it has no effect on this picture,So the contribution of this point is2*(n-1),If this point is a cut point,Then multiply all the connected blocks that delete it,Pay attention to the process of seeking that cut edge,That is, if the point connected to this point does not have a leaseback edge, it is a cut point,下面看代码吧

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 1e5+10;
vector<pair<int,int> > e[N];
int n,m,dfn[N],ins[N],low[N],idx,sz[N];
long long ans[N];
void dfs(int u,int id){
    
	dfn[u] = low[u] = ++idx;
	ins[u] = true;
	sz[u] = 1;
	ans[u] = n-1;
	int cut = n-1;
	for(auto pi : e[u]){
    
		int v = pi.first,idd = pi.second;
		if(!dfn[v]){
    
			dfs(v,idd);
			sz[u] += sz[v];
			low[u] = min(low[u],low[v]);
			if(low[v] >= dfn[u]){
    
				ans[u] += 1ll*(n-sz[v])*sz[v];
				cut -= sz[v];
			}
		}
		else if(idd != id){
    
			low[u] = min(low[u],dfn[v]);
		}
	}
	ans[u] += 1ll*(cut)*(n-cut);
}
int main(){
    
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
    
		int a,b;
		scanf("%d%d",&a,&b);
		e[a].pb({
    b,i});e[b].pb({
    a,i});
	}
	dfs(1,-1);
	for(int i=1;i<=n;i++) printf("%lld\n",ans[i]);
	return 0;
}