深度优先遍历这幅图。
设
s
i
z
[
x
]
siz[x]
siz[x] 表示在搜索树中,以
x
x
x 为根的子树的大小。
注意不连通的关系是双向的,所以
(
x
,
y
)
,
(
y
,
x
)
(x,y),(y,x)
(x,y),(y,x)算两次。
对于当前点
x
x
x,有两种情况:
#include<cstdio>
#include<iostream>
using std::min;
const int N = 1e5 + 5,M = 5e5 + 5;
struct edge {
int next,to;
}a[M << 1];
int head[N],n,m,a_size = 1,root;
inline void add(int u,int v) {
a[++a_size] = (edge){head[u],v};
head[u] = a_size;
a[++a_size] = (edge){head[v],u};
head[v] = a_size;
}
int dfn[N],low[N],siz[N],num = 0;
long long ans[N]; bool cut[N];
void tarjan(int x) {
dfn[x] = low[x] = ++num;
int flag = 0,sum = 0; siz[x] = 1;
for(int i = head[x]; i; i = a[i].next) {
int y = a[i].to;
if(!dfn[y]) {
tarjan(y); siz[x] += siz[y];
low[x] = min(low[x],low[y]);
if(low[y] >= dfn[x]) {
flag++; sum += siz[y];
ans[x] += 1ll * siz[y] * (n - siz[y]);
if(x != root || flag > 1) cut[x] = true;
}
}
else low[x] = min(low[x],dfn[y]);
}
if(cut[x]) ans[x] += 1ll * (n - 1 - sum) * (1 + sum) + n - 1;
else ans[x] = (n - 1) << 1;
}
inline int read() {
int x = 0,flag = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')flag = -1;ch = getchar();}
while(ch >='0' && ch <='9'){x = (x << 3) + (x << 1) + ch - 48;ch = getchar();}
return x * flag;
}
int main() {
n = read(),m = read();
for(int i = 1; i <= m; i++) {
int u = read(),v = read();
add(u,v);
}
for(int i = 1; i <= n; i++) {
if(dfn[i]) continue;
root = i; tarjan(root);
}
for(int i = 1; i <= n; i++) printf("%lld\n",ans[i]);
return 0;
}