C++14(g++5.4) 解法, 执行用时: 228ms, 内存消耗: 18632K, 提交时间: 2019-09-06 09:31:02

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
const int M=5e5+10;

int head[N],ver[2*M],nex[2*M],tot=1;
inline void add(int x,int y) {
    ver[++tot]=y;
    nex[tot]=head[x];
    head[x]=tot;
}

int dfn[N],low[N],sz[N],num;
ll ans[N];
int n,m;
void tarjan(int x) {
    dfn[x]=low[x]=++num;
    sz[x]=1;
    int sum=0;
    for(int i=head[x]; i; i=nex[i]) {
        int y=ver[i];
        if(!dfn[y]) {
            tarjan(y);
            sz[x]+=sz[y];
            low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x])
                ans[x]+=(ll)sz[y]*(n-sz[y]);
            else if(low[y]<dfn[x])
                sum+=sz[y];
        } else
            low[x]=min(low[x],dfn[y]);
    }
    ans[x]+=(n-1)+((ll)n-sz[x]+sum)*(sz[x]-sum);
}

int main() {
    scanf("%d%d",&n,&m);
    for(int i=0; i<m; ++i) {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    tarjan(1);
    for(int i=1; i<=n; ++i)
        printf("%lld\n",ans[i]);
    return 0;
}

C++ 解法, 执行用时: 401ms, 内存消耗: 25124K, 提交时间: 2022-07-23 10:30:44

#include<bits/stdc++.h>
using namespace std;
long long dfn[100001],low[100001],vis[100001],tim,ans[100001],sz[100001],u,v,n,m;
vector<long long> G[200001];
void tarjan(long long x){
	long long now=0;
	dfn[x]=low[x]=++tim;
	sz[x]=1;
	for(long long i=0;i<G[x].size();i++){
		long long v=G[x][i];
		if(!dfn[v]){
			tarjan(v);
			low[x]=min(low[x],low[v]);
			sz[x]+=sz[v];
			if(dfn[x]<=low[v])ans[x]+=now*sz[v],now+=sz[v];
		}
		else low[x]=min(low[x],dfn[v]);
	}
	ans[x]+=now*(n-now-1);
}
int main(){
	cin>>n>>m;
	for(long long i=1;i<=m;i++)cin>>u>>v,G[u].push_back(v),G[v].push_back(u);
	for(long long i=1;i<=n;i++)if(!dfn[i])tarjan(i);
	for(long long i=1;i<=n;i++)cout<<(ans[i]+n-1)*2<<"\n";
	return 0;
}