Giả sử chúng ta có n thành phố được biểu diễn dưới dạng một số trong phạm vi [0, n) và chúng ta cũng có danh sách các đường một chiều nối thành phố này với thành phố khác. Chúng tôi phải kiểm tra xem chúng tôi có thể đến bất kỳ thành phố nào từ bất kỳ thành phố nào hay không.
Vì vậy, nếu đầu vào giống như n =3, đường =[[0, 1], [0, 2], [1,0], [1,2], [2,0], [2,1]] , thì đầu ra sẽ là True, vì Bạn có thể chuyển 0 đến 1 và 1 thành 0
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau−
-
Định nghĩa một hàm dfs (). Điều này sẽ đưa tôi đến thăm, g
-
đánh dấu tôi là đã ghé thăm
-
đối với mỗi j trong g [i], thực hiện
-
nếu j không được truy cập, thì
-
dfs (j, đã thăm, g)
-
-
-
Định nghĩa một hàm travel (). Điều này sẽ mất g
-
đã ghé thăm:=một tập hợp mới
-
dfs (0, đã thăm, g)
-
trả về true khi kích thước lượt truy cập giống với n
-
Từ phương thức chính, hãy thực hiện như sau−
-
graph:=một bản đồ trống
-
rev_graph:=một bản đồ trống
-
đối với mỗi nguồn u và điểm đến v trong các con đường, thực hiện
-
chèn v vào cuối biểu đồ [u]
-
chèn u vào cuối rev_graph [v]
-
-
trả về true khi du lịch (đồ thị) và du lịch (rev_graph) đều đúng
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
class Solution: def solve(self, n, roads): from collections import defaultdict graph = defaultdict(list) rev_graph = defaultdict(list) for u, v in roads: graph[u].append(v) rev_graph[v].append(u) def dfs(i, visited, g): visited.add(i) for j in g[i]: if j not in visited: dfs(j, visited,g) def travel(g): visited = set() dfs(0, visited, g) return len(visited)==n return travel(graph) and travel(rev_graph) ob = Solution() n = 3 roads = [[0, 1],[0, 2],[1,0],[1,2],[2,0],[2,1]] print(ob.solve(n, roads))
Đầu vào
3, [[0, 1],[0, 2],[1,0],[1,2],[2,0],[2,1]]
Đầu ra
True