Một Số ứng Dụng Nâng Cao Của Cây DFS (phần 1) - AI Design

I. Cây DFS và bài toán định chiều đồ thị

1. Phân loại các cung trên cây DFStext{DFS}DFS

Trong quá trình DFStext{DFS}DFS duyệt đồ thị, với mỗi đỉnh uuu ta có được đỉnh par[u]text{par}[u]par[u] là đỉnh cha của đỉnh uuu trên đường đi. Nếu xây dựng đồ thị con gồm các cạnh có dạng (par[u],u),(text{par}[u], u),(par[u],u), ta sẽ thu được một cây, gọi là cây DFStext{DFS}DFS. Hình vẽ dưới đây biểu diễn một cây DFStext{DFS}DFS với 999 đỉnh, các cạnh nét liền là cạnh thuộc cây DFStext{DFS}DFS, các cạnh nét đứt là cạnh không thuộc cây DFStext{DFS}DFS.

Trên đồ thị có hướng, xét mọi cung được thăm và không được thăm trong quá trình DFS,text{DFS},DFS, ta có các loại cung sau:

• Cung của cây DFS (Tree Edges): Các cung được thăm trong quá trình DFStext{DFS}DFS (cung màu trắng nét liền).
• Cung xuôi (Forward edges): Cung không thuộc cây DFStext{DFS}DFS có dạng (u→v)(u rightarrow v)(u→v); trong đó uuu là cha của vvv trong quá trình DFStext{DFS}DFS (cạnh xanh lá).
• Cung ngược (Back edges): Cung không thuộc cây DFStext{DFS}DFS và có dạng (v→u)(v rightarrow u)(v→u); trong đó uuu là cha của vvv (cạnh đỏ) nhưng vvv đã được thăm trước đó do một dây chuyền DFStext{DFS}DFS khác.
• Cung chéo (Cross edges): Cung không thuộc cây DFStext{DFS}DFS, trong đó uuu và vvv thuộc hai nhánh khác nhau của cùng một cây DFStext{DFS}DFS (cạnh tím). Cung này sinh ra do tồn tại một đỉnh www đã duyệt trước cả uuu và vvv, và đỉnh www này tạo ra hai nhánh DFStext{DFS}DFS khác nhau, một nhánh chứa uuu và một nhánh chứa vvv. Cung chéo chỉ có thể đi từ nhánh thăm sau tới nhánh thăm trước chứ không thể đi từ nhánh thăm trước tới nhánh sau trước (thật vậy, nếu cung chéo đi từ nhánh thăm trước sang nhánh thăm sau thì cung đó cũng chính là cung thuộc nhánh thăm trước).

Trên đồ thị vô hướng, chỉ tồn tại hai loại cung là cung thuộc cây DFStext{DFS}DFS và cung ngược (không thuộc cây DFStext{DFS}DFS).

Đối với đồ thị vô hướng, nếu như trong quá trình DFStext{DFS}DFS, cứ khi duyệt qua một cạnh (u,v)(u, v)(u,v) thì ta bỏ luôn chiều (v,u)(v, u)(v,u) đi và định chiều lại cạnh (u,v)(u, v)(u,v) thành cung (u→v)(u rightarrow v)(u→v), thì thu được một phép định chiều đồ thị gọi là phép định chiều DFStext{DFS}DFS.

2. Đánh số các đỉnh trên cây DFStext{DFS}DFS và ghi nhận cung ngược lên cao nhất

Một số định nghĩa mảng sử dụng:

