【数据结构】带权并查集

时间 2021-02-18 标签 c++ spa code blog 递归 ci get string it class

对于一个物种（一类动物），若是存在它吃另外一个物种的关系，则让它的度数比另外一个物种多 \(1\) 。更严格地说，咱们记该物种为 a （并不是题意中的A），另外一个物种是 b，它们对应的度数为d[]，那么有 \(d[a]=d[b]+1\) 。如图：
递归

那么有了这样的规定，便有以下性质：ci

d[a]%3==d[b]%3 时，a，b是同一个物种。（操做1）
((d[a]-d[b])%3+3)%3==1 时，存在a吃b的关系。（这里屡次取模是为了保证左边的值只可能为 \(0,1,2\) ）（操做2）

从上面的性质能够看出，两个物种的关系与它们的模数（这题是 \(mod3\) ）余多少关系密切相关，所以接下来咱们也会着重考察两个数之间的这种关系。get

利用度数以及并查集，便可将各类动物之间的关系刻画清楚：string

这里依然对a，b进行讨论，为了方便，咱们记a的祖宗（根节点）为pa，b的祖宗（根节点）为pb。
it

若pa，pb不在同一个集合中：
就进行并查集的合并操做，让f[pa]=pb。能够看出，在合并的时候，仍然做为根节点的pb的度数仍是 \(0\)，可是pa的度数须要做出调整，才可以保证结点之间关系的正确。
① 若是a和b是同一个物种（操做1）：则有 d[pa]+d[a]=d[b]
② 若是a吃b（操做2）：则有 d[pa]+d[a]-d[b]=1（固然，右式等于 \(4,7,10\) 这样的数也是能够的，咱们只需找到 \(mod 3余1\)的数）
class
若pa，pb在同一个集合中：
相似于上面的讨论，
① 若是a和b是同一个物种（操做1）：若是 ((d[a]-d[b])%3+3)%3!=0，则矛盾，这句话即是谎话。
② 若是a吃b（操做2）：若是 ((d[a]-d[b])%3+3)%3!=1，则矛盾，这句话即是谎话。

综上，咱们的讨论将全部状况覆盖了。

路径压缩：
根据并查集的性质，若是不进行路径压缩，时间复杂度将会退化到 \(O(N)\) 。所以带权并查集也要进行路径压缩，那么主要问题就是解决如何维护d[]（度数）的问题：
归纳地说，就是在查询到某个点的时候，在搜索它的祖宗时递归地求出路上全部结点的度数，那么它的度数就是d[x]+=d[f[x]]。

如上图，pa在一次操做中并入了pb。
而在另外一次操做中，对a的进行了查询（求祖宗），便有以下路径压缩的并更新d[]的过程：
递归地找出祖宗pb。
pa的祖宗就是pb，度数在合并的时候已经求出来了，因此更新 \(0\)。
c的父亲节点是pa，合并的时候并无更新（所以记录的是距离pa的度数），度数须要加上 \(d[pa]\)，而后进行路径压缩。

a的父亲节点是c，在上一步更新了，因此度数加上 \(d[c]\) 便可，相似的，进行路径压缩。

（这里可能有点难理解，不过只要记住：所谓的d[x]指的是节点x相对于它父节点的度数便可）

不理解的地方能够结合代码理解

放上代码：（~~很短的~~）

#include<bits/stdc++.h>
using namespace std;

const int N=5e4+5;

int f[N],d[N];

int find(int x){
    if(x!=f[x]){
        int root=find(f[x]);
        d[x]+=d[f[x]];
        f[x]=root;
    }   
    return f[x];
}

int main(){
    int n,m;
    cin>>n>>m;
    
    for(int i=1;i<N;i++) f[i]=i;
    
    int cnt=0;
    while(m--){
        int op,a,b;
        cin>>op>>a>>b;
        
        //2,3 judge
        if(a>n || b>n){
            cnt++;
            continue;
        }
        if(a==b && op==2){
            cnt++;
            continue;
        }
        
        int pa=find(a),pb=find(b);
        
        int t= op==2;
        if(pa==pb){
            if(((d[a]-d[b])%3+3)%3!=t) cnt++;
        }else{
            f[pa]=pb;
            d[pa]=t+d[b]-d[a];
        }
    }
    
    cout<<cnt<<endl;
    
    return 0;
}

例题

https://www.acwing.com/problem/content/241/
分析：思路彻底相似于食物链那题。

代码

#include using namespace std;

const int N=2e4+5;

unordered_map<int,int> h;
int n,m;
int f[N];
int d[N];

int get(int x){
if(h.count(x)==0) h[x]=++n;
return h[x];
}

int find(int x){
if(f[x]!=x){
int root=find(f[x]);
d[x]^=d[f[x]];
f[x]=root;
}
return f[x];
}

int main(){
cin>>n>>m;
n=0;

//init
for(int i=1;i<N;i++) f[i]=i;

int ans=m;
for(int i=1;i<=m;i++){
    int a,b;
    string op;
    
    cin>>a>>b>>op;
    a=get(a-1); b=get(b);
    
    int t= op=="odd";
    
    int pa=find(a),pb=find(b);
    
    if(pa==pb){
        if(abs(d[a]-d[b])!=t){
            ans=i-1;
            break;
        }
    }else{
        //merge
        f[pa]=pb;
        d[pa]=d[a]^d[b]^t;
    }
}

cout<<ans<<endl;

return 0;

}

【数据结构】带权并查集

目录

简介

详细介绍

例题