Ta đưa bài này về đồ thị như sau : Coi mỗi cặp số như một cạnh có hướng từ u tới v, như thế mỗi mật khẩu hợp lệ chính là một đường đi trên đồ thị.

Ta cần phải tính tổng tất cả các đường đi có thể.

Tuy nhiên, lưu ý trường hợp đồ thị có chu trình. Lúc này sẽ có vô số mật khẩu. Ta sử dụng sắp xếp topo (topological sort) để kiểm tra đồ thị có phải là DAG?

Gọi numpath[u] là số đường đi xuất phát từ đỉnh \(u\), sumpath[u] là tổng các đường đi xuất phát từ đỉnh \(u\)

Ta thực hiện DFS trên đồ thị và QHĐ với công thức sau

Với mỗi cạnh \(u \rightarrow v\) ta có :

numpath[u] += numpath[v]

sumpath[u] += sumpath[v] + numpath[v] * a[u]

ĐPT \(O(n+m)\)