Peienwu's Blog

Hello world

0%

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

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

上課內容

雙連通元件

樹壓平、點雙連通、邊雙連通

SCC強連通元件

LCA（最低共同祖先）

上機作業

高棕櫚傳遞鏈

題目連結
在一張圖中找割點（定義：拔掉它整張圖就不連通了）
作法：如果用暴力，可以每一個點拔掉，做一次DFS判斷是否聯通（效率太差）

效率更高的就是Trajan 演算法找AP(articulation point)

Tarjan’s algorithm 找 AP
邊的種類可以分成：Tree edge,Back edge,Forward edge,Cross edge，其中無向圖中只會有樹邊跟回邊（按照無向邊DFS的結果，Foward edge 都會變成子孫的back edge, cross edge 會變成樹邊）

維護一個low函數，代表不經過父節點能到的最小時間戳記（進入）的節點，lv函數為當前節點的時間戳記。一個點是不是割點，只要他的任意子節點的low函數大於等於自己的時間戳記編號，那把這個點拔掉，他小孩就走不到祖先了（如果走得到祖先，對於這一棵子樹，拔掉當前節點就可利用此邊繼續連通），所以他就是割點。
更新：$low[now] = min(low[now],low[next])$分別為利用子孫或靠自己

必須要注意的是，割點判斷時要把root的特例獨立判斷。其實root反而比較簡單，如果root有超過一個子樹，代表拔掉root以後會分裂成以每個子樹為單位的連通塊

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
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0);
#define int long long
#define N 1000001
using namespace std;
int n,m,low[N],lv[N],es=1,root,son_cnt = 0;
bool visit[N],ans[N];
vector<int> edge[N];
//low函數為不經過父節點能到的最小時間戳記,lv為當前進入時間戳記

void DFS(int now,int father){
    visit[now] = 1;             //將此點設為已拜訪
    low[now] = lv[now] = es++;  //進入的時間戳記
    
    int len = edge[now].size();
    for(int i=0;i<len;i++){     //拜訪每一個子孫
        int next = edge[now][i];
        if(now==root && !visit[next])son_cnt++;//計算root小孩（處理特例）
        if(!visit[next]){       //排除走到祖先的情況
            DFS(next, now);
            if(low[next]>=lv[now] && now!=root)ans[now]=1;
            //無法透過小孩到達比自己淺的節點，將now設為AP
        }
        if(next!=father)low[now] = min(low[now],low[next]);
        //排除指向父親的情況，如果經過父親，拔掉就不能往更上面去
    }
}

signed main(){
    ios;
    cin>>n>>m;
    memset(lv, 0, sizeof(lv));
    memset(low, 0, sizeof(low));
    memset(visit, 0, sizeof(visit));
    memset(ans,0,sizeof(ans));
    
    for(int i=0;i<m;i++){
        int x,y;cin>>x>>y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    for(int i=0;i<n;i++){
        if(!visit[i]){
            root = i;
            son_cnt = 0;
            DFS(i, i);
            if(son_cnt>1)ans[root] = 1;
        }
    }
    for(int i=0;i<n;i++)if(ans[i])cout<<i<<endl;
}

謠言問題

題目連結
跟上一題（高棕櫚傳遞鏈）蠻類似的，一樣找到割點，不同的是要在DFS過程中同時紀錄子樹節點的數量。如果碰到割點，維護拔掉它之後分裂出去那些子樹的節點個數，到時候透過節點總數-拔掉後分裂個數即可推算有幾個人會知道謠言，取min即可

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
53
54
55
56
57
58
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0);
#define int long long
#define N 30001
using namespace std;
int n,m,root,lv[N],low[N],tree_cnt[N],es = 1;
bool visit[N],ans[N];
vector<int> edge[N];

int DFS(int now,int father){      //回傳當前子節點個數
    visit[now] = 1;
    lv[now] = es;
    low[now] = es++;
    
    int len = edge[now].size(),sum=1;//計算節點數
    for(int i=0;i<len;i++){
        int next = edge[now][i];     //下一個節點
        
        if(!visit[next]){
            int temp = DFS(next,now);
            sum += temp;
            if(low[next] >= lv[now] && now!=root){ //不能拔掉root
                ans[now] = 1;           //設為AP
                tree_cnt[now] += temp;  //被拔掉後可被分割成幾個連通塊節點數
            }
        }
        if(next!=father)low[now] = min(low[now],low[next]);
    }
    return sum;
}

signed main(){
    ios;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int x,y;cin>>x>>y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    cin>>root;
    
    memset(ans, 0, sizeof(ans));
    memset(visit, 0, sizeof(visit));
    memset(tree_cnt, 0, sizeof(tree_cnt));
    
    int sum = DFS(root,root),min_cnt = INT_MAX,min_pos = 0;
    
    for(int i=1;i<=n;i++){
        int temp = sum-tree_cnt[i]; //拔掉後剩下連通塊大小（跟root連的）
        if(ans[i] && temp < min_cnt){
            min_pos = i;        //拔掉第幾個
            min_cnt = temp;     //更新拔掉後剩下連通塊大小
        }
    }
    if(min_cnt == INT_MAX)cout<<0<<endl;
    else cout<<min_pos<<" "<<min_cnt<<endl;
}

高棕櫚傳遞鏈

題目連結
前兩題找割點，這一題是找橋，跟找割點的方法幾乎一樣，而且對於邊還不需要討論root的情況（root變成不是特例），然後判斷割點的 >= 變成 >，原因可以透過畫圖理解（把點拔掉跟把邊拔掉的差別），就可以實作了！
題目有一個特別的要求，按照給邊的順序進行輸出，那可以搭配set來快速查看某一元素是否在集合內$O(logN)$，接著就按照給定的條件來輸出

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
53
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0);
#define int long long
#define N 1000001
using namespace std;
int n,m,lv[N],low[N],timestamp = 1;
bool visit[N];
vector<int> edge[N];
vector<pair<int, int>> ans;
set<pair<int, int>>s;

