Peienwu's Blog

Hello world

0%

資芽第十週：進階圖論（一）

發表於 分類於 Valine：
文章字數： 6.4k 所需閱讀時間 ≈ 6 分鐘

上課內容

並查集 Disjoint Set

目標：快速判斷兩個元素是否同屬一個集合
功能：詢問元素隸屬的集合、合併兩個集合，在圖論中，集合通常表示連通快，並查集可以查詢任兩點是否連通。在實作MST的時候，當我們要檢查兩個點連接成的邊是否會跟其他已經加入的邊形成環，就會使用並查集幫助我們判斷！
複雜度：非常優秀，可以說是O(1)

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
#include <bits/stdc++.h>
#define N 100001
using namespace std;
int n,boss[N],num[N];

int find_boss(int a){        //使用路徑壓縮
    if(a==boss[a])return a;
    else return boss[a] = find_boss(boss[a]);
}

void merge(int a,int b){    //啟發式合併
    if(num[a]>=num[b]){     //較小的集合合併到較大的集合
        num[a] += num[b];
        boss[b] = a;
    }
    else{
        num[b] += num[a];
        boss[a] = b;
    }
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        boss[i] = i;
        num[i] = 1;
    }
    while(1){
        int a,b;cin>>a>>b;                    //要查詢兩個元素
        a = find_boss(a),b = find_boss(b);    //判斷是否同屬一個集合
        if(a!=b){                             //老大不同屬不同集合
            cout<<"不同集合"<<endl;
            merge(a, b);
        }
        else cout<<"同集合"<<endl;
        for(int i=1;i<=n;i++)cout<<boss[i]<<" ";
        cout<<endl;
    }
}

路徑壓縮
在回傳過程中順便利用遞迴把所經過的boss指向最上面的boss，由左圖變成右圖，效率更高（實測其實差不多，可能logn已經夠小加上遞迴本來就比較慢）

用遞迴實現的特性實現，遞迴拉上來的時候順便更新boss[x]：

路徑壓縮搭配啟發式合併，複雜度：$O(α(N))$等同常數

上機作業

最小生成樹

題目連結NEOJ
題目連結TIOJ
實作講義
資芽講義

這一題手刻最小生成樹，感覺蠻好的，都是利用一些性質來實作最小生成樹

性質一：樹

最小生成圖一定會是一棵樹，不具備環，且一共有n-1條邊
如果這張圖不是樹，則必定有環，即代表可以再拔掉一條邊使權重和更小

性質二：Cycle Property

C是圖上的一個環，e是C上權重最大一條邊，則e必不在MST一部分（證明：反證，假設e在MST，則加入另一邊比e權重更小形成環，此時把e拔掉可以形成更小的權重和，因此矛盾）

性質三：Cut Property

把圖上的點集分割成兩半，則cut上面的邊集合中最小權重的邊e會在MST裡面（證明：反證，假設e不在MST，則加入e會形成連接兩半節點的環，此時拔掉另一比e權重大的邊，會形成更小權重和，因此矛盾）

利用性質二、性質三，就可以利用Kruskal演算法：利用到併查集的維護搭配路徑壓縮，可以快速判斷一個元素是否與另一個元素同屬一個集合（複雜度幾乎可以$O(1)$，更準確來說是$O(\alpha)$），Kruskal總複雜度為 $O(ElogE)$
另外還有一種實作方式Prim’s algorithm，等等再看

實作步驟

1. 初始化設定： 設定好boss以及集合大小等參數

2. 對所有的邊依照權重排序： 利用$O(m\log m)$的時間排序，將邊依照權重由小到大加入MST中

3. 依序加入邊： 以下會有兩種情況，可以用並查集+路徑壓縮（優化）判斷是否會形成環

  • Case 1: 如果加了這條邊形成環（查到有一樣的boss）
    • 那這條邊會是這個環上的最大邊
    • 根據 Cycle property，這條邊不會是MST的一部分
  • Case 2: 加了這條邊不會形成環
    • 那這條邊是條橋，連接左右兩棵樹
    • 根據 Cut Property，因為這條邊是這個 cut 上最小的邊
    • 所以這條邊會是 MST 的一部分

4. 判斷是否合法： n個點所形成的樹會有n-1條邊，最小生成樹是一棵樹就必須滿足條件。

KRUSKAL’S ALGORITHM

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
#include <bits/stdc++.h>
#define int long long
#define N 200005
#define ios ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
int n,m,num[N],boss[N];
struct Node{
    int x,y,w;
}edge[N];

bool cmp(Node a, Node b){
    return a.w < b.w;
}
int findboss(int a){                    //尋找集合的老大（代表整個集合）
    if(a==boss[a])return a;
    return boss[a]=findboss(boss[a]);   //遞迴搭配路徑壓縮
}

signed main(){
    ios;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>edge[i].x>>edge[i].y>>edge[i].w;
    }
    for(int i=0;i<n;i++){
        num[i] = 1;
        boss[i] = i;
    }
    sort(edge,edge+m,cmp);                 //依照權重大小放入MST
    int result = 0,num_edge = 0;
    for(int i=0;i<m && num_edge<n;i++){    //樹必須滿足小於n-1條邊
        int a = findboss(edge[i].x),b = findboss(edge[i].y);
        if(a!=b){                          //boss不同可以放入MST（加入不會形成環by Cut Property）
            if(num[a]>=num[b]){            //執行啟發式合併
                boss[b] = a;
                num[a]+=num[b];
            }
            else{
                boss[a] = b;
                num[b]+=num[a];
            }
            result+=edge[i].w;
            num_edge++;
        }
    }
    cout<<result<<endl;
    //這邊可以判斷num_edge==n-1有沒有成立，不過題目是輸入都可以形成MST
}

