介紹

也稱為稱為並查集 • Disjoint-Set 是指能維護n 個物品中，哪些物品是同一種類的 東西的資料結構 • 常見的實作方法是：用一個有根樹來維護同一種類的物品(每個 樹稱為是一個group) 1. 要詢問兩個物品是否同一類時，找到各自的樹根看看是不是同一個東 西即可。(找一個點的樹根的操作被稱為find) 2. 要把兩個物品設為同一類時，也是找到各自的樹根後，把其中一個樹 根指向另一個樹根即可。(此步驟被稱為union)

模板

struct Disjoint_set{
    int d[MAXNUM],num[MAXNUM];
    void array_set(int n){
        for(int i=1;i<=n;i++){
            d[i]=i;
            num[i]=1;
        }
    }
    int find(int n){
        if(n!=d[n]){
            return d[n]=find(d[n]);
        }else{
            return n;
        }
    }
    bool Union(int x,int y){
        x=find(x);
        y=find(y);
        if(x==y)return 0;
        if(num[x]>num[y])swap(x,y);
        num[y]+=num[x];
        d[x]=y;
        return 1;
    }
}DS;