Nền tảng và Khái niệm Cơ bản

Để hiểu sâu về thuật toán Tarjan, chúng ta cần nắm vững cấu trúc của cây tìm kiếm (DFS Tree) trên đồ thị. Cần phân biệt rõ ràng giữa đồ thị gốc và cây sinh ra từ quá trình duyệt DFS. Hai mảng quan trọng nhất trong quá trình thực thi là:

• disc[u]: Lưu trữ thời điểm lần đầu tiên truy cập vào đỉnh u.
• low[u]: Giá trị nhỏ nhất của thời gian truy cập mà đỉnh u có thể đạt được thông qua các cạnh ngược hoặc cạnh của cây con.

Công thức tính giá trị low[u] được xác định bởi min của tập hợp bao gồm: thời gian truy cập của chính u, và các giá trị tham chiếu ngược lại từ cây con đã duyệt.

Vấn đề với Đồ thị Vô hướng

Cầu và Thành phần Liên thông Hai Cạnh (e-DCC)

Cầu (Bridge)

Trong một đồ thị vô hướng, nếu việc loại bỏ một cạnh cụ thể làm đồ thị tách thành hai hoặc nhiều thành phần rời rạc, cạnh đó được gọi là cầu hay cạnh cắt. Điều kiện xác định: Một cạnh nối từ u sang v là cầu khi và chỉ khi:

low[v] > disc[u]

Rõ ràng, tất cả các cầu đều nằm trên cây DFS. Các cạnh thuộc chu trình đơn giản chắc chắn không phải là cầu. Khi thực hiện duyệt, ta cần lưu ID của cạnh đến để tránh đi ngược lại ngay lập tức qua cùng một cạnh trong đồ thị vô hướng (xử lý đa đồ thị hoặc cạnh song song). Mẫu code tối ưu:

// Khởi tạo ban đầu ecnt = 1
void findBridges(int u, int edgeFromParent) {
    disc[u] = low[u] = ++timerCount;
    
    for (int idx = head[u]; idx != 0; idx = edges[idx].next) {
        int v = edges[idx].target;
        
        if (disc[v] == 0) {
            findBridges(v, idx);
            low[u] = min(low[u], low[v]);
            
            if (low[v] > disc[u]) {
                markBridge(idx);
                markBridge(idx ^ 1); // Đánh dấu cạnh vô hướng song song
            }
        } else if (idx != (edgeFromParent ^ 1)) {
            low[u] = min(low[u], disc[v]);
        }
    }
}

Thành phần Liên thông Hai Cạnh (e-DCC)

Một đồ thị vô hướng liên thông được gọi là liên thông hai cạnh nếu nó không chứa cầu nào. Tập con lớn nhất thỏa mãn tính chất này gọi là thành phần liên thông hai cạnh. Tính chất: Một đồ thị vô hướng là e-DCC khi và chỉ khi mọi cạnh của nó đều thuộc ít nhất một chu trình đơn giản. Cách xử lý: Sau khi xác định được các cầu, xóa chúng khỏi đồ thị sẽ chia đồ thị thành các thành phần độc lập. Chúng ta có thể co mỗi thành phần này thành một nút duy nhất. Kết quả là một rừng các cây (không còn chu trình).

bool visitedCheck[N];
int componentId[N];
int componentSize[N];
int compCount = 0;

// Hàm DFS gán nhãn thành phần
void assignComponent(int u) {
    visitedCheck[u] = true;
    componentId[u] = compCount;
    componentSize[compCount]++;
    
    for (int idx = head[u]; idx != 0; idx = edges[idx].next) {
        int v = edges[idx].target;
        // Nếu đã thăm hoặc cạnh bị coi là cầu thì bỏ qua
        if (visitedCheck[v] || isBridge[idx]) continue; 
        assignComponent(v);
    }
}

// Trong hàm main()
for (int i = 1; i <= n; ++i) {
    if (!disc[i]) findBridges(i, 0);
}

