并查集（进阶）

介绍

扩展域并查集：扩展节点个数，表示更多的状态

带权并查集：边存储了额外的信息，需要在 find、merge 操作中改变

扩展域并查集

关押罪犯

本题可以令$[1,n]$为第一个监狱，$[n+1,2n]$为第二个监狱

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void solve()
{
    int n,q;
    cin>>n>>q;
    vector<PII> a;
    while(q--){
        int x,y,w;
        cin>>x>>y>>w;
        a.push_back({x,y,w});
    }
    sort(a.begin(),a.end(),[](PII &a,PII &b){return a[2]>b[2];});
    DSU dsu(n*2);
    for(auto [x,y,w] : a){
        x--;y--;
        if(dsu.same(x,y)){
            cout<<w;return;
        }else{
            dsu.merge(x+n,y);
            dsu.merge(x,y+n);
        }
    }
    cout<<0;
}

食物链

$x$为父（捕食者），$x+n$为本（当前），$x+2\cdot n$为子（食物）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void solve()
{
    int n,q;
    cin>>n>>q;
    DSU dsu(3*n+1);
    ll ans=0;
    while(q--){
        int op,x,y;
        cin>>op>>x>>y;
        if(x>n||y>n){ans++;continue;}
        if(op==1){
            if(dsu.same(x+n,y)||dsu.same(x+n,y+2*n)) ans++;
            else{
                dsu.merge(x,y);
                dsu.merge(x+n,y+n);
                dsu.merge(x+2*n,y+2*n);
            }
        }else{
            if(dsu.same(x+n,y)||dsu.same(x,y)){ans++;}
            else{
                dsu.merge(x+n,y+2*n);
                dsu.merge(x+2*n,y);
                dsu.merge(y+n,x);              
            }
        }
    }
    cout<<ans<<'\n';
}

带权并查集

银河英雄传说

额外开一个数组 d ，用于记录一个节点到其祖宗节点的距离

路径有权值，在路径压缩时需要改变 d 的值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
int f[N],d[N],siz[N];

int find(int x){
    if(f[x]!=x){
        int root=find(f[x]);
        d[x]+=d[f[x]];
        f[x]=root;
    } 
    return f[x];
}
void merge(int x,int y){
    x=find(x),y=find(y);
    f[x]=y;
    d[x]=siz[y];
    siz[y]+=siz[x];
}
void solve()
{
    for(int i=0;i<N;i++){
        f[i]=i;
        siz[i]=1;
    } 
    int t;cin>>t;
    while(t--){
        char op;cin>>op;
        int x,y;
        cin>>x>>y;
        x--;y--;
        if(op=='M'){
            merge(x,y);
        }
        else{
            if(find(x)!=find(y)){
                cout<<"-1\n";
            }
            else{
                cout<<abs(d[x]-d[y])-1<<'\n';
            }
        }
    }
}

LCT

还是容易想到带权并查集的，但是如何merge和find

merge时主要的困难点在于

1
2
deep[x]=1;
find(x);

find时

1
2
3
int fa=f[x];
f[x]=find(f[x]);
deep[x]+=deep[fa];

这样就可以更新x的根节点，下一次如果要访问x所在的子树，就会像访问y一样进行访问

find时，我们通过这样的操作，保证了只会进行一次非路径压缩的find，不会增大时间复杂度，即在第一次find时逐级向上并同时完成压缩路径

补充

星球大战

摧毁节点可以转化为反向生成节点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
void solve()
{
    int n,m;
    cin>>n>>m;
    vector<vector<int>> g(n);
    while(m--){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int k;cin>>k;
    vector<int> a(k);
    unordered_map<int,int> des;
    for(int i=k-1;i>=0;i--){
        cin>>a[i];
        des[a[i]]=1;
    }
    DSU dsu(n);
    unordered_map<int,int> mp;
    vector<int> ans;
    for(int i=0;i<n;i++){
        if(!des[i]){
            for(auto v : g[i]){
                if(mp[v]!=0){
                    dsu.merge(i,v);
                }
            }
            mp[i]=1;
        }
    }
    int init=0;//初始连通块的数量
    for(int i=0;i<n;i++){
        if(!des[i]&&dsu.f[i]==i){
            init++;
        }
    }
    ans.push_back(init);
    int now=init;
    for(auto i : a){
        set<int> st;
        for(auto v : g[i]){
            if(mp[v]!=0){
                st.insert(dsu.find(v));
            }
        }
        now=now-st.size()+1;
        mp[i]=1;
        ans.push_back(now);
        for(auto it : st){//在中途merge会造成错误，需要统计完后再一起merge
            dsu.merge(i,it);
        }
    }
    reverse(ans.begin(),ans.end());
    for(auto i : ans){
        cout<<i<<"\n";
    }
}

总结

带权并查集既要维护节点信息，又要保证find的高效性

解决方案是只在第一次find时进行节点信息维护和路径压缩

那么之后find的都是路径压缩后的路径