Persistent Union Find
(DataStructure/persistentunionfind.hpp)

• View this file on GitHub
• Last update: 2022-01-16 22:20:31+09:00
• Include: #include "DataStructure/persistentunionfind.hpp"

Depends on

• Persistent Array (DataStructure/persistentarray.hpp)

Verified with

• Verify/LC_persistent_unionfind.test.cpp

Code

#pragma once
#include "DataStructure/persistentarray.hpp"


struct PersistentUnionFind{
    PersistentArray<int> dat;
    PersistentUnionFind(int n){
        rep(i,0,n)dat.set(i,-1);
    }
    int root(int x){
        if(dat.get(x)<0)return x;
        else return root(dat.get(x));
    }
    bool unite(int x,int y){
        x=root(x),y=root(y);
        if(x==y)return false;
        int p=dat.get(x),q=dat.get(y);
        if(p>q)swap(x,y);
        dat.set(x,p+q);
        dat.set(y,x);
        return true;
    }
    bool same(int x,int y){return root(x)==root(y);}
    int size(int a){return -dat.get(root(a));}
};

/**
 * @brief Persistent Union Find
 */

#line 2 "DataStructure/persistentarray.hpp"

template<typename T,int B=4>class PersistentArray{
    const int M=(1<<B)-1;
    struct Node{
        Node *cp[1<<B]={};
        T val;
    };
    Node* set(int i,T x,Node* a){
        Node *ret=new Node();
        if(a){
            memcpy(ret->cp,a->cp,sizeof(a->cp));
            ret->val=a->val;
        }
        if(i)ret->cp[i&M]=set(i>>B,x,ret->cp[i&M]);
        else ret->val=x;
        return ret;
    }
    T get(int i,Node* a){
        if(i)return get(i>>B,a->cp[i&M]);
        else return a->val;
    }
public:
    Node *root;
    PersistentArray(Node* _r=nullptr):root(_r){}
    void set(int i,T x){
        root=set(i,x,root);
    }
    T get(int i){
        return get(i,root);
    }
};

/**
 * @brief Persistent Array
 */
#line 3 "DataStructure/persistentunionfind.hpp"

struct PersistentUnionFind{
    PersistentArray<int> dat;
    PersistentUnionFind(int n){
        rep(i,0,n)dat.set(i,-1);
    }
    int root(int x){
        if(dat.get(x)<0)return x;
        else return root(dat.get(x));
    }
    bool unite(int x,int y){
        x=root(x),y=root(y);
        if(x==y)return false;
        int p=dat.get(x),q=dat.get(y);
        if(p>q)swap(x,y);
        dat.set(x,p+q);
        dat.set(y,x);
        return true;
    }
    bool same(int x,int y){return root(x)==root(y);}
    int size(int a){return -dat.get(root(a));}
};

/**
 * @brief Persistent Union Find
 */

Back to top page