Thành phần liên thông mạnh: Kosaraju và ý tưởng Tarjan

Có đường đi một chiều chưa đủ chung nhóm

Trên đồ thị vô hướng, chỉ cần một đường nối là hai đỉnh thuộc cùng thành phần liên thông. Trên đồ thị có hướng, u đi được tới v không bảo đảm v quay về u. Vì vậy cần một cách phân nhóm giữ đúng điều kiện hai chiều thay vì bỏ hướng rồi dùng DSU.

SCC là tập đỉnh lớn nhất theo quan hệ đi tới nhau hai chiều. Quan hệ này có tính bắc cầu: nếu u với v đi tới nhau được, v với w cũng đi tới nhau được, ta ghép các đoạn để đi giữa u và w. Vì thế mỗi đỉnh thuộc đúng một nhóm và các nhóm không chồng lấn.

Một đỉnh đứng riêng vẫn là một SCC ngay cả khi không có cạnh tự nối: đường đi độ dài 0 cho phép nó tới chính nó. Một chu trình có hướng thường nằm trong một SCC, nhưng một SCC có thể chứa nhiều chu trình và nhiều cạnh phức tạp hơn một vòng đơn.

Kosaraju nhìn đồ thị hai lần

Bước một chạy DFS trên đồ thị gốc và ghi đỉnh vào order khi kết thúc, sau khi đã xét xong mọi cạnh đi ra. Bước hai đảo hướng tất cả cạnh. Bước ba xét các đỉnh theo thứ tự kết thúc giảm dần, mỗi lần DFS trên đồ thị đảo từ một đỉnh chưa có nhóm thì gom được đúng một SCC.

Hai chữ “kết thúc” không thể thay bằng “phát hiện”. Thứ tự hậu duyệt chứa thông tin nhánh nào đã xử lý xong và quan hệ giữa các nhóm. Một stack chỉ pop đỉnh rồi ghi ngay, không mô phỏng thời điểm trở về, có thể tạo thứ tự sai.

Trong code, lượt đầu dùng khung (đỉnh, vị trí cạnh tiếp theo). Khi còn cạnh chưa xét thì đi sâu; hết cạnh mới ghi đỉnh vào order. Lượt hai chỉ cần gom khả năng đi tới nên dùng stack đỉnh đơn giản và đánh dấu nhóm ngay khi đưa vào stack.

Chạy tay thứ tự kết thúc và nhóm

Theo thứ tự cạnh của ví dụ, lượt đầu bắt đầu ở 0, đi 0 → 1 → 2, gặp cạnh về 0 đã thăm, rồi qua 3 → 4. Cạnh 4 → 3 quay về đỉnh đã gặp. Ta lần lượt kết thúc 4,3,2,1,0. Sau đó đỉnh 5 đứng riêng kết thúc cuối.

Kết quả có ba nhóm và dãy ID theo nhãn đỉnh là [1,1,1,2,2,0]. Nếu thay thứ tự nhập cạnh hoặc thứ tự duyệt gốc, các ID có thể khác mà cách phân chia vẫn đúng. So đáp án bằng nhãn nhóm cố định là lỗi kiểm thử phổ biến.

Vì sao lượt hai không tràn sang nhóm khác?

Nén tạm từng SCC thành một đỉnh để nhìn quan hệ giữa các nhóm. Nếu có cạnh từ nhóm A sang B, thời điểm kết thúc lớn nhất của A lớn hơn của B trong lượt DFS thích hợp trên đồ thị gốc. Khi chọn nhóm còn lại có thời điểm kết thúc lớn nhất rồi duyệt trên đồ thị đảo, ta không thể đi sang một nhóm chưa xử lý đứng trước nó theo quan hệ này.

Bên trong cùng SCC, đảo cạnh vẫn giữ khả năng đi tới nhau hai chiều. Do đó lượt hai vừa không bỏ sót thành viên của nhóm đang xét, vừa không kéo thêm thành viên của nhóm khác chưa chốt. Đây là ý nghĩa của việc phối hợp đúng thứ tự kết thúc và đúng chiều đồ thị.

