啟發(fā)式合并 [USACO22DEC] Making Friends P
題意
\(N\) 牛 \(M\) 關(guān)系，按照編號從小到大，牛依次離開，每一頭牛離開時它認(rèn)識的牛會互相認(rèn)識，求最后新增了多少朋友關(guān)系。
\(N,M\le 2\times 10^5\)
解法
我們將操作看成每個點(diǎn)邊集合的合并，嘗試使用啟發(fā)式合并解決問題。
但是直接做又發(fā)現(xiàn)沒有辦法搞，因?yàn)槲覀儠阒睾芏啵谑俏覀冞x擇僅僅連一條邊，從編號小到編號大。
這個樣子我們并不會錯過什么，因?yàn)檫吋暮喜⑹菑男」?jié)點(diǎn)開始的，我們貪心選擇相連的最小節(jié)點(diǎn)合并一定是不劣的，所以就做完了，復(fù)雜度就是標(biāo)準(zhǔn)的啟發(fā)式合并。
代碼↓
點(diǎn)擊查看代碼
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MN=1e6+116;
int n, m, ans=0; set <int> G[MN];
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n>>m; ans=-m;
for(int i=1; i<=m; ++i){
int u, v; cin>>u>>v;
G[min(u,v)].insert(max(u,v));
}
for(int i=1; i<=n; ++i){
if(G[i].empty()) continue;
ans+=G[i].size();
int u=*G[i].begin();//最小的辣個
G[i].erase(G[i].begin());
if(G[u].size()<G[i].size()) swap(G[u],G[i]);
for(auto v:G[i]) G[u].insert(v);
}
cout<<ans<<'\n';
return 0;
}
浙公網(wǎng)安備 33010602011771號