Skip to content

Dashboard

Một số ứng dụng nâng cao của cây DFS (phần 2)

Created by Admin

III. Bài toán tìm thành phần liên thông mạnh - giải thuật Tarjan

1. Định nghĩa thành phần liên thông mạnh

Đối với đồ thị G=(V,E)G=(V, E) có hướng, ta có ba định nghĩa về tính liên thông:

  • GG được gọi là liên thông mạnh (strongly connected) nếu với mọi cặp đỉnh phân biệt (u,v)(u, v), ta có uu đến được vvvv đến được uu.
  • GG được gọi là liên thông yếu (weakly connected) nếu như đồ thị vô hướng nền của nó là liên thông (tức là hủy bỏ chiều của các cạnh trên đồ thị).
  • GG được gọi là liên thông một phần (unilaterally connected) nếu như với mọi cặp đỉnh phân biệt (u,v),(u, v), có ít nhất một đỉnh đến được đỉnh còn lại.

Như vậy, có thể hiểu một thành phần liên thông mạnh của một đồ thị có hướng là một đồ thị con tối đại liên thông mạnh (nghĩa là nếu thêm vào thành phần liên thông này một tập hợp đỉnh khác sẽ làm mất đi tính liên thông mạnh). Nếu mỗi thành phần liên thông mạnh được co lại thành một đỉnh, thì đồ thị sẽ trở thành một đồ thị có hướng không chu trình. Giải thuật Tarjan là một giải thuật rất được ưa thích để tìm các thành phần liên thông mạnh trên đồ thị.

2. Các định lý quan trọng

Có ba định lý rất quan trọng sử dụng trong quá trình phát triển giải thuật Tarjan:

Định lý 1

Nếu aabb là hai đỉnh thuộc thành phần liên thông mạnh CC thì mọi đường đi từ aa tới bb cũng giống như đường đi từ bb tới aa. Tất cả các đỉnh trung gian trên đường đi đó đều phải thuộc CC.

Chứng minh: Nếu aabb là hai đỉnh thuộc CC thì tức là có một đường đi từ aa đến bb và một đường khác đi từ bb về aa. Suy ra với một đỉnh vv nằm trên đường đi từ aa tới bb thì aa tới được v,vv, v tới được b,b,bb có đường tới aa nên vv cũng tới được aa. Vậy vv nằm trong thành phần liên thông mạnh chứa aa tức là vv thuộc CC. Tương tự với một đỉnh nằm trên đường đi từ bb tới aa.

Định lý 2

Với một thành phần liên thông mạnh CC bất kỳ, sẽ tồn tại một đỉnh rCr∈C sao cho mọi đỉnh của CC đều thuộc nhánh DFS\text{DFS} gốc rr. Đặt đỉnh rr này là đỉnh thăm đầu tiên trong quá trình dfs trên thành phần C,C, ta có rrchốt của CC.

Chứng minh: Trước hết, nhắc lại một thành phần liên thông mạnh là một đồ thị con liên thông mạnh của đồ thị ban đầu thoả mãn tính chất tối đại tức là việc thêm vào thành phần đó một tập hợp đỉnh khác sẽ làm mắt đi tính liên thông mạnh. Trong số các đỉnh của C,C, chọn rr là đỉnh được thăm đầu tiên theo thuật toán tìm kiếm theo chiều sâu. Ta sẽ chứng minh CC nằm trong nhánh DFS\text{DFS} gốc rr. Thật vậy, với một đỉnh vv bất kỳ của C,C, do CC liên thông mạnh nên phải tồn tại một đường đi từ rr tới vv: r=x0,x1,,xk=vr=x_0,x_1,…,x_k=v

Từ định lý 1,1, tất cả các đỉnh x1,x2,,xkx_1,x_2,…,x_k đều thuộc CC nên chúng sẽ phải thăm sau đỉnh rr. Khi hàm DFS(r)\text{DFS}(r) được gọi thì tất cả các đỉnh x1,x2,,xkx_1,x_2,…,x_k đều chưa thăm; vì hàm DFS(r)\text{DFS}(r) sẽ liệt kê tất cả những đỉnh chưa thăm đến được từ rr bằng cách xây dựng nhánh gốc rr của cây DFS,DFS, nên các đỉnh x1,x2,,xk=vx_1,x_2,…,x_k=v sẽ thuộc nhánh gốc rr của cây DFS\text{DFS}. Bởi chọn vv là đỉnh bất kỳ trong CC nên ta có điều phải chứng minh. Đỉnh rr trong chứng minh định lý - đỉnh thăm trước tất cả các đỉnh khác trong CC - gọi là chốt của thành phần CC. Mỗi thành phần liên thông mạnh có duy nhất một chốt. Xét về vị trí trong cây tìm kiếm DFS, chốt của một thành phân liên thông là đỉnh nằm cao nhất so với các đỉnh khác thuộc thành phần đó, hay nói cách khác: là tiền bối của tất cả các đỉnh thuộc thành phần đó.

