X 國的一個網絡使用若干條線路連接若干個節點。節點間的通信是雙向的。某重要數據包，為了安全起見，必須恰好被轉發兩次到達目的地。該包可能在任意一個節點產生，我們需要知道該網絡中一共有多少種不同的轉發路徑。

源地址和目標地址可以相同，但中間節點必須不同。

如圖所示的網絡。

1 -> 2 -> 3 -> 1 是允許的

1 -> 2 -> 1-> 2 或者 1->2->3->2 都是非法的。

輸入數據的第一行為兩個整數N M，分別表示節點個數和連接線路的條數(1<=N<=10000; 0<=M<=100000)。

接下去有M行，每行為兩個整數 u 和 v，表示節點u 和 v 聯通(1<=u,v<=N , u!=v)。

輸入數據保證任意兩點最多只有一條邊連接，并且沒有自己連自己的邊，即不存在重邊和自環。

輸出一個整數，表示滿足要求的路徑條數。

例如：
用戶輸入：
3 3
1 2
2 3
1 3
則程序應該輸出：
6

再例如：
用戶輸入：
4 4
1 2
2 3
3 1
1 4
則程序應該輸出：
10

深度優先搜索

深搜三步走。

Code

def dfs(x, pre, step):if step == 3:global ansans += 1returnfor i in range(len(graph[x])):if graph[x][i] != pre:dfs(graph[x][i], x, step + 1)if __name__ == '__main__':n, m = map(int, input().split())ans, graph = 0, [[] for _ in range(10007)]for _ in range(m):u, v = map(int, input().split())graph[u].append(v)graph[v].append(u)for i in range(1, n + 1):dfs(i, 0, 0)print(ans)

總結

以上是生活随笔為你收集整理的2013\National _C_C++_A\5.网络寻路的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。