問題是
給定一個無向圖，由 N 個頂點（編號從 1 到 N）和 M 條邊組成。
該圖由長度為 M 的兩個陣列 A 和 B 描述。對于 K 從 0 到 M-1 的一對 (A[K], B[K]) 描述頂點 A[K] 和頂點 B[K]。
你的任務是檢查給定的圖形是否包含從頂點 1 到頂點 N 的路徑，該路徑通過所有頂點，一個一個地，按照它們的數量遞增的順序。路徑上的所有連接都應該是直接的。
寫一個函式：
定義解 (N, A, B)
即，給定一個整數 N 和兩個由 M 個整陣列成的陣列 A 和 B，如果存在從頂點 1 到 N 的路徑按遞增順序依次經過所有頂點，則回傳 True，否則回傳 False。
例子：
給定 N = 4，A = [1, 2, 4, 4, 3] 和 B = [2, 3, 1, 3, 1]，函式應該回傳 True。有一條使用邊 (1, 2)、(2, 3) 和 (4, 3) 的路徑 (1-2-3-4)。
給定 N = 4，A = [1, 2, 1, 3] 和 B = [2, 4, 3, 4]，該函式應回傳 False。沒有路徑（123→4），因為從頂點 2 到頂點 3 沒有直接連接。
給定 N = 6，A = [2, 4, 5, 3] 和 B = [3, 5, 6, 4]，函式應該回傳 False。從頂點 1 到頂點 2 沒有直接連接。
給定 N = 3，A = [1, 3] 和 B = [2, 2]，函式應該回傳 True。有一條使用邊 (1, 2) 和 (3, 2) 的路徑 (1-2-3)。
為以下假設撰寫一個有效的演算法：
? N 是[2..100,000] 范圍內的整數；
M 是 [0..100,000] 范圍內的整數；
? 陣列A 和B 的所有元素都是[1..N] 范圍內的整數；
圖中沒有自環（A[K] = B[K] 的邊）；
? 相同頂點之間沒有多條邊
我寫的代碼是：
def solution(N, A, B):
# write your code in Python 3.6
pass
graph = {}
for i in range(len(A)):
if A[i] not in graph:
graph[A[i]] = [B[i]]
else:
graph[A[i]].append(B[i])
if B[i] not in graph:
graph[B[i]] = [A[i]]
else:
graph[B[i]].append(A[i])
print(graph)
visited = [False] * (N 1)
visited[0] = True
visited[1] = True
queue = [1]
while queue:
current = queue.pop(0)
for i in graph[current]:
if visited[i] == False:
visited[i] = True
queue.append(i)
return visited[N]
print(solution(4, [1, 2, 4, 4, 3], [2, 3, 1, 3, 1]))
print(solution(4, [1, 2, 1, 3], [2, 4, 3, 4]))
print(solution(6, [2, 4, 5, 3], [3, 5, 6, 4]))
print(solution(3, [1, 3], [2, 2]))
它拋出的錯誤是：
{1: [2, 4, 3], 2: [1, 3], 3: [2, 4, 1], 4: [1, 3]}
True
{1: [2, 3], 2: [1, 4], 4: [2, 3], 3: [1, 4]}
True
{2: [3], 3: [2, 4], 4: [5, 3], 5: [4, 6], 6: [5]}
---------------------------------------------------------------------------
KeyError Traceback (most recent call last)
~\AppData\Local\Temp/ipykernel_5588/4101128367.py in <module>
27 print(solution(4, [1, 2, 4, 4, 3], [2, 3, 1, 3, 1]))
28 print(solution(4, [1, 2, 1, 3], [2, 4, 3, 4]))
---> 29 print(solution(6, [2, 4, 5, 3], [3, 5, 6, 4]))
30 print(solution(3, [1, 3], [2, 2]))
~\AppData\Local\Temp/ipykernel_5588/4101128367.py in solution(N, A, B)
19 while queue:
20 current = queue.pop(0)
---> 21 for i in graph[current]:
22 if visited[i] == False:
23 visited[i] = True
KeyError: 1
誰能幫我這個？
uj5u.com熱心網友回復：
使用 defaultdict 可以省去麻煩。在這個問題中，您只需要檢查 i-1 是否連接到 i ，其中 i 是節點的編號。
from collections import defaultdict
def solution(N, A, B):
# write your code in Python 3.6
pass
graph = defaultdict(set)
for i in range(len(A)):
graph[A[i]].add(B[i])
graph[B[i]].add(A[i])
print(graph)
for i in range(2,N 1):
if i-1 not in graph[i]:
return False
return True
print(solution(4, [1, 2, 4, 4, 3], [2, 3, 1, 3, 1]))
print(solution(4, [1, 2, 1, 3], [2, 4, 3, 4]))
print(solution(6, [2, 4, 5, 3], [3, 5, 6, 4]))
print(solution(3, [1, 3], [2, 2]))
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/410521.html
標籤：