Phân tích: Diamond Inheritance

Bài toán yêu cầu chúng ta xác định xem trong một đồ thị có hướng, có tồn tại cặp nút \((X, Y)\) nào mà có từ hai đường đi trở lên từ \(X\) đến \(Y\) hay không.

Thuật toán

Với mỗi nút, chúng ta thực hiện tìm kiếm theo chiều sâu (depth-first search - DFS) với nút đó là gốc. Nếu trong quá trình DFS, chúng ta đi đến cùng một nút hai lần, thì chắc chắn chúng ta đã đi theo hai đường đi khác nhau để đến nút đó từ nút gốc, do đó chúng ta đã tìm thấy một cặp \((X, Y)\) thỏa mãn. Ngược lại, nếu có hai đường đi giữa \(X\) và \(Y\), chúng ta sẽ chạm đến \(Y\) ít nhất hai lần khi thực hiện DFS từ \(X\). Vì vậy, nếu thuật toán này không tìm thấy cặp \((X, Y)\) nào, thì không có cặp nào tồn tại trong đồ thị.

Độ phức tạp

Nếu có \(V\) nút và \(E\) cạnh trong đồ thị, thì một lần DFS nói chung có độ phức tạp là \(O(V+E)\). Tuy nhiên, mỗi lần DFS sẽ không bao giờ đi qua quá \(V\) cạnh, bởi vì sau khi đi qua số cạnh đó, chắc chắn sẽ có một nút nào đó được thăm lại lần thứ hai, và khi đó chúng ta có thể dừng lại ngay lập tức. Do đó, thuật toán này có tổng độ phức tạp là \(O(V^2)\).

Chúng ta cũng có thể sử dụng một biến thể của thuật toán Floyd để đếm số đường đi, với độ phức tạp là \(O(V^3)\), nhưng cách này rất đơn giản để cài đặt. Với chỉ 1000 nút trong đồ thị, một cài đặt nhanh sẽ hoàn thành trong giới hạn thời gian cho phép.

Dựa trên phân tích chính thức của Google Code Jam.