memset(visitedCheck, false, sizeof(visitedCheck));
for (int i = 1; i <= n; ++i) {
    if (!visitedCheck[i]) {
        compCount++;
        assignComponent(i);
    }
}
// Xây dựng đồ thị mới dựa trên thành phần
vector<int> newAdj[N];
for (int i = 2; i <= ecnt; i += 2) {
    if (isBridge[i]) {
        int uRoot = componentId[edges[i].target];
        int vRoot = componentId[edges[i^1].target];
        newAdj[uRoot].push_back(vRoot);
        newAdj[vRoot].push_back(uRoot);
    }
}

Ứng dụng điển hình: Tìm đường đi bắt buộc trong đồ thị vô hướng. Một cạnh là bắt buộc nếu việc xóa nó khiến hai điểm trở nên không liên thông (tức là cạnh đó là cầu). Có thể dùng kỹ thuật Co điểm kết hợp với Chain Decomposition (Nối chuỗi) để tính khoảng cách nhanh.

Điểm Khớp và Thành phần Liên thông Hai Đỉnh (v-DCC)

Điểm Khớp (Articulation Point)

Xóa một đỉnh và tất cả các cạnh nối với nó khiến đồ thị vô hướng tăng số lượng thành phần liên thông, đỉnh đó là điểm khớp. Điều kiện xác định:

• low[v] >= disc[u]
• Nếu u không phải là gốc: Nếu tồn tại con v sao cho không có cạnh đi ngược lên tổ tiên của u, thì u là điểm khớp.
• Nếu u là gốc: Nó là điểm khớp nếu có nhiều hơn 1 nhánh cây DFS xuất phát từ nó.

Lưu ý: Sử dụng toán tử ≥ giúp đảm bảo rằng dù ta cập nhật low bằng disc của cha, đỉnh vẫn được nhận diện đúng nếu điều kiện chặt chẽ hơn xảy ra.

int cutVertexCount = 0;
bool isArticulationPoint[N];

void findArticulationPoints(int u, bool isRoot) {
    disc[u] = low[u] = ++timerCount;
    int childrenInTree = 0;
    
    for (int idx = head[u]; idx != 0; idx = edges[idx].next) {
        int v = edges[idx].target;
        
        if (disc[v] == 0) {
            childrenInTree++;
            findArticulationPoints(v, false);
            low[u] = min(low[u], low[v]);
            
            if (!isRoot && low[v] >= disc[u]) {
                markAsCut(u);
            }
        } else {
            low[u] = min(low[u], disc[v]);
        }
    }
    
    if (isRoot && childrenInTree > 1) {
        markAsCut(u);
    }
}

Ví dụ bài toán: Cho đồ thị, hỏi khi khóa một điểm, có bao nhiêu cặp (x, y) không thể đến nhau. Nếu điểm không phải là điểm khớp, số lượng cặp giảm đi 2 * (n - 1). Nếu là điểm khớp, đồ thị tách thành nhiều mảnh, tính tích kích thước các mảnh cộng với phần còn lại.

Thành phần Liên thông Hai Đỉnh (v-DCC)

Đồ thị không chứa điểm khớp gọi là liên thông hai đỉnh. Lưu ý: Một điểm khớp có thể thuộc nhiều thành phần v-DCC khác nhau, nhưng các điểm không phải điểm khớp chỉ thuộc đúng một thành phần. Cơ chế tìm kiếm: Sử dụng ngăn xếp (stack) để lưu các đỉnh đang duyệt. Khi gặp điều kiện low[v] >= disc[u], ta trích xuất từ stack cho đến khi lấy ra được đỉnh v. Đỉnh u cũng được đưa vào thành phần này. Xây dựng đồ thị mới (Co điểm): Do điểm khớp có thể lặp lại ở nhiều thành phần, kỹ thuật co điểm thường nhân bản điểm khớp thành một nút trung gian để chuyển đổi thành cây.

stack<int> pointStack;
vector<int> dccList[MAX_DCC];

