Sắp xếp tô-pô: xếp việc theo quan hệ phụ thuộc

Tại sao cần xếp thứ tự phụ thuộc?

Muốn chạy một chương trình, bạn cần biên dịch các phần mà nó sử dụng. Muốn học môn nâng cao, bạn cần hoàn thành môn tiên quyết. Những quan hệ này đều có thể viết thành cạnh có hướng: việc đầu phải hoàn thành trước khi việc sau được phép bắt đầu.

Giả sử có năm công việc từ 0 tới 4. Việc 2 cần cả 0 và 1; việc 3 cần 2; việc 4 cần 1. Ta có các cạnh 0 → 2, 1 → 2, 2 → 3 và 1 → 4. Một thứ tự hợp lệ là 0, 1, 2, 4, 3. Thứ tự 1, 4, 0, 2, 3 cũng đúng vì mọi cạnh đều đi từ vị trí trước tới vị trí sau.

Không được hiểu thứ tự tô-pô là đường đi xuyên qua tất cả các đỉnh. Hai công việc đứng cạnh nhau trong danh sách kết quả có thể không có cạnh nối. Danh sách chỉ cần tôn trọng những ràng buộc thật sự có trong đồ thị.

Bậc vào cho biết còn phải đợi ai

Bậc vào của v là số cạnh đi vào v. Ban đầu, bậc vào của năm đỉnh lần lượt là 0, 0, 2, 1, 1. Đỉnh có bậc vào 0 không còn tiền nhiệm chưa xử lý, nên ta được quyền lấy nó ra làm tiếp.

Sau khi hoàn thành u, xem như xóa mọi cạnh u → v. Mỗi cạnh xóa làm bậc vào của v giảm một. Khi bậc vào vừa về 0, đưa v vào hàng đợi. Không được giảm theo số đỉnh đã xử lý chung của toàn đồ thị: chỉ các cạnh đi ra từ u mới bị xóa ở bước đó.

Một bất biến hữu ích là: bậc vào hiện tại bằng số cạnh đến từ các đỉnh chưa lấy ra. Nhờ bất biến này, mỗi đỉnh được thêm vào kết quả khi mọi điều kiện đứng trước nó đã hoàn thành. Đó chính là điều mà đáp án cần thỏa mãn.

Chạy tay thuật toán Kahn

Khởi tạo hàng đợi bằng các đỉnh bậc vào 0 theo thứ tự tăng dần: [0, 1]. Trong bảng, hàng đợi ghi từ đầu tới cuối, còn kết quả chứa các đỉnh đã lấy ra.

Ở bước 3, đỉnh 3 đã sẵn sàng nhưng phải đứng sau đỉnh 4 đang chờ trong FIFO. Điều này hoàn toàn hợp lệ. Nếu đề yêu cầu dãy nhỏ nhất theo thứ tự từ điển, thay hàng đợi bằng min-heap để luôn lấy đỉnh nhỏ nhất trong số các đỉnh đang sẵn sàng; khi đó độ phức tạp có thêm chi phí heap.

Vì sao không lấy đủ đỉnh là có chu trình?

Xét phần đồ thị còn lại sau khi hàng đợi rỗng. Nếu nó vẫn có đỉnh, mọi đỉnh còn lại đều có ít nhất một cạnh đi vào từ phần chưa xử lý. Lần ngược tiền nhiệm mãi trong một tập hữu hạn sẽ gặp lại một đỉnh. Các cạnh đó tạo thành chu trình có hướng.

Chiều ngược lại cũng dễ thấy: trong một chu trình, mỗi đỉnh phải đợi một đỉnh khác của chính chu trình. Không ai có thể trở thành người hoàn thành đầu tiên. Vì vậy, đồ thị có thứ tự tô-pô đầy đủ đúng khi không có chu trình, thường gọi là DAG.

Đừng chỉ kiểm hàng đợi ban đầu có rỗng hay không. Một đồ thị có thể gồm phần DAG xử lý được và một chu trình nằm riêng. Chương trình vẫn in được vài đỉnh rồi mắc lại. Điều kiện cuối phải là số đỉnh đã lấy bằng n, chứ không phải đã từng lấy được ít nhất một đỉnh.

Code C++ và Python

#include <algorithm>
#include <functional>
#include <iostream>
#include <numeric>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
const long long INF=1LL<<60;
vector<int> kahn(int n,const vector<pair<int,int>>&edges){
    vector<vector<int>>adj(n);vector<int>deg(n);
    for(auto[u,v]:edges){adj[u].push_back(v);++deg[v];}
    queue<int>q;for(int i=0;i<n;++i)if(!deg[i])q.push(i);
    vector<int>out;
    while(!q.empty()){int u=q.front();q.pop();out.push_back(u);for(int v:adj[u])if(--deg[v]==0)q.push(v);}
    if((int)out.size()!=n) return {-1};
    return out;
}