• num[u]:text{num}[u]:num[u]: Số thứ tự duyệt đến của đỉnh uuu trong quá trình DFStext{DFS}DFS.
• low[u]:text{low}[u]:low[u]: Số thứ tự nhỏ nhất (giá trị num[]text{num}[]num[]) của một đỉnh vvv tới được từ nhánh DFStext{DFS}DFS gốc uuu bằng tối đa một cung ngược. Có nghĩa là, nếu trong nhánh DFStext{DFS}DFS gốc uuu tồn tại nhiều cung ngược, thì ta ghi nhận cung ngược hướng lên đỉnh có thứ tự thăm nhỏ nhất. Ban đầu low[u]=num[u],text{low}[u] = text{num}[u],low[u]=num[u], do đỉnh uuu có thể tự đi tới chính nó.
• par[u]:text{par}[u]:par[u]: Đỉnh cha của đỉnh uuu trên cây DFStext{DFS}DFS.
• tail[u]:text{tail}[u]:tail[u]: Thời điểm duyệt xong nhánh DFStext{DFS}DFS gốc uuu. Các đỉnh có số thứ tự thăm từ num[u]text{num}[u]num[u] tới tail[u]text{tail}[u]tail[u] sẽ thuộc nhánh DFStext{DFS}DFS gốc uuu.

Nhận xét: Trong quá trình DFStext{DFS}DFS từ đỉnh uuu tới đỉnh v,v,v, xảy ra ba trường hợp:

• Nếu đỉnh vvv chính bằng đỉnh đã gọi đệ quy tới uuu ở trước đó thì bỏ qua.
• Nếu đỉnh vvv chưa thăm thì DFStext{DFS}DFS thăm vvv. Khi duyệt xong nhánh DFStext{DFS}DFS gốc v,v,v, ta đã xây dựng được một nhánh DFStext{DFS}DFS gốc vvv là cây con của nhánh DFStext{DFS}DFS gốc uuu. Do đó, các cung ngược đi ra từ nhánh DFStext{DFS}DFS gốc vvv cũng là cung ngược đi ra từ nhánh DFStext{DFS}DFS gốc uuu. Ta sẽ cực tiểu hóa:

low[u]=min(low[u],low[v])text{low}[u] = text{min}(text{low}[u], text{low}[v]) low[u]=min(low[u],low[v])

• Nếu đỉnh vvv đã thăm rồi, tức là (u→v)(u rightarrow v)(u→v) là một cung ngược không thuộc cây DFStext{DFS}DFS. Ta cực tiểu hóa:

low[u]=min(low[u],num[v])text{low}[u]=text{min}(text{low}[u], text{num}[v]) low[u]=min(low[u],num[v])

Cài đặt:

