帶權(quán)并查集就是除了維護(hù)一個(gè)fa數(shù)組以外，維護(hù)一個(gè)rank數(shù)組，有兩層含義，一個(gè)是路徑壓縮時(shí)邊的權(quán)值，，再一個(gè)是當(dāng)前點(diǎn)與根節(jié)點(diǎn)的相對(duì)關(guān)系。這個(gè)題很明顯考察的是

根節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)的一種相對(duì)關(guān)系，讓rank【x】 = 0 ，1，2表示A，B，C三個(gè)種類(lèi)的動(dòng)物，在剛開(kāi)始的時(shí)候，所有的動(dòng)物的rank值都是0，表示還沒(méi)有給他們安排關(guān)系，隨

著語(yǔ)句的輸入，1xy表示把x,y置為相同值，2xy表示rank【x】 + 1 = rank【y】，然而在這里并不是直接改變y的rank的值，而是改變y所在的根結(jié)點(diǎn)的rank值，因?yàn)橐坏﹛,y確

立了關(guān)系，和y在一個(gè)集合內(nèi)的動(dòng)物都與x建立了關(guān)系，這樣只有改變根節(jié)點(diǎn)的rank才能保證每一個(gè)動(dòng)物的rank都會(huì)被更新到，因?yàn)樵趚所在的集合和y所在的集合沒(méi)有建立關(guān)系

之前，x,y的關(guān)系可以是任意的。

如果輸入1xy，首先看x,y是否在一個(gè)集合內(nèi)，如果是那麼x,y之間是一種絕對(duì)的關(guān)系，可以通過(guò)rank【x】和rank【y】的大小來(lái)判斷語(yǔ)句的正確性，如果不是那麼x,y之間就沒(méi)有

確定的關(guān)系，那么這句話就是對(duì)的，修改rank【y】所在集合的根結(jié)點(diǎn)的rank值，

輸入2xy時(shí)和輸入1xy時(shí)同理。

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<map> #define N 100005 #define lc rt<<1 #define rc rt<<1|1 #define INF 0x3f3f3f3f using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn = 5e4 + 10;int n,k; int d,x,y; int fa[maxn]; int rank[maxn];int find(int x) {if(fa[x] == x)return x;int p = find(fa[x]);rank[x] = (rank[fa[x]] + rank[x])%3;return fa[x] = p; }int main() {//freopen("in","r",stdin);int cnt = 0;scanf("%d%d",&n,&k);for(int i = 0; i < n; ++i) fa[i] = i;memset(rank,0,sizeof(rank));for(int i = 0; i < k; ++i){scanf("%d%d%d",&d,&x,&y);if(x > n||y > n||(d == 2&&x == y)) {cnt++;continue;}int s1 = find(x),s2 = find(y);//求根節(jié)點(diǎn)if(d == 1){if(s1 == s2){if(rank[x] != rank[y]) cnt++;}else {rank[s2] = (rank[x] - rank[y] + 3)%3;//更新y的根結(jié)點(diǎn)，注意不要寫(xiě)錯(cuò)s2；fa[s2] = s1;//建立x集合與y集合的關(guān)系；}}else if(d == 2){if(s1 == s2) {if((rank[x] + 1)%3 != rank[y]) cnt++;}else {rank[s2] = (rank[x] + 1 - rank[y] + 3)%3;//同上fa[s2] = s1;}}//printf("%d %d\n",i,cnt); }printf("%d\n",cnt); }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Norlan/p/4888413.html

總結(jié)

以上是生活随笔為你收集整理的POJ1182--带权并查集的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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