【題目來(lái)源】
http://oj.ecustacm.cn/problem.php?id=1850
http://oj.ecustacm.cn/viewnews.php?id=1023
【題目描述】
給定 n 個(gè)小球，編號(hào)為 1-n，給定 m 個(gè)籃子，編號(hào)為 1-m。
每個(gè)球只允許放入樣例給定的編號(hào)為 Ai 或者 Bi 的兩個(gè)籃子中的 1 個(gè)。
每個(gè)球必須放入某個(gè)籃子。
如果籃子中球的數(shù)量為奇數(shù)，則該籃子是特殊的。
計(jì)算特殊的籃子最少有多少個(gè)。
【輸入格式】
第一行為兩個(gè)正整數(shù) n 和 m，1≤n,m≤200000。表示 n 個(gè)小球，m 個(gè)籃子。
接下來(lái) n 行，每行兩個(gè)數(shù)字 Ai，Bi，表示第 i 個(gè)球可以放入 Ai 或者 Bi 編號(hào)的籃子。
1≤Ai,Bi≤m，Ai≠Bi。
【輸出格式】
輸出一個(gè)數(shù)字表示答案。
【輸入樣例】
4 3
1 2
2 3
1 3
1 2
【輸入樣例】
0
【算法分析】
◆ 異質(zhì)圖
本題本質(zhì)上是異質(zhì)圖問(wèn)題。異質(zhì)圖是一種具有多種節(jié)點(diǎn)類(lèi)型或多種邊類(lèi)型的圖數(shù)據(jù)結(jié)構(gòu)，用于刻畫(huà)復(fù)雜異質(zhì)對(duì)象及其交互，具有豐富的語(yǔ)義信息。
本題異質(zhì)圖構(gòu)建的依據(jù)是：將某球放入某個(gè)籃子，則此球與籃子之間就有連線，否則就沒(méi)有連線。
依據(jù)本題樣例，將第 i 個(gè)球放入 Ai 或者 Bi 編號(hào)的籃子中，可得出如下的異質(zhì)圖。其中，從某個(gè)小球引出的兩條線，分別以一實(shí)線和一虛線表示（切記：根據(jù)題意，從某個(gè)小球引出的一實(shí)線和一虛線不能共存，只能取其一。此處都畫(huà)出，只是為了示意）。
根據(jù)“從某個(gè)小球引出的一實(shí)線和一虛線不能共存，只能取其一”的約束，可得出符合本題題意的一種異質(zhì)圖。如下所示。
可見(jiàn)，若依據(jù)圖論的觀點(diǎn)，上面的示意圖由若干個(gè)連通子圖構(gòu)成。那么問(wèn)題來(lái)了。一個(gè)連通子圖中，最少有多少個(gè)是特殊籃子？顯然，如果連通子圖中的線條是偶數(shù)，則特殊籃子最少為0個(gè)；如果連通子圖中的線條是奇數(shù)，則特殊籃子最少為1個(gè)。
為了求解連通子圖中的特殊籃子數(shù)，首選并查集。因?yàn)椋?/span>并查集是求解判定連通子圖相關(guān)問(wèn)題的得力工具。
◆ 并查集
并查集模板：https://blog.csdn.net/hnjzsyjyj/article/details/120147618
int find(int x) {
if(x!=pre[x]) pre[x]=find(pre[x]);
return pre[x];
}
void merge(int x,int y) {
int p=find(x);
int q=find(y);
if(p!=q) pre[p]=q;
}并查集模板題之求團(tuán)伙數(shù)量：https://blog.csdn.net/hnjzsyjyj/article/details/120120591
#include <bits/stdc++.h>
using namespace std;
const int maxn=100;
int pre[maxn];
int find(int x) { //尋找x的父節(jié)點(diǎn)
if(x!=pre[x]) pre[x]=find(pre[x]);
return pre[x];
}
void merge(int x,int y) { //合并兩個(gè)子集
int p=find(x);
int q=find(y);
if(p!=q) pre[p]=q;
}
int main() {
int u,v,p,q;
int ans;
cin>>u>>v; //頂點(diǎn)數(shù)、邊數(shù)
for(int i=1; i<=u; i++) //初始時(shí)每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)都是自己
pre[i]=i;
for(int i=1; i<=v; i++) {
cin>>p>>q; //邊的兩個(gè)頂點(diǎn)序號(hào)
merge(p,q);
}
for(int i=1; i<=u; i++) {
if(find(i)==i) ans++; //計(jì)算連通子圖個(gè)數(shù)，也就是得出幾個(gè)團(tuán)伙
}
cout<<ans<<endl;
return 0;
}
/*
in:
10 9
1 2
3 4
5 2
4 6
2 6
8 7
9 7
1 6
2 4
out:
3
*/
【算法代碼】文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-665800.html
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int cnt[maxn],pre[maxn],st[maxn];
int n,m;
int find(int x) {
if(x!=pre[x]) pre[x]=find(pre[x]);
return pre[x];
}
void merge(int x,int y) {
int p=find(x);
int q=find(y);
if(p!=q) {
pre[p]=q;
cnt[q]+=cnt[p]+1;
} else cnt[p]++;
}
int main() {
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++) pre[i]=i;
for(int i=1;i<=n;i++) {
int x,y;
scanf("%d %d",&x,&y);
merge(x,y);
}
int ans=0;
for(int i=1;i<=m;i++) {
int x=find(i);
if(!st[x]) {
if(cnt[x] & 1) ans++;
st[x]=1;
}
}
printf("%d",ans);
return 0;
}
/*
in:
4 3
1 2
2 3
1 3
1 2
out:
0
*/
【參考文獻(xiàn)】
https://blog.csdn.net/weixin_43914593/article/details/131800622
https://blog.csdn.net/hnjzsyjyj/article/details/120120591
https://blog.csdn.net/hnjzsyjyj/article/details/120147618
?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-665800.html
到了這里，關(guān)于羅勇軍 →《算法競(jìng)賽·快沖300題》每日一題：“小球配對(duì)” ← 并查集的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
