Khớp và cầu trong đồ thị: hiểu tin, low qua DFS

Xóa một cạnh hoặc một đỉnh thì mạng có bị tách?

Trong một mạng vô hướng, một tuyến duy nhất nối hai vùng là điểm yếu: bỏ tuyến đó làm hai vùng không còn liên lạc. Cạnh có tính chất này gọi là cầu. Nếu một nút trung chuyển bị bỏ làm mạng tách thêm thành phần, nút đó gọi là đỉnh khớp.

Định nghĩa chính xác cần so số thành phần liên thông. Đồ thị ban đầu có thể đã rời rạc, nên không thể dùng câu “xóa xong mà đồ thị không liên thông” để kết luận. Phải kiểm số thành phần sau khi xóa có lớn hơn số thành phần trước hay không. Xóa một đỉnh nghĩa là xóa cả đỉnh đó và mọi cạnh kề.

Cách vét cạn thử xóa từng cạnh rồi duyệt lại dễ hiểu nhưng tốn O(m(n+m)). Thử xóa từng đỉnh cũng phải duyệt nhiều lần. DFS cho phép gom thông tin đường vòng vào low, nhờ đó chỉ cần một quá trình duyệt tuyến tính.

tin và low lưu hai loại thông tin khác nhau

tin[u] là thời điểm phát hiện đỉnh u trong DFS. Đồng hồ tăng mỗi khi thấy một đỉnh mới, nên tổ tiên trong cây DFS có tin nhỏ hơn hậu duệ. Cạnh lần đầu dẫn tới một đỉnh chưa gặp trở thành cạnh cây; các kết nối còn lại cung cấp đường quay về phần đã gặp.

low[u] là thời điểm nhỏ nhất có thể chạm tới từ cây con DFS của u bằng các cạnh đi xuống trong cây rồi nhiều nhất một cạnh quay lại, không dùng chính cạnh cha để quay về. Ban đầu low[u]=tin[u]. Sau khi duyệt xong con v, gộp low[v] vào low[u]. Với cạnh tới đỉnh đã gặp v khác cạnh cha, thử tin[v].

Ý nghĩa cần giữ là cây con có đường thoát lên cao tới đâu. Không phải low là khoảng cách, nhãn nhóm hay số đỉnh trong cây con. Nếu chỉ học thuộc hai dấu so sánh mà không hiểu đường thoát đó, rất dễ dùng nhầm >= cho cầu.

Tại sao cạnh cầu dùng dấu lớn hơn nghiêm ngặt?

Xét cạnh cây u–v, với u là cha của v. Nếu low[v] > tin[u], cây con của v không có đường vòng về u hoặc một tổ tiên của u. Xóa cạnh u–v sẽ tách toàn bộ cây con này ra, nên đó là cầu.

Nếu low[v] bằng tin[u], có đường khác từ cây con về chính u. Khi xóa cạnh cây, đường đó vẫn còn nối hai phía. Vì vậy, trường hợp bằng nhau không được tính cầu. Một ví dụ rõ là hai cạnh song song giữa u và v: một cạnh là cạnh cha, cạnh còn lại vẫn đưa v về u.

Đây cũng là lý do code lưu ID từng cạnh. Khi ở v, chỉ bỏ đúng ID cạnh đã dùng từ cha tới v, không bỏ mọi cạnh có đầu còn lại bằng cha. Nếu bỏ tất cả theo nhãn cha, cạnh song song mất tác dụng và thuật toán có thể báo cầu giả.

Tại sao đỉnh khớp lại dùng lớn hơn hoặc bằng?

Với u không là gốc, nếu có con v mà low[v] >= tin[u], cây con v không có đường tới một tổ tiên thật sự ở phía trên u. Nó có thể vòng về chính u, nhưng khi xóa u thì đường đó cũng mất. Do đó cây con v bị tách khỏi phần phía cha của u, khiến u là khớp.

Gốc DFS không có phần phía cha để so theo lập luận này. Gốc chỉ là khớp khi có ít nhất hai con trực tiếp trong cây DFS. Hai nhánh đó không có đường nối tránh gốc; nếu có, DFS đã đi từ nhánh này sang nhánh kia và chúng không thành hai con tách biệt của gốc.

Đếm con DFS khác đếm số hàng xóm. Trong tam giác, gốc 0 có hai hàng xóm 1 và 2 nhưng chỉ một con DFS nếu duyệt 0 → 1 → 2. Xóa 0 vẫn để 1 và 2 nối nhau, nên 0 không là khớp. Một ngôi sao có gốc ở tâm lại có nhiều con DFS và tâm là khớp.