Có một phiên bản tương đương đổi vai trò hai đồ thị: lượt đầu trên đồ thị đảo rồi lượt hai trên đồ thị gốc với thứ tự phù hợp. Không trộn một nửa của phiên bản này với một nửa của phiên bản kia rồi bỏ bước kiểm chứng.

Tarjan khác ở đâu?

Tarjan tìm SCC trong một DFS bằng tin, lowlink và một stack riêng. Khi thăm u, đưa u vào stack các đỉnh chưa được chốt nhóm. Cạnh cây truyền thông tin từ con về cha. Với cạnh tới một đỉnh v đã thăm nhưng vẫn còn trên stack SCC, dùng tin[v] để cập nhật lowlink[u]. Nếu v đã ra khỏi stack và thuộc một nhóm chốt rồi, cạnh đó không kéo lowlink về nhóm cũ.

Khi lowlink[u] bằng tin[u], u là điểm bắt đầu của một SCC cần chốt. Lấy lần lượt các đỉnh khỏi stack SCC tới khi lấy cả u, gán chúng cùng nhóm. Stack SCC khác stack lời gọi DFS: một đỉnh có thể đã kết thúc lời gọi nhưng vẫn cần nằm chờ trong stack SCC cho tới khi cả nhóm được xác định.

Đừng sao chép nguyên low của bài cầu vô hướng sang đây. Trong bài cầu, ta bỏ đúng cạnh cha và xét đường quay lại trong cấu trúc vô hướng. Trong Tarjan SCC, điều kiện còn trên stack là thiết yếu để không gộp sai các nhóm có cạnh một chiều.

Bài này chọn code Kosaraju lặp để học rõ thời điểm kết thúc và tránh độ sâu đệ quy. Phần Tarjan giải thích nguyên lý để bạn so sánh và học tiếp, không có nghĩa tệp code bên dưới đang chạy đồng thời cả hai thuật toán.

Code C++ và Python

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
pair<int,vector<int>> kosaraju(int n,const vector<pair<int,int>>& edges){
    vector<vector<int>> g(n),rev(n);
    for(auto [u,v]:edges){g[u].push_back(v);rev[v].push_back(u);}
    vector<bool> seen(n,false);vector<int> order;
    for(int root=0;root<n;++root)if(!seen[root]){
        vector<pair<int,int>> st={{root,0}};seen[root]=true;
        while(!st.empty()){
            int u=st.back().first;
            if(st.back().second<(int)g[u].size()){
                int v=g[u][st.back().second++];
                if(!seen[v]){seen[v]=true;st.push_back({v,0});}
            }else{order.push_back(u);st.pop_back();}
        }
    }
    vector<int> comp(n,-1);int count=0;
    reverse(order.begin(),order.end());
    for(int root:order)if(comp[root]==-1){
        vector<int> st={root};comp[root]=count;
        while(!st.empty()){
            int u=st.back();st.pop_back();
            for(int v:rev[u])if(comp[v]==-1){comp[v]=count;st.push_back(v);}
        }
        ++count;
    }
    return {count,comp};
}
int main(){
    int n=6,m;vector<pair<int,int>> e={{0,1},{1,2},{2,0},{2,3},{3,4},{4,3}};
    if(cin>>n>>m){e.resize(m);for(auto& [u,v]:e)cin>>u>>v;}
    auto [count,comp]=kosaraju(n,e);cout<<count<<'\n';
    for(int x:comp){cout<<x<<' ';}
    cout<<'\n';
}

import sys

def kosaraju(n,edges):
    g=[[] for _ in range(n)];rev=[[] for _ in range(n)]
    for u,v in edges:
        g[u].append(v);rev[v].append(u)
    seen=[False]*n;order=[]
    for root in range(n):
        if seen[root]:
            continue
        stack=[(root,0)];seen[root]=True
        while stack:
            u,index=stack[-1]
            if index<len(g[u]):
                v=g[u][index];stack[-1]=(u,index+1)
                if not seen[v]:
                    seen[v]=True;stack.append((v,0))
            else:
                order.append(u);stack.pop()
    comp=[-1]*n;count=0
    for root in reversed(order):
        if comp[root]!=-1:
            continue
        stack=[root];comp[root]=count
        while stack:
            u=stack.pop()
            for v in rev[u]:
                if comp[v]==-1:
                    comp[v]=count;stack.append(v)
        count+=1
    return count,comp

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

