백준 17398 통신망 분할

https://www.acmicpc.net/problem/17398

숭고한 공식 풀이는 여기서 보실 수 있습니다.

거꾸로 생각하면 쉬운 union find 문제입니다. 각 그룹에 포함되어 있는 노드의 개수를 저장하고 있다가, 두 노드가 연결될 때 집합이 새로 합쳐진다면 비용이 발생하게 됩니다.

처음에는 모두 연결되어 있는 상태이므로 쿼리를 오프라인 쿼리로 저장한 뒤 쿼리에 나타나지 않는 간선들은 비용 고려 없이 모두 연결해 두어야 합니다. (쿼리에 나타나는 간선들은 쿼리 순으로 계산하면서 비용을 고려해 주면 되겠죠?)

#include<bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int SZ=100005;
pii cnt[SZ];
int par[SZ];
int qry[SZ];
int vst[SZ];
ll ch[SZ];
int n;
int find(int x){
	if(x==par[x]) return x;
	return par[x]=find(par[x]);
}
void merge(int x, int y){
	x=find(x); y=find(y);
	if(x==y) return;
	par[y]=x;
	ch[x]+=ch[y];
	ch[y]=0;
}
int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL);
	int m,q; cin>>n>>m>>q;
	for(int i=1;i<=n;i++){
		par[i]=i;
		ch[i]=1LL;
	}
	for(int i=1;i<=m;i++) cin>>cnt[i].ff>>cnt[i].ss;
	ll ans=0;
	for(int i=q;i>=1;i--){
		cin>>qry[i];
		vst[qry[i]]=1;
	}
	for(int i=1;i<=m;i++){
		if(vst[i]==1) continue;
		merge(cnt[i].ff,cnt[i].ss);
	}
	for(int i=1;i<=q;i++){
		int p1=find(cnt[qry[i]].ff);
		int p2=find(cnt[qry[i]].ss);
		ans+=(p1==p2?0LL:ch[p1] * ch[p2]);
		merge(cnt[qry[i]].ff,cnt[qry[i]].ss);
	}
	cout<<ans;
	return 0;
}