并查集好題 P6279 Favorite Colors G
這是一道極為有趣的題目，尤其是當我對著一個假的方法寫了好久的時候。
加上這個題我感興趣的正解寫的不太好，搞得我沒太懂，我想著寫一寫這個題的擴展并查集做法。
題意
\(N\) 頭牛，每個有喜歡的顏色，但是不告訴你這個顏色是什么。
我們有 \(M\) 對奶牛，\((a,b)\) 表示 \(b\) 仰慕 \(a\)。
奶牛 b 仰慕奶牛 a。有可能 a=b，此時一頭奶牛仰慕她自己。對于任意顏色 c，如果奶牛 x 和 y 都仰慕一頭喜歡顏色 c 的奶牛，那么 x 和 y 喜歡的顏色相同
都是 \(10^5\) 級別的。
怎么做
首先我想到了一個極其簡單的，卻顯然不對的做法。
使用一下并查集小姐姐。
我們反向建邊，枚舉每一個點，把它能到達的放到一塊，因為我們知道他們有一樣的仰慕對象。
最后我們從 1 開始枚舉到 n，只要這個聯通快沒有標記就打上。
最后求出聯通塊的統計肯定是正確的，但是求聯通快本身是有問題的。
結果自然是不對的。
因為我們這些點本身是擁有喜歡顏色的，兩個喜歡同樣顏色的可以作為載體讓一些本來八桿子打不著的點一樣。
就像樣例中，3,7 喜歡顏色是一樣的，所以才反映出了 1跟 4,5 所喜歡的一樣。
如果不明白說明你沒有讀對題！！！
這也是我做法假的原因之一。
兩個牛仰慕的牛并不一定是相同一頭牛，不同的牛也可以，前提是這被仰慕的兩頭牛所喜歡的顏色一樣。
不信讀題去。
究其根本是什么？？？ 我們并沒有利用并查集真正的去表示出喜歡這個抽象意義的邊，從而沒有真正表示出它了連通性。
所以我們使用一個擴展域并查集，表示這個點所真正喜歡的顏色。
練邊我們使用將仰慕者合并上被仰慕者喜歡的顏色這個點。
這樣我們不禁解決了這個問題，而且還順便解決了仰慕自己的問題。
但是明顯這個合并絕對不能像正常的合并走了，因為這兩個點在一個聯通快內的信息是隱含的，我們如果知道了兩個點所喜歡的顏色是一樣的，我們自然而然需要把它上邊的代表真正喜歡的點連起來，
所以我們每一次將小的做父親，醬紫我們合并時最后判斷兩個點是不是真的表示點，如果是，我們就把兩個代表真正喜歡顏色的點再連起來。
非常難繃，這個還是寫啟發式合并吧...
代碼
點擊查看代碼
#include <bits/stdc++.h>
#define getchar getchar_unlocked
using namespace std;
const int MN=1e6+116;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
x=x*10+ch-'0',ch=getchar();
return x*f;
}
int father[MN], n, m;
int find(int x){
if(father[x]!=x) father[x]=find(father[x]);
return father[x];
}
void merge(int x, int y){
x=find(x); y=find(y);
if(x==y) return;
if(x>y) swap(x,y);
father[y]=x;
if(x<=n&&y<=n) merge(x+n,y+n);
return;
}
int val[MN];
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
n=read(); m=read();
for(int i=1; i<=n*2+1; ++i) father[i]=i;
for(int i=1; i<=m; ++i){
int u, v; u=read(), v=read();
merge(u+n,v);
}
int cnt=0;
for(int i=1; i<=n; ++i){
int u=find(i);
if(!val[u]){
val[u]=++cnt;
}
cout<<val[u]<<'\n';
}
return 0;
}
浙公網安備 33010602011771號