Không nhập dữ liệu, dòng đầu in 3; dòng sau là 1 1 1 2 2 0. Input riêng có n, m rồi m cặp u v biểu diễn cạnh có hướng. n có thể bằng 0; mọi chỉ số cạnh hợp lệ. Cạnh song song và cạnh tự nối đều được phép.

Code lưu đồ thị gốc và đồ thị đảo, cộng các mảng seen, order, comp và stack. Mỗi lượt duyệt đỉnh, cạnh một số lần hằng số, nên O(n+m) thời gian và O(n+m) bộ nhớ. Dù có hai bản danh sách kề, cận tiệm cận vẫn tuyến tính; khi ước lượng dung lượng thực tế thì phải tính cả hai bản.

Nén SCC để tạo DAG và làm tiếp

Sau khi có comp[u], duyệt mỗi cạnh u → v. Nếu hai ID khác nhau, thêm cạnh comp[u] → comp[v] vào đồ thị nén. Bỏ các cạnh trong cùng nhóm. Nếu cần đếm số cạnh hoặc bậc theo quan hệ phân biệt, phải loại cạnh trùng theo yêu cầu; nếu chỉ cần duyệt hoặc tính cực trị, cạnh trùng có thể vẫn xử lý được nhưng cần phân tích rõ.

Đồ thị nén không có chu trình: nếu các nhóm A,B,C nối thành một vòng có hướng, từ mỗi nhóm đều đi được tới các nhóm còn lại và quay về, nên chúng đáng lẽ phải là cùng một SCC. Mâu thuẫn này chứng minh tính DAG và cho phép dùng tô-pô hoặc quy hoạch động trên nhóm.

Không phải mọi bài tối ưu đều được giải bằng cộng hết giá trị trong mỗi SCC rồi lấy đường trên DAG. Cách tổng hợp bên trong nhóm phụ thuộc luật đi lại, giá trị được lấy mấy lần và tài nguyên có bị giới hạn không. SCC chỉ cung cấp cấu trúc đi tới hai chiều; phần mô hình hóa mục tiêu vẫn cần chứng minh riêng.

Kiểm nhóm bằng khả năng đi tới độc lập

Để tự kiểm tra trên đồ thị nhỏ, bạn có thể tìm ma trận đường đi giữa mọi cặp đỉnh bằng BFS/DFS từ từng đỉnh, rồi xác nhận hai đỉnh u, v nhận cùng mã SCC khi và chỉ khi u đi tới được v đồng thời v đi tới được u. Cách kiểm tra này độc lập với thứ tự đánh số SCC của từng thuật toán.

Tự thử một chuỗi 0 → 1 → 2: có ba SCC dù đồ thị nối được nếu bỏ hướng. Thêm 2 → 0 thì cả ba gộp thành một. Thử hai chu trình chỉ có một cạnh nối một chiều: vẫn hai nhóm. Thêm cạnh từ nhóm sau quay về nhóm trước thì chúng có thể gộp lại. Đừng quên đỉnh cô lập và n=0.

Luyện ngay trên Big-O Coding

Bài tìm SCC luyện trực tiếp cách chia nhóm. Bài phân chia SCC và tối ưu chi phí là phần mở rộng: cần nén đồ thị, xác định thông tin giữ ở mỗi nhóm rồi mới giải bài tối ưu. Hãy kiểm cách phân nhóm riêng trên đồ thị nhỏ trước khi ghép bước xử lý trên DAG.

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

Nguồn tham khảo

• CP-Algorithms: SCC and condensation
• Princeton Algorithms: Kosaraju–Sharir SCC
• Princeton Algorithms: Tarjan SCC