data-structure/dsu.hpp

• View this file on GitHub
• Last update: 2024-07-29 18:44:45+07:00
• Include: #include "data-structure/dsu.hpp"

Verified with

• verify/yosupo/data-structure/unionfind.test.cpp

Code

#pragma once

/**
 * Author: Teetat T.
 * Date: 2024-06-28
 * Description: Disjoint Set Union.
 */

struct DSU{
    vector<int> p,sz;
    DSU(){}
    DSU(int n){init(n);}
    void init(int n){
        p.resize(n);
        iota(p.begin(),p.end(),0);
        sz.assign(n,1);
    }
    int find(int u){
        return p[u]==u?u:p[u]=find(p[u]);
    }
    bool same(int u,int v){
        return find(u)==find(v);
    }
    bool merge(int u,int v){
        u=find(u),v=find(v);
        if(u==v)return false;
        sz[u]+=sz[v];
        p[v]=u;
        return true;
    }
    int size(int u){
        return sz[find(u)];
    }
};

#line 2 "data-structure/dsu.hpp"

/**
 * Author: Teetat T.
 * Date: 2024-06-28
 * Description: Disjoint Set Union.
 */

struct DSU{
    vector<int> p,sz;
    DSU(){}
    DSU(int n){init(n);}
    void init(int n){
        p.resize(n);
        iota(p.begin(),p.end(),0);
        sz.assign(n,1);
    }
    int find(int u){
        return p[u]==u?u:p[u]=find(p[u]);
    }
    bool same(int u,int v){
        return find(u)==find(v);
    }
    bool merge(int u,int v){
        u=find(u),v=find(v);
        if(u==v)return false;
        sz[u]+=sz[v];
        p[v]=u;
        return true;
    }
    int size(int u){
        return sz[find(u)];
    }
};

Back to top page