int time_dfs =0;voiddfs(int u){ num[u]= low[u]=++time_dfs;// Xác định thời điểm duyệt tới của đỉnh u.for(int v: adj[u]){if(v == par[u])// Đỉnh v là đỉnh cha của đỉnh u -> bỏ qua.continue;if(!num[v])// Chưa duyệt v.{ par[v]= u;// Gán cha của đỉnh v là đỉnh u.dfs(v); low[u]=min(low[u], low[v]);// Cực tiểu hóa low[u].}else// Đỉnh v đã duyệt qua, (u -> v) là cung ngược. { low[u]=min(low[u], num[v]);}} tail[u]= time_dfs;}

Hình vẽ dưới đây minh họa một đồ thị gồm 888 đỉnh và các cạnh của nó:

Quá trình DFStext{DFS}DFS định chiều và đánh số đồ thị diễn ra như sau:

II. Bài toán tìm khớp và cầu của đồ thị

1. Giải thuật tìm khớp và cầu của đồ thị

Bài toán: Cho một đơn đồ thị vô hướng gồm nnn đỉnh (1≤n≤104)(1 le n le 10^4)(1≤n≤104) và mmm cạnh (1≤m≤5×104)(1le m le 5 times 10^4)(1≤m≤5×104). Hãy xác định số lượng đỉnh khớp và cạnh cầu của đồ thị?

Định nghĩa:

• Một đỉnh được gọi là đỉnh khớp nếu như khi loại bỏ đỉnh này và các cạnh liên thuộc với nó khỏi đồ thị thì số thành phần liên thông của đồ thị tăng lên (các đỉnh màu xanh lá cây).
• Một cạnh được gọi là cạnh cầu nếu như khi loại bỏ cạnh này khỏi đồ thị thì số thành phần liên thông của đồ thị tăng lên (các cạnh màu đỏ).

Nhận xét: Cạnh cầu của đồ thị không thể là cung ngược, do khi bỏ đi cung ngược này thì không ảnh hưởng gì tới tính liên thông của đồ thị. Do đó, cạnh cầu bắt buộc phải là cung thuộc cây DFStext{DFS}DFS.

Hướng giải quyết: Tiến hành dựng cây DFStext{DFS}DFS và định chiều lại đồ thị đã cho, đồng thời ghi nhận cung ngược lên cao nhất theo giải thuật ở phần (1.2)(1.2)(1.2). Xét cung (u→v)(u rightarrow v)(u→v) là cung thuộc cây DFS,text{DFS},DFS, ta có:

• Nếu từ nhánh DFStext{DFS}DFS gốc vvv không có cung ngược nào lên phía trên v,v,v, tức là từ vvv chỉ có thể đi tới được các cạnh nội bộ của nhánh DFStext{DFS}DFS gốc vvv thôi. Lúc này, nếu ta loại bỏ cạnh (u,v)(u,v)(u,v) thì nhánh DFStext{DFS}DFS gốc vvv sẽ bị chia cắt với các nhánh DFStext{DFS}DFS khác, do đó số thành phần liên thông của đồ thị sẽ tăng lên. Tức là cạnh (u,v)(u,v)(u,v) là cầu khi và chỉ khi lowv=numvtext{low}_v=text{num}_vlowv​=numv​.
• Nếu từ nhánh DFStext{DFS}DFS gốc vvv không có cung nào ngược lên phía trên u,u,u, tức là nhánh DFStext{DFS}DFS gốc vvv kết nối với các đỉnh khác duy nhất thông qua cạnh (u,v)(u, v)(u,v). Khi đó, nếu bỏ đỉnh uuu đi thì nhánh DFSDFSDFS gốc vvv cũng sẽ bị chia cắt với các nhánh khác, do đó đỉnh uuu là đỉnh khớp khi và chỉ khi lowv≥numutext{low}_v ge text{num}_ulowv​≥numu​.
• Ngoài ra, nếu một đỉnh uuu là gốc của một cây DFStext{DFS}DFS và cây này có ít nhất 222 nhánh con, thì khi bỏ đỉnh uuu đi, hai nhánh con sẽ bị chia cắt thành 222 thành phần liên thông khác nhau. Khi đó u cũng là khớp. Để kiểm soát việc này, ta sử dụng thêm một mảng (cntchild)u(cnt_text{child})_text{u}(cntchild​)u​ là số nhánh con của đỉnh uuu. Mảng isarticulation[u]is_text{articulation}[u]isarticulation​[u] sẽ dùng để đánh đấu đỉnh uuu có phải một khớp hay không, nếu có thì isarticulation[u]=1,is_text{articulation}[u] = 1,isarticulation​[u]=1, ngược lại isarticulation[u]=0is_text{articulation}[u] = 0isarticulation​[u]=0.

Cài đặt:

#include<bits/stdc++.h>#definetask"GRAPH."#defineinf1e9+7#definexfirst#defineysecondusingnamespace std;constint maxn =1e5+10;// Hai biến cnt_bridge, cnt_articulation dùng để đếm số cầu và khớp.int n, m, time_dfs, cnt_bridge,cnt_articulation, low[maxn], number[maxn];int is_articulation[maxn], cnt_child[maxn], par[maxn]; vector <int> adj[maxn];voidenter(){ cin >> n >> m;for(int i =1; i <= M;++i){int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u);}}voiddfs(int u){ low[u]= number[u]=++time_dfs;for(int v: adj[u]){if(v == par[u])continue;// Đỉnh v chưa thăm thì thăm nó và gắn cha của nó bằng u.if(!number[v]){ par[v]= u;++cnt_child[u];dfs(v); low[u]=min(low[u], low[v]);// Cực tiểu hóa low[u].if(low[v]== number[v])// cung (u, v) là cầu.++cnt_bridge;// u là chốt và u có nhiều hơn 1 nhánh con => u là khớp.if(par[u]==-1){if(cnt_child[u]>=2) is_articulation[u]=1;}// u là khớp nếu không có cung ngược hoặc cung chéo đi ra từ nhánh DFS gốc u.elseif(low[v]>= number[u]){ is_articulation[u]=1;}}else{// Cực tiểu hóa low[u] theo number[v] nếu v đã thăm. low[u]=min(low[u], number[v]);}}}voidsolution(){fill(par +1, par +1+ n,-1);for(int u =1; u <= n;++u)if(!number[u])dfs(u);for(int u =1; u <= n;++u) cnt_articulation += is_articulation[u]; cout << cnt_articulation <<' '<< cnt_bridge;}main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);enter();solution();return0;}

2. Bài toán ví dụ

2.1. Bài toán 1

Nguồn bài:https://bit.ly/3Ft6bWe.

Tóm tắt đề bài: Cho đơn đồ thị vô hướng liên thông GGG gồm nnn đỉnh, mmm cạnh (1≤n≤1000,1≤m≤10000)(1 le n le 1000, 1 le m le 10000)(1≤n≤1000,1≤m≤10000). Cần định chiều lại các cạnh của đồ thị thành một chiều, sao cho đồ thị mới vẫn liên thông và số lượng cạnh hai chiều còn lại là ít nhất có thể?

Ý tưởng:

• Áp dụng giải thuật DFStext{DFS}DFS kết hợp với phép định chiều đồ thị, khi xét tới cạnh (u,v)(u, v)(u,v) thì bỏ luôn chiều (v→u)(v rightarrow u)(v→u) và định chiều nó thành cung (u→v)(u rightarrow v)(u→v).
• Tuy nhiên, đối với các cạnh là cầu của đồ thị, việc định chiều lại nó sẽ làm mất tính liên thông của đồ thị. Do đó, nếu sau khi duyệt xong nhánh DFStext{DFS}DFS gốc vvv mà thấy cạnh (u,v)(u, v)(u,v) là một cầu thì ta sẽ khôi phục lại chiều (v→u)(v rightarrow u)(v→u) cho nó để giữ lại cạnh hai chiều.

Cài đặt:

#include<bits/stdc++.h>#defineintlonglong#definetask"StreetDirection."#defineinf1e9+7#definexfirst#defineysecondusingnamespace std;constint maxn =1001;int n, m, time_dfs, testcase, low[maxn], num[maxn];bool adj[maxn][maxn];voidreset_data(int n){memset(adj,false,sizeof(adj));fill(low +1, low +1+ n,0);fill(num +1, num +1+ n,0); time_dfs =0;}voidenter(){ cin >> n >> m;reset_data(n);for(int i =1; i <= m;++i){int u, v; cin >> u >> v; adj[u][v]=true; adj[v][u]=true;}}voiddfs(int u,int par){ low[u]= num[u]=++time_dfs;for(int v =1; v <= N;++v){if(v == par ||!adj[u][v])continue; adj[v][u]=false;// Bỏ luôn chiều (v -> u), định chiều cạnh (u - v) thành cung (u -> v).if(!num[v]){dfs(v, u); low[u]=min(low[u], low[v]);// Cạnh (u, v) là cầu thì phải giữ nguyên 2 chiều để đảm bảm tính liên thông.if(low[v]== num[v]) adj[v][u]=true;}else{ low[u]=min(low[u], num[v]);}}}voidsolution(){for(int u =1; u <= n;++u)if(!num[u])dfs(u,-1); cout <<++testcase << endl << endl;// In ra các cạnh được định chiều lại thành u -> v.for(int u =1; u <= n;++u)for(int v =1; v <= n;++v)if(adj[u][v]) cout << u <<' '<< v << endl; cout <<"#n";}main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);while(true){enter();if(n ==0&& m ==0)break;solution();}return0;}

2.2. Bài toán 2

Nguồn bài:https://bit.ly/3AAbtvj.

Tóm tắt đề bài: Cho một đa đồ thị vô hướng GGG gồm nnn đỉnh, mmm cạnh (1≤n≤100,1≤m≤5000)(1 le n le 100, 1 le m le 5000)(1≤n≤100,1≤m≤5000). Độ kết dính giữa một cặp đỉnh (u,v)(u, v)(u,v) bất kỳ là số lượng cạnh mà nếu bỏ đi sẽ khiến cho hai đỉnh này không còn liên thông nữa. Hãy tính tổng độ kết dính của mọi cặp đỉnh?

Ý tưởng:

• Với mọi cặp đỉnh (u,v)(u, v)(u,v) của đồ thị, ta cần quan tâm tới số cạnh cầu trên đường đi từ uuu tới vvv. Những cạnh này khi bỏ đi sẽ làm uuu và vvv mất tính liên thông.
• Đặt nchildren[u]n_text{children}[u]nchildren​[u] là số đỉnh thuộc nhánh DFStext{DFS}DFS gốc uuu. Ta xây dựng trong quá trình dựng cây DFS bằng công thức QHĐ đơn giản: nchildren[u]=∑nchildren[v],n_text{children}[u] = sum n_text{children}[v],nchildren​[u]=∑nchildren​[v], với vvv là con của uuu và nhánh DFStext{DFS}DFS gốc uuu đã duyệt xong.
• Đề bài yêu cầu in ra tổng độ kết dính, tức là tổng số cạnh cầu trên đường đi của mọi cặp đỉnh (u,v)(u, v)(u,v). Như vậy ta có thể thay đổi cách tính: Với mỗi cạnh cầu (u,v)(u, v)(u,v) của đồ thị, số cặp đỉnh phải đi qua cầu này sẽ là:

f(u,v)=nchildren[v]∗(n−nchildren[v])f(u, v) = n_text{children}[v] * (n – n_text{children}[v]) f(u,v)=nchildren​[v]∗(n−nchildren​[v])

(Các đỉnh trong nhánh DFStext{DFS}DFS gốc vvv đi tới các đỉnh không thuộc nhánh DFStext{DFS}DFS gốc vvv)

• Tổng tất cả các giá trị f(u,v)f(u, v)f(u,v) với mọi cạnh cầu sẽ là kết quả bài toán.

Cài đặt:

#include<bits/stdc++.h>#defineintlonglong#definetask"Weather."#defineinf1e9+7#definexfirst#defineysecondusingnamespace std;constint maxn =101;int res, time_dfs, low[maxn], num[maxn], n_children[maxn]; vector <int> adj[maxN];voidenter(){ cin >> n >> m;for(int i =1; i <= m;++i){int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u);}}voiddfs(int u,int par){ num[u]= low[u]=++time_dfs;// Tăng số thứ tự duyệt của đỉnh u. n_children[u]=1;// Ban đầu nhánh DFS gốc u chỉ có chính nó.for(int v: adj[u]){if(v == par)continue;if(!num[v]){dfs(v, u); low[u]=min(low[u], low[v]);// Đếm số con nhánh cây DFS gốc u sau khi đã duyệt xong nhánh DFS gốc u. n_children[u]+= n_children[v];// Nếu cung (u, v) là một cạnh cầu.if(low[v]== number[v]) res += n_children[v]*(n - n_children[v]);}else{ low[u]=min(low[u], num[v]);}}}voidsolution(){// Duyệt qua các đỉnh của đồ thị, đỉnh nào chưa thăm thì dựng cây DFS từ đỉnh đó.for(int u =1; u <= n;++u)if(!number[u])dfs(u,-1); cout << res;}main(){enter();solution();return0;}