題目鏈接：點擊查看

題目大意：給出兩個數(shù)組 a[ i ]? 和 b[ i?]，每次可以從 a[ i ] 和 b[ i ] 中選擇一個數(shù)，求最后選出的數(shù)中，不同的數(shù)的個數(shù)最多

題目分析：比賽時用網(wǎng)絡流亂搞水過去了，但是現(xiàn)在都不知道為什么那樣建圖能過

正解是并查集，將每對 a[ i ] 和 b[ i ] 視為一條邊后，n 條邊連接之后，會出現(xiàn)數(shù)個連通塊，對于每個連通塊我們分兩種情況討論：

連通塊是個樹：有 n 個點和 n - 1 條邊，因為每條邊最多選一個點，所以 n - 1 條邊最多只能選 n - 1 個點

連通塊存在至少一個環(huán)：那么此時 n 個點的話至少有 n 條邊了，肯定存在一種方法可以將連通塊中的所有點都選一遍

所以實現(xiàn)的話，可以用帶權并查集，維護父節(jié)點的同時順便維護一個布爾變量 circle ，代表當前的連通塊內(nèi)是否有環(huán)，數(shù)據(jù)較大需要離散化，我是?map 離散化，因為用 map 的話可以在線離散化

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;int f[N],cnt;bool circle[N];unordered_map<int,int>mp;int find(int x) {return f[x]==x?x:f[x]=find(f[x]); }void merge(int x,int y) {int xx=find(x),yy=find(y);if(xx!=yy){f[xx]=yy;circle[yy]|=circle[xx];}elsecircle[xx]=true; }void init() {mp.clear();cnt=0;for(int i=0;i<N;i++){f[i]=i;circle[i]=false;} }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;int kase=0;while(w--){init();int n;scanf("%d",&n);for(int i=1;i<=n;i++){int x,y;scanf("%d%d",&x,&y);if(!mp[x])mp[x]=++cnt;if(!mp[y])mp[y]=++cnt;merge(mp[x],mp[y]);}int ans=cnt;for(int i=1;i<=cnt;i++)if(f[i]==i&&!circle[i])ans--;printf("Case #%d: %d\n",++kase,ans);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的牛客多校8 - Interesting Computer Game(并查集)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。