void DFS(int now,int father){
    lv[now] = low[now] = timestamp++;
    visit[now] = 1;
    
    int len = edge[now].size();
    for(int i=0;i<len;i++){
        int next = edge[now][i];
        
        if(!visit[next]){
            DFS(next, now);
            if(low[next] > lv[now]){
                if(next<now)s.insert(make_pair(next,now));
                else s.insert(make_pair(now, next));
            }
        }
        if(next!=father)low[now] = min(low[now],low[next]);
    }
}

signed main(){
    ios;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int x,y;cin>>x>>y;
        edge[x].push_back(y);
        edge[y].push_back(x);
        ans.push_back(make_pair(x, y));
    }
    memset(visit, 0, sizeof(visit));
    
    for(int i=1;i<=n;i++){
        if(!visit[i]){
            DFS(i, i);
        }
    }
    for(int i=0;i<m;i++){
        pair<int, int> temp = ans[i];
        if(s.find(temp)!=s.end()){
            cout<<temp.first<<" "<<temp.second<<endl;
        }
    }
}

芽芽逛大街

題目連結
有向無環圖的 case → DAG 最長路徑!
將每個強連通元件縮成點後，因為內部的點可以一直亂走全部走到，所以只要將新點的點權更新成內部所有點的點權總和，得到一張新的有向無環圖，就可以直接做 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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <bits/stdc++.h>
#define int long long
#define ios ios::sync_with_stdio(0),cin.tie(0);
#define N 500002
using namespace std;
int n,m,dfn[N],low[N],es = 1,stk_in[N],vertex_val[N],deg[N];
//dfn為時間戳記,low為back, cross edge（經過最多一次）到達最小點dfn,stk_in是否在stack內
bool visit[N];
int scc[N],scc_ind = 0,scc_val[N];//紀錄屬於哪個scc,scc編號,scc編號的價值（權重和）
int topological_order[N],ind = 0;

struct edg{
    int to;
    int val;
};

vector<edg> edge[N],new_edge[N];
stack<int> s;

void DFS(int now){
    dfn[now] = low[now] = es++;
    s.push(now);
    stk_in[now] = 1;
    visit[now] = 1;
    int len = edge[now].size();
    for(int i=0;i<len;i++){
        int next = edge[now][i].to;
        if(!visit[next]){       //尚未拜訪則拜訪
            DFS(next);
            low[now] = min(low[now],low[next]);
        }
        else if(stk_in[next]){  //在stk內且已拜訪->同屬一個SCC
            low[now] = min(low[now],dfn[next]);
            //這條邊指向還沒出stack的點，可為cross or back edge 更新low[now]
        }
    }
    //如果是scc就pop stack裡面的東西
    if(low[now] == dfn[now]){
        stk_in[now] = 0;        //pop出stack裡面
        scc[now] = ++scc_ind;   //進行SCC編號
        scc_val[scc_ind] = vertex_val[now]; //更新點權
        while(s.top()!=now){                //pop直到now被找到
            scc[s.top()] = scc_ind;
            stk_in[s.top()] = 0;            //pop出來
            scc_val[scc_ind] += vertex_val[s.top()];
            s.pop();
        }
        s.pop();//將stack 中now也pop
    }
}

signed main(){
    ios;
    cin>>n>>m;
    memset(visit, 0, sizeof(visit));
    memset(stk_in, 0, sizeof(stk_in));
    memset(deg, 0, sizeof(deg));
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        vertex_val[i] = x;
    }
    for(int i=0;i<m;i++){
        int x,y,val;cin>>x>>y>>val;//x指向y
        edge[x].push_back( edg{y,val} );
    }
    for(int i=1;i<=n;i++)
        if(!visit[i])DFS(i);
    
    //枚舉每一條邊更新邊權
    for(int i=1;i<=n;i++){
        int len = edge[i].size();
        for(int j=0;j<len;j++){
            int to = edge[i][j].to;
            if(scc[to]==scc[i]){
                int ind = scc[to];
                scc_val[ind]+=edge[i][j].val;
            }
            else{   //不同SCC指向不同的邊
                new_edge[scc[i]].push_back( edg{scc[to],edge[i][j].val});
                deg[scc[to]]++;
            }
        }
    }
    
    //Topological sort
    queue<int> q;
    
    for(int i=1;i<=scc_ind;i++)
        if(deg[i]==0)q.push(i);

    while(!q.empty()){
        int now = q.front(),len = new_edge[now].size();
        topological_order[ind++] = now;
        q.pop();
        for(int i=0;i<len;i++){
            int next = new_edge[now][i].to;
            if(--deg[next]==0)q.push(next);
        }
    }
    
    //拓墣排序完進行DP找最長路徑
    int dp[ind],ans = 0;
    for(int i=1;i<=scc_ind;i++){
        dp[i] = scc_val[i];
        ans = max(ans, scc_val[i]);
    }
    
    for(int i=0;i<ind;i++){
        int now = topological_order[i],len = new_edge[now].size();
        for(int j=0;j<len;j++){
            int next = new_edge[now][j].to;
            dp[next] = max(dp[next],scc_val[next]+dp[now]+new_edge[now][j].val);
            ans = max(ans, dp[next]);
        }
    }
    cout<<ans<<endl;
}

手寫作業

介紹雜湊，重點在於rolling hash，這也是下一週隨機課程當中會用到的重要概念。