363. B城

发表于 2024-10-02 更新于 2024-10-05 分类于 acwing 阅读次数： Waline：本文字数： 311 阅读时长 ≈ 1 分钟

考点

割点

题解

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 50, maxm = 5e5 + 50;
int n, m;
int tot, head[maxn], nxt[maxm << 1], ver[maxm << 1];
int num, dfn[maxn], low[maxn], sz[maxn];
long long ans[maxn];
bool cut[maxn];

void add(int x, int y) { ver[++tot] = y, nxt[tot] = head[x], head[x] = tot; }

void tarjan(int x) {
  dfn[x] = low[x] = ++num;
  sz[x] = 1;
  int sum = 0, flag = 0;
  for (int i = head[x]; i; i = nxt[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]) {
        ++flag;
        ans[x] += 1ll * sz[y] * (n - sz[y]);
        sum += sz[y];
        if (x != 1 || flag > 1) cut[x] = 1;
      }
    } else {
      // 非树边
      low[x] = min(low[x], dfn[y]);
    }
  }
  if (cut[x])
    ans[x] += (n - 1) + 1ll * (n - 1 - sum) * (sum + 1);
  else
    ans[x] = 2 * (n - 1);
}

int main() {
  cin >> n >> m;
  for (int x, y, i = 1; i <= m; ++i) {
    cin >> x >> y;
    add(x, y), add(y, x);
  }
  tarjan(1);
  for (int i = 1; i <= n; ++i) cout << ans[i] << endl;
  return 0;
}