int main(){int n=5,m;vector<pair<int,int>>edges={{0,2},{1,2},{2,3},{1,4}};
if(cin>>n>>m){edges.resize(m);for(auto&[u,v]:edges)cin>>u>>v;}
for(auto x:kahn(n,edges)) { cout<<x<<' '; }
cout<<'\n';}

INF=1<<60
def solve(n,edges,s=0):
    from collections import deque
    adj=[[] for _ in range(n)];deg=[0]*n
    for u,v in edges:adj[u].append(v);deg[v]+=1
    q=deque(i for i in range(n) if deg[i]==0);out=[]
    while q:
        u=q.popleft();out.append(u)
        for v in adj[u]:
            deg[v]-=1
            if deg[v]==0:q.append(v)
    return out if len(out)==n else [-1]

if __name__=='__main__':
    import sys
    d=list(map(int,sys.stdin.read().split()))
    if d:
        n,m=d[:2];off=2;s=0 if off==2 else d[2]
        width=2;edges=[tuple(d[i:i+width]) for i in range(off,off+width*m,width)]
    else:
        n,s,edges=5,0,[(0, 2), (1, 2), (2, 3), (1, 4)]
    print(*solve(n,edges,s))

Nếu không nhập dữ liệu, chương trình chạy ví dụ năm đỉnh và in 0 1 2 4 3. Với dữ liệu riêng, nhập n, m rồi m cặp u v, mỗi cặp biểu diễn cạnh có hướng u → v. Đỉnh được đánh số từ 0 tới n−1; n có thể bằng 0 và mọi chỉ số cạnh phải hợp lệ.

Kết quả -1 báo rằng không có thứ tự đầy đủ vì tồn tại chu trình. Nếu đề thật dùng thông báo khác như IMPOSSIBLE, cần đổi phần xuất. Không nên mang nguyên quy ước đầu ra của ví dụ vào hệ thống chấm mà chưa đọc định dạng đề.

Hàm tạo mảng bậc vào riêng rồi thay đổi mảng đó trong lúc xử lý. Nếu muốn chạy thuật toán hai lần trên cùng đồ thị, hãy tính lại hoặc sao chép bậc vào ban đầu. Mảng đã giảm hết sau lượt đầu không còn mô tả dữ liệu gốc.

Dùng tô-pô cho quy hoạch động trên DAG

Khi đã có thứ tự hợp lệ, nhiều bài toán trở thành một lượt cập nhật từ trước ra sau. Ví dụ, đặt ways[s]=1 và truyền số cách từ u sang các v theo cạnh u → v. Đến lúc xử lý u, mọi tiền nhiệm của u đã được xử lý, nên các đóng góp cần thiết đã tới đủ.

Với thời lượng công việc t[v], có thể tính thời điểm hoàn thành sớm nhất bằng cách lấy thời điểm kết thúc lớn nhất trong các tiền nhiệm rồi cộng t[v]. Tuy nhiên, phép tính này giả định đủ tài nguyên để những việc độc lập chạy đồng thời. Nếu chỉ có một máy hoặc số nhân lực bị giới hạn, bài lập lịch có thêm ràng buộc và kết quả này chưa giải quyết hết đề.

Trọng số âm không cản trở việc tính đường ngắn nhất trên DAG: duyệt theo thứ tự tô-pô rồi nới lỏng mỗi cạnh. Lý do là không có chu trình và mọi tiền nhiệm đi trước, khác với điều kiện không âm mà Dijkstra cần.

So với cách dùng DFS

Chỉ đảo danh sách kết thúc DFS mà không kiểm chu trình có thể cho một dãy trông hợp lý nhưng vi phạm cạnh. Với người mới, Kahn thường dễ chạy tay hơn vì trạng thái đợi còn lại được thể hiện trực tiếp qua bậc vào.

Độ phức tạp và các test dễ sót

Trên danh sách kề, khởi tạo duyệt n đỉnh và m cạnh. Mỗi đỉnh vào hàng nhiều nhất một lần, mỗi cạnh được giảm bậc vào một lần, nên thời gian O(n+m); đồ thị và trạng thái dùng O(n+m) bộ nhớ. Cạnh song song vẫn xử lý được nếu được đếm và giảm đủ số lần.

Khi tự kiểm tra, bạn hãy thử đồ thị rỗng, nhiều đỉnh không cạnh, đường thẳng dài, cạnh tự nối và chu trình nằm trong một thành phần riêng. Với mỗi thứ tự tô-pô thu được, chỉ cần xác nhận mọi đỉnh xuất hiện đúng một lần và vị trí của u luôn đứng trước v với mọi cạnh có hướng u → v.

Luyện ngay trên Big-O Coding

Bắt đầu bằng hai bài sắp xếp tô-pô trực tiếp để vững bậc vào và hàng đợi. Sau đó chuyển sang lập lịch khóa học: từ mô tả môn tiên quyết, bạn cần tự xác định đúng hướng cạnh trước khi dùng cùng khung thuật toán.

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

Nguồn tham khảo

• CP-Algorithms: Topological Sorting
• CP-Algorithms: Finding a cycle
• Python: collections.deque