Định lý 3

Luôn tìm được đỉnh chốt aa thỏa mãn: Quá trình tìm kiếm theo chiều sâu bắt đầu từ aa không thăm được bất kỳ một chốt nào khác (tức là nhánh DFS\text{DFS} gốc aa không chứa một chốt nào ngoài aa). Chẳng hạn, ta chọn a là chốt được thăm sau cùng trong một dây chuyền đệ quy hoặc chọn aa là chốt thăm sau tất cả các chốt khác. Với chốt aa như vậy thì các đỉnh thuộc nhánh DFS\text{DFS} gốc aa chính là thành phần liên thông mạnh chứa aa.

Chứng minh: Với mọi đỉnh vv nằm trong nhánh DFS\text{DFS} gốc a,a, xét bb là chốt của thành phần liên thông mạnh chứa vv. Ta sẽ chứng minh a=ba=b. Thật vậy, theo định lý 2,v2, v phải nằm trong nhánh DFS\text{DFS} gốc bb. Vậy vv nằm trong cả nhánh DFS\text{DFS} gốc aa và nhánh DFS\text{DFS} gốc bb. Giả sử phản chứng rằng aa khác bb thì sẽ có hai trường hợp xảy ra:

  • Trường hợp 11: Nhánh DFS\text{DFS} gốc aa chứa nhánh DFS\text{DFS} gốc b,b, có nghĩa là hàm DFS(b)\text{DFS}(b) sẽ do hàm DFS(a)\text{DFS}(a) gọi tới, điều này mâu thuẫn với giả thiết rằng aa là chốt mà quá trình tìm kiếm theo chiều sâu bắt đầu từ aa không thăm một chốt nào khác.
  • Trường hợp 22: Nhánh DFS\text{DFS} gốc aa nằm trong nhánh DFS\text{DFS} gốc b,b, có nghĩa là aa nằm trên một đường đi từ bb tới vv. Do bbvv thuộc cùng một thành phần liên thông mạnh nên theo định lý 1,a1, a cũng phải thuộc thành phần liên thông mạnh đó. Vậy thì thành phần liên thông mạnh này có hai chốt aabb. Điều này vô lý.

Theo định lý 2,2, ta đã có thành phân liên thông mạnh chứa aa nằm trong nhánh DFS\text{DFS} gốc a,a, theo chứng minh trên ta lại có: Mọi đỉnh trong nhánh DFS\text{DFS} gốc aa nằm trong thành phân liên thông mạnh chứa aa. Kết hợp lại được: Nhánh DFS\text{DFS} gốc aa chính là thành phần liên thông mạnh chứa a.

3. Giải thuật Tarjan

3.1. Ý tưởng

Giải thuật Tarjan có thể phát biểu như sau: Chọn rr là chốt không là tiền bối của một chốt nào khác, chọn lấy thành phần liên thông mạnh thứ nhất là nhánh DFS\text{DFS} gốc rr. Sau đó loại bỏ nhánh DFS gốc rr ra khỏi cây DFS,\text{DFS}, lại tìm thấy một chốt ss khác mà nhánh DFS\text{DFS} gốc ss không chứa chốt nào khác, lại chọn lấy thành phần liên thông mạnh thứ hai là nhánh DFS gốc s,...s,... Tương tự như vậy cho thành phần liên thông mạnh thứ ba, thứ tư, v.v… Có thể hình dung thuật toán Tarjan “bẻ” cây DFS\text{DFS} tại vị trí các chốt để thu được các nhánh rời rạc, mỗi nhánh là một thành phần liên thông mạnh.

Mô hình thuật toán:

void dfs(u)
{
    {Đánh_dấu_đã_thăm_u};
    
    // Duyệt các đỉnh v kề với u.
    for (v in adj[u])
        if {v_chưa_thăm}
            dfs(v);
            
    if {u_là_chốt}
    {
        {Liệt_kê_thành_phần_liên_thông_mạnh_chốt_u};
        {Loại_bỏ_các_đỉnh_đã_liệt_kê_khỏi_đồ_thị};
    }
}