Prim’s Algorithm

是一種貪婪演算法，首先取任一點加入最小生成樹中，接著將連到的邊加入heap中，每一次取出heap中邊權重最小的邊，如果這一條邊連到的點尚未被走訪，則加入這一條邊為最小生成數。正確性證明則可用cut proprity證明每次都加入權重最小的邊即為最小生成數。

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
#include <bits/stdc++.h>
#define Orz ios::sync_with_stdio(0),cin.tie(0)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pii pair<int,int>
#define pdd pair<double,double>
#define int long long
#define ll long long
#define ld long double
#define N 200005
#define eps 1e-9
#define x first
#define y second
using namespace std;
int n,m;
bool visit[N];

struct node{
    int to,w;
};
vector<node> edge[N];

struct cmp{
    bool operator()(node a,node b){
        return a.w > b.w;
    }
};

signed main(){
    Orz;
    memset(visit,0,sizeof(visit));
    cin>>n>>m;
    rep(i,0,m-1){
        int a,b,w;cin>>a>>b>>w;
        edge[a].push_back({b,w});
        edge[b].push_back({a,w});
    }
    priority_queue<node,vector<node>,cmp> pq;
    visit[1] = 1;
    for(auto i : edge[1])pq.push(i);
    int num_edge = 0,ans = 0;
    while(num_edge < n-1){
        node x = pq.top();pq.pop();
        if(visit[x.to])continue;
        visit[x.to] = 1;
        num_edge += 1;
        ans += x.w;
        for(auto i : edge[x.to]){
            pq.push(i);
        }
    }
    cout<<ans<<endl;
}

高棕櫚的意外收穫

題目連結
講義連結

這一題就是按照字典序print出尤拉路徑，特別用鄰接矩陣來存圖是因為要按照字典序輸出，如果用鏈結串列來存還要花時間排序，因此用大一點的空間來節省時間

尤拉路徑也是一筆畫問題，每一個節點一定會有進有出，因此原先的無向圖上每一點一定度數為偶數，若有奇點則選擇其中一個奇點作為起點，當奇點數量超過兩個則代表無解。我們將DFS的過程中離開當前節點的順序紀錄起來，逆序輸出就是一組合法歐拉迴路的解了！

實作程序

1. 判斷奇點個數，若奇點個數k：

  • k > 2，那麼無解
  • k = 2，則選擇其中一個奇點作為起點
  • k = 0，則選擇任意一個點作為起點

2. DFS 執行下列步驟

若當前節點還有尚未走過的邊，那麼拜訪該邊，並在拜訪完後輸出該邊
否則離開當前結點

3. 若還有節點尚未拜訪，則無解
4. 否則輸出順序即為一組解

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
#include <bits/stdc++.h>
#define N 501
using namespace std;
int n,Edge[N][N],ans[1025],ind = 0;

void DFS(int cur){
    for(int i=1;i<=500;i++){
        if(Edge[cur][i]){
            Edge[cur][i]--;Edge[i][cur]--;
            DFS(i);
        }
    }
    ans[ind++] = cur;
}

signed main(){
    cin>>n;
    memset(Edge, 0, sizeof(Edge));
    for(int i=0;i<n;i++){
        int a,b;cin>>a>>b;
        Edge[a][b]++;
        Edge[b][a]++;
    }
    int start = 1;                //開始的節點編號
    for(int i=1;i<=500;i++){
        int sum = 0;
        for(int j=1;j<=500;j++){
            sum+=Edge[i][j];
        }
        if(sum%2!=0){             //找到第一個度數為奇數的節點
            start = i;
            break;
        }
    }
    DFS(start);
    for(int i=ind-1;i>=0;i--)cout<<ans[i]<<endl;
}

陣線推進

題目連結
拓墣排序題，兩種實作方式，第一是BFS變形實作（queue實作），被pop出來的順序就是topological sort
第二種就是DFS搭配時間戳記，最晚離開的放在最前面

這一題是把入度為0的節點先push進priority_queue（按照字典序），當一個點處理過之後，入度變成0的所有它指向的點在push進queue裡面
拓墣排序可以用在DAG的判定以及解決具有依賴關係的問題

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
#include <bits/stdc++.h>
#define N 100001
using namespace std;
int t,n,m,deg[N];//入度
int ans[N],ind = 0;

signed main(){
    cin>>t;
    while(t--){
        memset(deg,0,sizeof(deg));
        memset(ans, 0, sizeof(ans));
        ind = 0;
        vector<int> edge[N];
        cin>>n>>m;
        for(int i=0;i<m;i++){
            int a,b;cin>>a>>b;
            edge[a].push_back(b);
            deg[b]++;
        }
        priority_queue<int,vector<int>,greater<int> > qq;//priority_queue取代queue
        for(int i=0;i<n;i++)if(deg[i]==0)qq.push(i);
        while(!qq.empty()){
            int cur = qq.top();
            qq.pop();
            ans[ind++] = cur;
            int len = edge[cur].size();
            for(int i=0;i<len;i++){
                deg[edge[cur][i]]--;
                if(deg[edge[cur][i]]==0)
                    qq.push(edge[cur][i]);
            }
        }
        if(ind==n){
            cout<<ans[0];
            for(int i=1;i<n;i++)cout<<" "<<ans[i];
            cout<<endl;
        }
        else cout<<"QAQ"<<endl;
    }
}

手寫作業

這一次的手寫也蠻困難的，討論BIT(fenwick tree)的實作以及複雜度！