資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Python程式：檢查是否可以從任何城市到達任何其他城市
假設我們有n個城市，用[0, n)範圍內的數字表示，我們還有一個單向道路列表，連線一個城市到另一個城市。我們必須檢查是否可以從任何城市到達任何其他城市。
因此，如果輸入類似於n = 3，roads = [[0, 1],[0, 2],[1,0],[1,2],[2,0],[2,1]]，則輸出為True，因為您可以從0到1，從1到0。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式dfs()。它將接收i、visited和g。
將i標記為已訪問。
對於g[i]中的每個j，執行：
如果j未被訪問，則
dfs(j, visited, g)
定義一個函式travel()。它將接收g。
visited := 一個新的集合
dfs(0, visited, g)
當visited的大小與n相同時返回true
在主方法中，執行以下操作：
graph := 一個空對映
rev_graph := 一個空對映
對於roads中的每個源u和目標v，執行：
在graph[u]的末尾插入v
在rev_graph[v]的末尾插入u
當travel(graph)和travel(rev_graph)都為true時返回true
讓我們看看下面的實現以更好地理解：
示例
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))
輸入
3, [[0, 1],[0, 2],[1,0],[1,2],[2,0],[2,1]]
輸出
True
更新於：2020年10月5日
733 次瀏覽
廣告