main()
{
    {Đánh_dấu_mọi_đỉnh_v_đều_chưa_thăm};
    
    // Duyệt mọi đỉnh u thuộc tập đỉnh V của đồ thị G.
    for (u in V)
        if (u_chưa_thăm)
            dfs(u);
}

3.2. Xác định một đỉnh có phải là chốt hay không

Ý tưởng thì khá dễ hiểu, tuy nhiên, làm thế nào để xác định được một đỉnh rr có phải là chốt hay không thì lại là câu chuyện khác. Để làm được như thế, ta dựa vào các nhận xét dưới đây:

  • Nhận xét 1: Xét một nhánh DFS\text{DFS} gốc rr. Nếu như trong nhánh này không có cung ngược hoặc cung chéo nào đi ra khỏi nhánh đó thì chắc chắn rr là chốt. Điều này dễ dàng chứng minh bởi vì từ rr ta chỉ đến được các đỉnh thuộc nhánh đó mà thôi, do đó rr là chốt.
  • Nhận xét 2: Nếu từ một đỉnh vv nào đó của nhánh DFS\text{DFS} gốc rr có một cung ngược tới đỉnh ww bất kỳ là cha của rr thì rr không thể là chốt. Bởi vì nếu như vậy, ta sẽ có chu trình: wrvw,w→r→v→w, nên w,r,vw,r,v thuộc cùng một thành phần liên thông mạnh. Mà ww lại được thăm trước r,r, trong khi đang giả sử rr là chốt (đỉnh được duyệt đầu tiên trong TPLT mạnh) nên điều này mâu thuẫn.
  • Nhận xét 3: Trong trường hợp nếu giữa hai nhánh DFS\text{DFS} gốc rr và gốc rr’ tồn tại một cung chéo (v,v),(v,v’), thì rr cũng không thể là chốt. Thật vậy, cung chéo (v,v)(v,v’) này buộc phải đi từ nhánh thăm sau tới nhánh thăm trước (tính chất cây DFS\text{DFS}), tức là nhánh gốc rr’ phải thăm trước nhánh gốc r,r, suy ra vv’ phải thăm trước rrrr’ cũng phải thăm trước rr. Lúc này, tồn tại hai khả năng có thể xảy ra:
    • Nếu rr’ thuộc nhánh DFS\text{DFS} đã duyệt trước r,r, thì rr’ sẽ được duyệt xong trước khi thăm tới rr. Vậy khi quá trình DFS\text{DFS} gọi tới rr thì toàn bộ các đỉnh trong nhánh DFS\text{DFS} gốc rr’ đã được duyệt xong (nói cách khác là đã bị hủy đi), nên sẽ không tiến hành DFS\text{DFS} tiếp từ đỉnh vv sang đỉnh vv’ nữa. Lúc này cung (v,v)(v,v’) bị hủy.
    • Nếu rr’ là cha của rr thì ta có: rr’ tới được r,vr, v lại nằm trong nhánh DFS\text{DFS} gốc rr nên rr đến được v,v,vv đến được vv’ do (v,v)(v,v’) là một cung, vv’ lại đến được rr’ do vv’ thuộc thành phần liên thông mạnh gốc rr’. Như vậy ta có chu trình: rrvvr,r’→r→v→v’→r’, suy ra rrrr’ thuộc cùng một thành phần liên thông mạnh. Mà rr’ đã duyệt trước rr nên rr không thể là một chốt nữa.

Tựu chung lại, đỉnh rr là một chốt khi và chỉ khi không tồn tại cung ngược hoặc cung chéo nối từ nhánh DFS\text{DFS} gốc rr sang một nhánh gốc rr’ khác. Nói cách khác, rr là chốt nếu như không tồn tại cung nối từ nhánh DFS\text{DFS} gốc rr tới một đỉnh đã thăm trước rr.

4. Cài đặt

