ABC 120 D - Decayed Bridges - ykmakuのブログ

問題

解法

連結無向グラフから枝を取り除いていったときに非連結な頂点のペアの個数を答える問題.

一般に，グラフから枝や頂点を取り除くという操作は難しいです.
逆に枝や頂点を追加するという操作は比較的かんたんです.

今回の場合，枝を後ろから順に見ていくことを考えます.
後ろから見るということは枝を追加していくということに対応します.
枝 $(x,y)$ が追加されるとき， $x$ と $y$ が同じ連結成分に含まれていないならば， $x$ $\left(y\right)$ を含む連結成分の頂点の個数を $size(x)$ ( $size(y)$ )とすれば，枝 $(x,y)$ 追加されたとき不便さは $size(x)\times size(y)$ だけ解消されます.

無向グラフの連結成分を扱うにはUnion-Findが便利です.

#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;

#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;


struct union_find{
  vector<int> par,r,size;

  union_find(int n) : par(n),r(n),size(n){init(n);}

  void init(int n){
    for(int i = 0; i < n; i++) par[i] = i;
    for(int i = 0; i < n; i++) r[i] = 0;
    for(int i = 0; i < n; i++) size[i] = 1;
  }

  int find(int x){
    if(par[x] == x) return x;
    else return find(par[x]);
  }

  void unite(int x,int y){
    x = find(x);
    y = find(y);
    if(x == y) return;
    if(r[x] < r[y]){
      par[x] = y;
      size[y] += size[x];
    }else{
      par[y] = x;
      size[x] += size[y];
      if(r[x] == r[y]) r[x]++;
    }
  }

  bool same(int x,int y){
    return find(x) == find(y);
  }
};

int main()
{
	ll n,m;
	cin>>n>>m;
	vector<pair<int,int> > edge(m);
	for(int i = 0; i < m; i++){
		int a,b;
		cin>>a>>b;
		a--;b--;
		edge[i] = pair<int,int>(a,b);
	}

	reverse(all(edge));
	vector<ll> ans(m+1);
	ans[0] = (n-1)*n/2;
	union_find uf(n);
	ll cnt = 0;
	for(int i = 0; i < m; i++){
		int a = edge[i].first,b=edge[i].second;
		if(uf.same(a,b)) ans[i+1] = ans[i];
		else{
			cnt += uf.size[uf.find(a)]*uf.size[uf.find(b)];
			uf.unite(a,b);
			ans[i+1] = (n-1)*n/2-cnt;
		}
	}
	reverse(all(ans));
	for(int i = 1; i < ans.size(); i++){
		cout << ans[i] << endl;
	}

	return 0;
}