Chạy tay trên tam giác có đuôi

Theo thứ tự cạnh trong code, DFS đi từ 0 qua 1, 2 rồi quay về, sau đó đi từ 1 sang 3 và 4. tin lần lượt là 0,1,2,3,4. Các giá trị khi kết thúc như sau.

Đỉnh 3 là khớp vì con 4 có low[4] >= tin[3]. Đỉnh 4 không có con nên không là khớp; bỏ một lá không làm số thành phần tăng. Hai đầu của một cầu cũng không nhất thiết đều là khớp, như cạnh 3–4 trong ví dụ này.

Code DFS lặp C++ và Python

#include <algorithm>
#include <iostream>
#include <numeric>
#include <utility>
#include <vector>
using namespace std;
pair<vector<int>,vector<int>> lowlink(int n,const vector<pair<int,int>>& edges){
    vector<vector<pair<int,int>>> g(n);
    for(int id=0;id<(int)edges.size();++id){
        auto [u,v]=edges[id];g[u].push_back({v,id});g[v].push_back({u,id});
    }
    vector<int> tin(n,-1),low(n),par(n,-1),pe(n,-1),it(n,0),children(n,0),bridges;
    vector<bool> cut(n,false);int timer=0;
    for(int root=0;root<n;++root)if(tin[root]==-1){
        vector<int> st={root};tin[root]=low[root]=timer++;
        while(!st.empty()){
            int u=st.back();
            if(it[u]<(int)g[u].size()){
                auto [v,id]=g[u][it[u]++];
                if(id==pe[u])continue;
                if(tin[v]==-1){
                    par[v]=u;pe[v]=id;++children[u];
                    tin[v]=low[v]=timer++;st.push_back(v);
                }else low[u]=min(low[u],tin[v]);
            }else{
                st.pop_back();int p=par[u];
                if(p==-1)cut[u]=children[u]>1;
                else{
                    low[p]=min(low[p],low[u]);
                    if(low[u]>tin[p])bridges.push_back(pe[u]);
                    if(par[p]!=-1 && low[u]>=tin[p])cut[p]=true;
                }
            }
        }
    }
    vector<int> points;for(int u=0;u<n;++u)if(cut[u])points.push_back(u);
    vector<bool> mark(edges.size(),false);
    for(int id:bridges)mark[id]=true;
    bridges.clear();
    for(int id=0;id<(int)mark.size();++id)if(mark[id])bridges.push_back(id);
    return {bridges,points};
}
int main(){
    int n=5,m;vector<pair<int,int>> e={{0,1},{1,2},{2,0},{1,3},{3,4}};
    if(cin>>n>>m){e.resize(m);for(auto& [u,v]:e)cin>>u>>v;}
    auto [b,c]=lowlink(n,e);
    cout<<b.size();for(int id:b)cout<<' '<<id;cout<<'\n';
    cout<<c.size();for(int u:c)cout<<' '<<u;cout<<'\n';
}

import sys

def lowlink(n,edges):
    g=[[] for _ in range(n)]
    for eid,(u,v) in enumerate(edges):
        g[u].append((v,eid));g[v].append((u,eid))
    tin=[-1]*n;low=[0]*n;parent=[-1]*n;pe=[-1]*n
    index=[0]*n;children=[0]*n;cut=[False]*n
    bridges=[];timer=0
    for root in range(n):
        if tin[root]!=-1:
            continue
        stack=[root];tin[root]=low[root]=timer;timer+=1
        while stack:
            u=stack[-1]
            if index[u]<len(g[u]):
                v,eid=g[u][index[u]];index[u]+=1
                if eid==pe[u]:
                    continue
                if tin[v]==-1:
                    parent[v]=u;pe[v]=eid;children[u]+=1
                    tin[v]=low[v]=timer;timer+=1;stack.append(v)
                else:
                    low[u]=min(low[u],tin[v])
            else:
                stack.pop();p=parent[u]
                if p==-1:
                    cut[u]=children[u]>1
                else:
                    low[p]=min(low[p],low[u])
                    if low[u]>tin[p]:
                        bridges.append(pe[u])
                    if parent[p]!=-1 and low[u]>=tin[p]:
                        cut[p]=True
    mark=[False]*len(edges)
    for eid in bridges:
        mark[eid]=True
    return [eid for eid in range(len(edges)) if mark[eid]],[u for u in range(n) if cut[u]]

