Trước tiên, hãy thực hiện DFS trên biểu đồ, bắt đầu từ nút nguồn, như bạn đã biết, được biết trước. Nếu bạn gặp phải một cạnh sau [1], sau đó bạn có một chu kỳ và bạn có thể thoát ra với một lỗi.Trong quá trình truyền tải này, bạn có thể xác định nếu có các nút, không thể truy cập từ nguồn [2] và thực hiện hành động thích hợp.
Một khi bạn đã xác định đồ thị là một DAG, bạn có thể đảm bảo rằng tất cả các nút nằm trên một đường đi từ nguồn đến chìm bởi một DFS, bắt đầu từ nguồn, như sau:
bool have_path(source, sink) {
if source == sink {
source.flag = true
return true
}
// traverse all successor nodes of `source`
for dst in succ(source) {
if not dst.flag and not have_path(dst, sink)
return false // exit as soon as we find a node with no path to `sink`
}
source.flag = true;
return true
}
Các thủ tục have_path thiết lập một boolean flag trong mỗi nút, trong đó có tồn tại một số đường dẫn từ nút đó đến bồn rửa. Trong cùng một thời gian, thủ tục chỉ duyệt qua các nút có thể truy cập từ nguồn và nó đi qua tất cả các nút có thể truy cập từ nguồn. Nếu thủ tục trả về true, thì tất cả các nút, có thể truy cập từ nguồn nằm trên một đường dẫn đến bồn rửa. Các nút không thể truy cập đã được xử lý trong giai đoạn đầu tiên.
[1] một cạnh, liên kết một nút với một số DFS lớn hơn cho một nút với một số DFS thấp hơn, đó không phải là đã hoàn toàn xử lý, tức là vẫn còn trên DFS chồng
[2 ] ví dụ họ sẽ không có số DFS được chỉ định
Tìm các thành phần được kết nối mạnh mẽ. Sau đó, bạn có CC nguồn và chìm CC. Kiểm tra xem cả hai chỉ chứa một phần tử. Độ phức tạp cũng là tuyến tính. –
Trên thực tế, không phải thuật toán của Tarjan là thuật toán tìm thấy thành phần được kết nối mạnh mẽ? –