Board logo

標題: 202411潛力2-鐵路 (Rail) [打印本頁]
作者: may    時間: 2024-12-27 14:55     標題: 202411潛力2-鐵路 (Rail)

問題敘述
某國的鐵路有N座車站，編號0 ~ N-1，並且由M條雙向軌道連接兩座相異車站。如果兩座車站之間存在軌道，則原本在其中一座車站的火車即可藉由軌道到達另外一座車站。火車可以互相到達的車站們屬於同一個鐵路網。為了節省維護成本，鐵路公司決定停用某些軌道，使得所有鐵路網的兩座相異車站恰有一條軌道路徑連通。請寫一個程式計算出總共有多少個鐵路網會被停用軌道，又有多少個鐵路網不會被停用任何軌道。 例如：有N = 7座車站、M = 6條雙向軌道，鐵路路網圖如圖一所示。圖中圓圈代表車站，裡面的數字代表車站編號；連接兩座車站的線代表軌道。由此圖可知，總共有兩個鐵路網，分別由車站0, 1 , 2, 3以及車站4, 5, 6組成。其中由車站0, 1, 2, 3 組成的鐵路網會被停用一條軌道，至於另外一個由車站4, 5, 6組成的鐵路網則不會被停用任何軌道，因為任兩座相異的車站之間已經恰好由一條軌道路徑連通了。
[attach]20346[/attach]
輸入格式
第一列有兩個正整數N 和 M ( 2 ≤ N ≤ 103, M ≤ N×( N-1)/2 )，表示有N座車站和M條雙向軌道。接下來M列，每列有兩個相異整數A 和 B (0 ≤ A, B ≤ N-1)，兩個整數間以一個空白為間隔，表示車站A和車站B存在一條雙向軌道連通。兩座車站之間最多只會有一條鐵軌連通。測資保證每個鐵路車站至少連有一條軌道。
輸出格式
請輸出兩個正整數，兩數以一個空白隔開，分別表示「會被停用軌道的鐵路網個數」以及「不會被停用軌道的鐵路網個數」。
[attach]20347[/attach]
評分說明 此題目測資分成兩組，每組測資有多筆測試資料，需答對該組所有測試資料才能獲得該組分數，各組詳細限制如下。
第一組 (50 分)：所有鐵路網都會被停用鐵軌。
第二組 (50 分)：無特別限制。
作者: may    時間: 2024-12-27 21:12

  1. //#include <iostream>
  2. //#include <vector>
  3. //#include <set>
  4. #include <bits/stdc++.h>
  5. using namespace std;

  7. // 用於表示鐵路網的鄰接清單
  8. vector<vector<int>> adjList;
  9. vector<bool> visited;

  11. // 記錄鐵路網中的車站數與邊數
  12. int nodes, edges;

  14. // 深度優先搜尋 (DFS) 計算鐵路網的節點與邊數
  15. void dfs(int node, int &nodeCount, int &edgeCount) {
  16.     visited[node] = true;//將要搜尋的節點值為true
  17.     nodeCount++;
  18.     for (int neighbor : adjList[node]) {//搜尋每節點的相通節點
  19.         edgeCount++;//邊數累加
  20.         if (!visited[neighbor]) {// if (visited[i]==0)
  21.             dfs(neighbor, nodeCount, edgeCount);
  22.         }
  23.     }
  24. }

  26. int main() {
  27.     int N, M;//N點,M邊
  28.     cin >> N >> M;

  30.     adjList.resize(N);//vector adjList包含N個元素
  31.     visited.resize(N, false);//vector visited包含N個元素,預設為false
  32.     //cout<<visited[0]<<visited[1]<<visited[2]<<visited[3]<<visited[4]<<visited[5]<<visited[6]<<"#";

  34.     // 建立鄰接清單
  35.     for (int i = 0; i < M; i++) {
  36.         int A, B;
  37.         cin >> A >> B;
  38.         adjList[A].push_back(B);
  39.         adjList[B].push_back(A);
  40.     }

  42.     int reducible = 0;  // 會被停用軌道的鐵路網數量
  43.     int irreducible = 0; // 不會被停用軌道的鐵路網數量

  45.     // 遍歷所有車站，確認每個鐵路網
  46.     for (int i = 0; i < N; i++) {
  47.         if (!visited[i]) { //if (visited[i]==0)
  48.             int nodeCount = 0, edgeCount = 0;//節點,邊數初始值為0
  49.             dfs(i, nodeCount, edgeCount);//呼叫dfs函數

  51.             // 計算邊數應為雙向，因此需除以 2
  52.             edgeCount /= 2;

  54.             // 如果邊數多於節點數 - 1，代表此鐵路網可簡化
  55.             if (edgeCount > nodeCount - 1) {
  56.                 reducible++;
  57.             } else {
  58.                 irreducible++;
  59.             }
  60.         }
  61.     }

  63.     // 輸出結果
  64.     cout << reducible << " " << irreducible << endl;

  66.     return 0;
  67. }
  68. /*
  69. 輸入範例1
  70. 7 6
  71. 0 1
  72. 1 2
  73. 2 0
  74. 1 3
  75. 4 5
  76. 5 6
  77. 輸出範例1
  78. 1 1
  79. 在C++中，resize() 是一個常用的成員函數，主要用於調整std:: vector容器的大小。
  80. std::vector 是一個動態數組，允許在運行時改變其大小。
  81. resize() 提供了一種簡單的方法來增加或減少vector 的元素數量
  82. */
複製代碼
程式邏輯說明
鄰接清單的構建：

輸入的車站和軌道以鄰接清單 (adjList) 方式儲存，每個節點連結其相鄰的節點。
DFS 計算鐵路網的節點與邊數：

使用深度優先搜尋（DFS）來計算某個連通分量的車站數（nodeCount）與邊數（edgeCount）。
注意：由於每條軌道是雙向的，DFS 遍歷時每條邊會被計算兩次，因此最終邊數需除以 2。
分類鐵路網：

判斷條件：
若邊數多於節點數減 1（edgeCount > nodeCount - 1），表示該鐵路網有多餘的軌道可簡化。
否則，該鐵路網已是最小連通樹，不需簡化。
輸出結果：

輸出兩個數字，分別代表「會被停用軌道的鐵路網數量」與「不會被停用任何軌道的鐵路網數量」。
測試範例
輸入：
複製程式碼
7 6
0 1
1 2
2 0
1 3
4 5
5 6
輸出：
複製程式碼
1 1
解釋：
共有兩個鐵路網：
車站 {0, 1, 2, 3}，包含 4 個節點與 4 條邊，多餘的軌道可停用。
車站 {4, 5, 6}，包含 3 個節點與 2 條邊，無多餘軌道。



歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://istak.org.tw/seed/) Powered by Discuz! 7.2