Dựa vào ý tưởng đánh số các đỉnh trên cây DFS\text{DFS} và ghi nhận cung ngược lên cao nhất, ta có thể kiểm tra được từ một đỉnh uu có tồn tại cung nối thuộc nhánh DFS\text{DFS} gốc uu tới một đỉnh thăm trước uu hay không. Nếu có thì uu sẽ không thể là chốt, ngược lại thì uu là chốt. Cụ thể như sau:

  • Sử dụng mảng num[u]\text{num}[u] là số thứ tự duyệt DFS\text{DFS} của đỉnh uulow[u]\text{low}[u] là giá trị num[]\text{num}[] nhỏ nhất mà từ nhánh DFS\text{DFS} gốc uu có thể tới được bằng một cung (giống với cách xây dựng cây DFS\text{DFS}). Ban đầu tăng num[u]\text{num}[u] lên và khởi gán low[u]=num[u]\text{low}[u] = \text{num}[u] trong quá trình DFS\text{DFS}.
  • Sử dụng thêm mảng \text{is_deleted}[u] để đánh dấu đỉnh uu đã bị loại khỏi đồ thị hay chưa. isdeleted[u]=trueis_\text{deleted}[u] = true nếu uu đã xóa và ngược lại.
  • Dựa vào nhận xét số 3,3, ta có một cách cài đặt tiện lợi sử dụng cấu trúc dữ liệu stack như sau: Khi duyệt xong một nhánh DFS\text{DFS} gốc u,u, trước khi thoát khỏi hàm dfs(u),\text{dfs}(u), ta kiểm tra uu có phải là chốt không bằng cách so sánh low[u]\text{low}[u]num[u]\text{num}[u]. Nếu low[u]=num[u]\text{low}[u] = \text{num}[u] thì từ uu chỉ tới được các đỉnh thuộc nhánh DFS\text{DFS} gốc u,u, từ đó uu là chốt và các đỉnh thuộc nhánh DFS\text{DFS} gốc uu chính là các đỉnh thuộc thành phần liên thông mạnh chốt là uu. Trong quá trình DFS,\text{DFS}, khi thăm tới một đỉnh u,u, ta sẽ đẩy ngay nó vào stack. Như vậy khi duyệt xong đỉnh uu thì các đỉnh thuộc nhánh DFS\text{DFS} gốc uu sẽ nằm liên tiếp ngay cạnh nhau trong stack. Nếu uu là chốt, ta chỉ cần lấy ra các đỉnh này tới khi lấy được đỉnh u,u, toàn bộ các đỉnh đó chính là thành phần liên thông mạnh chứa uu.
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 10;
int cnt_components, time_dfs, number[maxn], low[maxn];
stack < int > vertex;
bool is_deleted[maxn];
vector < int > adj[maxn];

void dfs(int u) // Giải thuật Tarjan
{
    number[u] = ++time_dfs;
    low[u] = num[u];

    for (int v: adj[u])
    {		
        if (is_deleted[v]) // Đỉnh v đã xóa rồi thì bỏ qua.
            continue;
        if (!number[v]) // đỉnh v chưa được đánh số => chưa được thăm.
        {
            dfs(v); // Thăm v.
            low[u] = min(low[u], low[v]); // Cực tiểu hóa low[u].
        }
        else // Nếu v đã thăm.
        {
            low[u] = min(low[u], num[v]); // Cực tiểu hóa low[u] theo num[v].
        }
    }

    // Bắt đầu kiểm tra đỉnh u có phải chốt hay không.
    if (low[u] == num[u]) 
    {
        // In ra chỉ số của thành phần liên thông này.
        cout << "Strongly Connected Component " << ++cnt_components << ": ";
        
        // Liệt kê thành phần liên thông mạnh chốt là u.
        int v;
        do
        {
            v = vertex.top(); // Lấy các đỉnh từ trong stack ra.
            cout << v << ‘ ‘;
            vertex.pop();
            is_deleted[v] = 1;
        }
        while (v != u); // Nếu đã lấy ra chốt u thì kết thúc TPLTM chốt u.
        
        cout << endl;
    }
}

main()
{
    // Nhập dữ liệu đồ thị.
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }
    
    // Duyệt qua các đỉnh, nếu đỉnh nào chưa thăm thì bắt đầu dfs từ đỉnh đó.
    for (int u = 1; u <= N; ++u)
        if (!number[u])
            dfs(u);
}

Giả sử với dữ liệu đồ thị G(V,E)G(V, E) như hình dưới đây:

Chạy chương trình trên sẽ cho ra kết quả:

Strongly Connected Component 1: 7 6 5
Strongly Connected Component 2: 4 3 2
Strongly Connected Component 3: 11 10 9 8
Strongly Connected Component 4: 1

Đánh giá độ phức tạp: Bởi vì giải thuật Tarjan chỉ là sửa đổi một chút từ giải thuật DFS,\text{DFS}, các phép toán vào/ra của ngăn xếp được thực hiện không quá nn lần, nên thời gian thực hiện giải thuật vẫn là O(n+m)O(n + m) trong trường hợp đồ thị được biểu diễn bằng danh sách kề, O(n2)O(n^2) nếu dùng ma trận kề và O(n×m)O(n \times m) nếu dùng danh sách cạnh.

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

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