if __name__=='__main__':
    a=list(map(int,sys.stdin.buffer.read().split()))
    n=5;edges=[(0,1),(1,2),(2,0),(1,3),(3,4)]
    if a:
        n,m=a[:2]
        edges=[tuple(a[2+2*i:4+2*i]) for i in range(m)]
    for row in lowlink(n,edges):
        print(len(row),*row)

Không nhập dữ liệu, dòng đầu in 2 3 4: có hai cầu mang ID 3 và 4. Dòng sau in 2 1 3: có hai đỉnh khớp là 1 và 3. ID cạnh tính từ 0 theo thứ tự nhập, khác nhãn của hai đầu cạnh. Nếu đề muốn in cặp đầu mút, dùng ID để tra lại danh sách cạnh ban đầu.

Input riêng có n, m rồi m cặp u v. Đồ thị vô hướng, chỉ số hợp lệ; cho phép n=0, cạnh song song và cạnh tự nối. Hàm chạy DFS từ mọi gốc chưa thăm nên xử lý toàn bộ đồ thị rời rạc. Các danh sách kết quả được sắp theo ID để dễ đối chiếu, không phụ thuộc thứ tự hoàn thành nhánh.

Bản lặp giữ index[u], vị trí hàng xóm kế tiếp cần xét. Khi còn hàng xóm thì tiếp tục đi sâu; khi hết mới coi là thời điểm trở về từ u, cập nhật low cho cha và kiểm hai điều kiện. Một stack đỉnh đơn giản chỉ đánh dấu khi pop không tự lưu được đầy đủ thời điểm quay lui này.

Vì sao cần xử lý lúc kết thúc con?

Khi vừa phát hiện v, low[v] mới chỉ bằng tin[v]. Những cạnh ở sâu bên dưới có thể đưa nó về một tổ tiên rất cao. Kiểm cầu ngay lúc đẩy v vào stack sẽ dùng thông tin chưa hoàn tất và có thể coi cạnh trong một vòng là cầu.

Mỗi khung DFS cần biết đã xét tới cạnh nào, tương tự vị trí mà lời gọi đệ quy sẽ quay về. Trong code, stack giữ đỉnh còn index nằm ở mảng riêng. Đây là một cách biểu diễn khung; có thể lưu cả đỉnh, cha và iterator trong cùng đối tượng, miễn giữ đúng thứ tự vào nhánh và ra nhánh.

Tránh đệ quy không đồng nghĩa có thể bỏ phân tích bộ nhớ. Vẫn có tối đa O(n) khung đang hoạt động, các mảng tin, low, cha và danh sách kề O(n+m). Mỗi cạnh được xét qua các mục kề, nên phần tìm khớp/cầu là O(n+m). Kết quả cầu được đánh dấu theo ID rồi quét theo thứ tự nhập, nên việc xuất danh sách tăng dần cũng tuyến tính, không cần thêm một bước sắp xếp.

Tự kiểm bằng xóa thật trên đồ thị nhỏ

Để tự kiểm tra trên đồ thị nhỏ, bạn đừng chỉ so sánh hai bản cài đặt Tarjan với nhau: hãy viết một hàm đếm số thành phần liên thông ban đầu, sau đó thử bỏ lần lượt từng cạnh hoặc từng đỉnh xem số thành phần liên thông có tăng lên hay không.

Hãy thử một cạnh nối hai đỉnh: cạnh là cầu nhưng hai đỉnh không là khớp. Thử hai cạnh song song: không cạnh nào là cầu. Thử tam giác: không có khớp/cầu. Thử đường bốn đỉnh: mọi cạnh là cầu, hai đỉnh giữa là khớp. Cuối cùng ghép thêm một thành phần riêng để kiểm định nghĩa tăng số thành phần trên đồ thị rời rạc.

Luyện ngay trên Big-O Coding

Hai bài đầu tách riêng cạnh cầu và đỉnh khớp để luyện đúng điều kiện. Bài phân loại cạnh trong các cây khung nhỏ nhất là phần nâng cao: sau khi gom các cạnh cùng trọng số vào đồ thị phụ phù hợp, cầu giúp nhận ra cạnh bắt buộc. Không chạy lowlink trực tiếp trên đồ thị gốc rồi coi mọi cầu là lời giải đầy đủ cho bài phân loại.

Câu hỏi thường gặp

Nguồn tham khảo

• CP-Algorithms: Bridges
• CP-Algorithms: Articulation points
• Open Data Structures: Graph Traversal