2022 December Contest
T2 Making Friends
答案是最后的总边数减去 \(m\)。
连边常用的优化方法是两两之间互相连边只连到一个点上去。这边尝试连到最小的点上。
考虑正确性。假设 \(i\) 删掉了，那么他现在相邻的点数要加入答案。设它相邻的最小点为 \(j\)。把 \(i\) 相邻的都连到 \(j\)，\(j\) 下一次就可以同样传递（到编号大一点的），每个点都会传递到。
两个 set 合并的时候用启发式合并即可。
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5+5;
int n,m;
set<int> st[N];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for (int i=1; i<=m; i++){
int a,b;
cin>>a>>b;
st[min(a,b)].insert(max(a,b));
}
ll ans=-m;
for (int i=1; i<=n; i++){
ans+=(ll)st[i].size();
if (st[i].size()){
auto j=*st[i].begin();
st[i].erase(j);
if ((int)st[i].size()>(int)st[j].size()){
swap(st[i],st[j]);
}
for (auto u : st[i]){
st[j].insert(u);
}
}
}
cout<<ans<<endl;
return 0;
}