C++ 並查集實作

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

class dsu{
    private:
        vector<int> p;
        vector<long long> rank;
    public:
        void init(int n){
            for(int i=0;i<=n;i++){
                p.push_back(i);
                rank.push_back(1);
            }
        }
        
        int find(int a){
            if(a==p[a]) return a;
            return p[a]=find(p[a]);
        }
        
        bool same(int a,int b){
            return find(a)==find(b);
        }
        
        bool uni(int a,int b){
            if(!same(a,b)){
                int rA=rank[find(a)],rB=rank[find(b)];
                if(rA>rB){
                    p[find(b)]=p[find(a)];
                }else if(rA==rB){
                    p[find(b)]=p[find(a)];
                    rank[p[find(a)]]++;
                }else{
                    p[find(a)]=p[find(b)];
                }
            }
        }
};

包含路徑壓縮與啟發式合併。

C++程式設計教學(五)-函式與遞迴

你有遇過雖然重複卻無法使用迴圈的時候嗎?如果沒有,請見以下範例。

stable_sort(dt,dt+n,[](int a,int b){
    int ctA=0,ctB=0;
    while(a>=1){
        if(a%2==1){
            ctA++;
        }
        a/=2;
    }
    while(b>=1){
        if(b%2==1){
            ctB++;
        }
        b/=2;
    }
    return ctA<ctB;
});

藍色部分是引用c++的函式庫,先不用理會。看看橘色部分。有兩個 while 迴圈,幾乎在做一樣的事情。這時怎麼改?這就要用到函數了!

int ct(int a){
    int ctA=0;
    while(a>=1){
        if(a%2==1){
            ctA++;
        }
        a/=2;
    }
}

stable_sort(dt,dt+n,[](int a,int b){
    int ctA=ct(a),ctB=ct(b);
    return ctA<ctB;
});

簡潔了許多,然而,看起來似乎只有一個變數阿!實際上那個變數是從傳入的a,b複製過去的,而且用完就會銷毀。這就是函式方便之處。
以下才是真正的教學。

函式 ( function ) 在程式設計中有著至關重要的地位。事實上函式的宣告與變數有幾分相似。請看以下範例。

int db(int a){
    return a*2;
}
//函數通式,注意傳入的參數可以有多個(不只兩個),但每個前面都要加入型態名稱
<回傳值變數型態> <函式名>(<要傳入的變數型態> <變數名>,<變數型態> <變數名>){
    <程式碼>
    return <變數>
}

而遞迴則是在函式中呼叫自己,來達成更進階的功能。以費式數列為例。
A1=1, A2=1, An=An-1+An-2 if(n>2) 寫作程式即為。

int f(int n){
    if(n==1){
        return 1;
    }else if(n==2){
        return 1;
    }else{
        return f(n-1)+f(n-2);
    }
}

這裡先講個大概,後續在 DP 還有更多技巧。
下回會說陣列~