Tóm tắt đề bài: Cho đa đồ thị có hướng gồm nn đỉnh, mm cạnh (1n105,0m2×105)(1 \le n \le 10^5, 0 \le m \le 2 \times 10^5). Hai đỉnh aabb được gọi là thân thiện nếu như từ aa tới được bb và từ bb cũng tới được aa. Cần thêm vào đồ thị một số cung sao cho các cặp đỉnh thân thiện đều có đường nối trực tiếp với nhau và số cung thêm vào là ít nhất có thể (cung thêm vào không được trùng với các cung đã có)?

Ý tưởng:

  • Nhận xét: Các cặp thành phố thân thiện chỉ có thể là các cặp thành phố nằm trong cùng một TPLT mạnh.
  • Từ nhận xét trên, bước 11 ta tìm các TPLT mạnh của đồ thị, với mỗi TPLT mạnh, số cung tối đa cần thêm là e=k×(k1)e = k \times (k - 1) cung, với kk là số đỉnh thuộc TPLT mạnh đó. Ta sẽ đếm số cung nối trực tiếp đã có sẵn trong TPLT mạnh đó (gọi là dd), tính toán ra số cạnh tối thiểu cần thêm trong TPLT mạnh này là (ed)(e - d).
  • Lưu ý đồ thị đã cho là đa đồ thị, mỗi cặp đỉnh có thể có nhiều cạnh nối trực tiếp, do đó cần lưu ý khi xử lý để không trừ cạnh giữa 22 cặp đỉnh nhiều lần. Ví dụ có 22 cạnh nối từ đỉnh 11 tới đỉnh 22 thì cũng chỉ tính là 11 cung trực tiếp đã có và chỉ trừ đi 11 lần thôi.

Cài đặt:

#include <bits/stdc++.h>
#define int long long
#define task "NewRoads."
#define inf 1e9 + 7
#define x first
#define y second

using namespace std;

const int maxn = 1e5 + 10;
int n, m, time_dfs, minimum_new_roads, cnt_comps;
int par[maxn], component_num[maxn], num[maxn], low[maxn];
bool is_deleted[maxn];
stack < int > vertex;
vector < int > adj[maxn], component[maxn];

void enter()
{
    cin >> N >> M;

    for (int i = 1; i <= M; ++i)
    {
        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
    }
}

// Đếm số cạnh cần thêm trong 1 TPLT mạnh có K đỉnh.
int cntNewRoads(vector < int > component) 
{
    // par[v] = u: Tồn tại một cung (u -> v). Mảng này để kiểm soát các cung nối cùng 1 
    // cặp đỉnh, tránh trừ nhiều lần.
    int k = component.size(), had_directed_edges = 0;

    for (int u: component)
    {
        for (int v: adj[u])
            if (par[v] != u && componentNum[v] == componentNum[u])
            {
                par[v] = u;
                ++had_directed_edges;
            }
    }

    return k * (k - 1) - had_directed_edges;
}

// Xác định các TPLT mạnh bằng giải thuật Tarjan.
void tarjan(int u) 
{
    num[u] = low[u] = ++time_dfs;
    vertex.push(u);

    for (int v: adj[u])
    {
        if (is_deleted[v])
            continue;

        if (num[v])
        {
            low[u] = min(low[u], num[v]);
        }
        else
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
    }

    if (low[u] == num[u])
    {
        vector < int > component_vertexes;
        int v;
        ++cnt_comps;

        do
        {
            v = vertex.top();
            vertex.pop();
            is_deleted[v] = true;
            
            // Nạp đỉnh v vào danh sách các đỉnh trong tplt thứ cnt.
            component_vertexes.push_back(v); 
            // Đánh số hiệu cho v: Nằm trong thành phần liên thông thứ cnt.
            component_num[v] = cnt_comps; 
        }
        while (v != u);

        minimum_new_roads += cnt_new_roads(component_vertexes);
    }
}

void solution()
{
    for (int u = 1; u <= N; ++u)
        if (!num[u])
            tarjan(u);

    cout << minimum_new_roads;
}

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    enter();
    solution();

    return 0;
}

IV. Tài liệu tham khảo

Source: https://viblo.asia/p/mot-so-ung-dung-nang-cao-cua-cay-dfs-phan-2-RQqKLBvpl7z