atcoder abc120 D - Decayed Bridges

AtCoder UnionFind

問題

D - Decayed Bridges

解法

ぱっと見でUnionFindだろうなと思ったが、少々工夫が必要だった。

  • 橋の削除操作は難しいため、逆順から橋を追加していく操作を考える
  • 橋が一つもない状態の不便さは $ {}_n C_2 $ で求まる
  • 橋を追加後の不便さは、次で求まる
    • 追加前の不便さ - 追加した頂点a[i]連結成分のサイズ x 追加した頂点b[i]連結成分のサイズ
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
using ll = long long;

struct UnionFind {
  vector<ll> d;
  UnionFind(ll n=0): d(n, -1) {} // -1で初期化
  ll root(ll x) {
    if (d[x] < 0) return x; // 負の場合はroot
    return d[x] = root(d[x]); // 経路圧縮
  }
  bool unite(ll x, ll y) {
    x = root(x); y = root(y);
    if (x == y) return false;
    if (d[x] > d[y]) swap(x,y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(ll x, ll y) { return root(x) == root(y); }
  ll size(ll x) { return -d[root(x)]; /* 木の深さ */ }
};

ll n,m;
vector<ll> a,b;

void solve() {
  vector<ll> ans(m); // 不便さ
  ans[0]=n*(n-1)/2; // 橋がどこにも無い状態の不便さ

  // 橋を逆順から追加していく操作で考えるためreverse
  reverse(a.begin(),a.end());
  reverse(b.begin(),b.end());

  UnionFind uf(n);

  REP(i,m-1) {
    // 連結済みの場合
    if (uf.same(a[i],b[i])) { ans[i+1] = ans[i]; continue; }

    ans[i+1] = ans[i] - uf.size(a[i]) * uf.size(b[i]);
    uf.unite(a[i],b[i]);
  }

  reverse(ans.begin(),ans.end()); // ansが逆順の操作で格納されているためreverse
  REP(i,m) cout << ans[i] << endl;

  return;
}

int main() {
  cin >> n >> m;
  a.resize(m); b.resize(m);

  REP(i,m) {
    cin >> a[i] >> b[i];
    a[i]--; b[i]--; // 0-indexed
  }

  solve();
  return 0;
}