void buildDcc(int u) {
    disc[u] = low[u] = ++timerCount;
    pointStack.push(u);
    
    for (int idx = head[u]; idx != 0; idx = edges[idx].next) {
        int v = edges[idx].target;
        
        if (disc[v] == 0) {
            buildDcc(v);
            low[u] = min(low[u], low[v]);
            
            if (low[v] >= disc[u]) {
                int tempNode;
                vector<int> currentDcc;
                
                do {
                    tempNode = pointStack.top();
                    pointStack.pop();
                    currentDcc.push_back(tempNode);
                } while (tempNode != v);
                
                currentDcc.push_back(u);
                dccList[++dccCounter] = currentDcc;
            }
        } else {
            low[u] = min(low[u], disc[v]);
        }
    }
}

Khôi phục cạnh trong v-DCC: Để biết cạnh nào thuộc v-DCC nào, ta cần theo dõi ngăn xếp cạnh tương tự như ngăn xếp đỉnh. Mỗi cạnh được đẩy vào ngăn xếp khi bắt đầu duyệt và rút ra khi hoàn thành một thành phần.

Vấn đề với Đồ thị Có hướng

Thuật toán Tarjan và Thành phần Liên thông Mạnh (SCC)

Với đồ thị có hướng, mục tiêu là tìm các nhóm đỉnh mà bất kỳ cặp nào trong nhóm đều có đường đi qua lại lẫn nhau. Các điểm chú ý:

1. Kiểm tra nếu đỉnh đích chưa từng được truy cập, tiếp tục DFS.
2. Nếu đỉnh đích đang nằm trong ngăn xếp (chưa thuộc SCC nào), cập nhật low theo disc của đỉnh đích.
3. Khi low[u] == disc[u], toàn bộ nội dung từ đỉnh u trở lên trong stack tạo thành một SCC.

void findSCC(int u) {
    disc[u] = low[u] = ++timerCount;
    stackNodes.push(u);
    inStack[u] = true;
    
    for (int idx = head[u]; idx != 0; idx = edges[idx].next) {
        int v = edges[idx].target;
        
        if (disc[v] == 0) {
            findSCC(v);
            low[u] = min(low[u], low[v]);
        } else if (inStack[v]) {
            low[u] = min(low[u], disc[v]);
        }
    }
    
    if (low[u] == disc[u]) {
        sccCount++;
        int currentNode;
        do {
            currentNode = stackNodes.top();
            stackNodes.pop();
            inStack[currentNode] = false;
            sccId[currentNode] = sccCount;
        } while (currentNode != u);
    }
}

Sau khi tìm được SCC, việc co đồ thị sẽ tạo ra một đồ thị hữu hướng không chu trình (DAG), giúp giải quyết các bài toán như sắp xếp topo, đường đi dài nhất, v.v.

Đường đi Bắt buộc trong Đồ thị Có hướng

Trong trường hợp tổng quát, vấn đề này liên quan đến cây chi phối (Dominator Tree). Tuy nhiên, đối với DAG sau khi co SCC, ta có thể sử dụng phương pháp đếm đường đi kết hợp với Hashing để tránh tràn số. Nguyên lý:

1. Tính số đường đi từ nguồn S đến mọi điểm x (fs[x]).
   
2. Tính số đường đi từ mọi điểm x đến đích T (ft[x]) trên đồ thị đảo chiều.
   
3. Bộ tổng đường đi là totalPaths = fs[T].
   
4. Một cạnh (u, v) là bắt buộc nếu fs[u] * ft[v] == totalPaths.
   
5. Một đỉnh u là bắt buộc nếu fs[u] * ft[u] == totalPaths.

Cảnh báo: Số lượng đường đi có thể rất lớn, cần sử dụng phép toán modulo hoặc Hashing kép để đảm bảo độ chính xác cao.

Hướng dẫn chung

• Biên độ dữ liệu: Thường xuyên kiểm tra trường hợp đồ thị chỉ gồm 1 thành phần liên thông để tránh sai sót.
• Cơ chế Pop Stack:
  • Với v-DCC (điểm khớp): Duyệt vòng cho đến khi lấy được v, cuối cùng thêm u.
  • Với SCC (liên thông mạnh): Duyệt vòng cho đến khi lấy được chính u.
• Áp dụng mở rộng: Cấu trúc cây từ v-DCC (thường gọi là Square-Circle Tree) rất hữu ích để giải quyết các bài toán liên quan đến điểm chung trên đường đi.