yukicoder : No.3200 Sinking Islands

これもかなり定番。
https://yukicoder.me/problems/no/3200

問題

N点M辺のグラフが与えられる。
以後辺を1つ消すクエリが与えられるので、そのつど互いに連結しない2頂点対の数を答えよ。

解法

典型問題で、Union-Findを使いクエリを逆順に処理して行けばよい。

int N,M;
int U[202020],V[202020];
int Q;
int vis[202020];
int order[202020];
ll ret[202020];

template<int um> class UF {
	public:
	vector<int> par,rank,cnt,G[um];
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit(int num=um) {int i; FOR(i,num) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<202020> uf;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>U[i]>>V[i];
		U[i]--,V[i]--;
	}
	cin>>Q;
	FOR(i,Q) {
		cin>>x;
		vis[x-1]=1;
		order[i]=x-1;
	}
	ll num=0;
	FOR(i,M) if(vis[i]==0) {
		if(uf[U[i]]!=uf[V[i]]) {
			num+=1LL*uf.count(U[i])*uf.count(V[i]);
			uf(U[i],V[i]);
		}
	}
	for(i=Q-1;i>=0;i--) {
		ret[i]=1LL*N*(N-1)/2-num;
		x=order[i];
		if(uf[U[x]]!=uf[V[x]]) {
			num+=1LL*uf.count(U[x])*uf.count(V[x]);
			uf(U[x],V[x]);
		}
	}
	FOR(i,Q) cout<<ret[i]<<endl;
}

まとめ

典型っぽいので★2.5でもいい気はするけどね。