202411潛力2-鐵路 (Rail)

may

問題敘述
某國的鐵路有N座車站，編號0 ~ N-1，並且由M條雙向軌道連接兩座相異車站。如果兩座車站之間存在軌道，則原本在其中一座車站的火車即可藉由軌道到達另外一座車站。火車可以互相到達的車站們屬於同一個鐵路網。為了節省維護成本，鐵路公司決定停用某些軌道，使得所有鐵路網的兩座相異車站恰有一條軌道路徑連通。請寫一個程式計算出總共有多少個鐵路網會被停用軌道，又有多少個鐵路網不會被停用任何軌道。 例如：有N = 7座車站、M = 6條雙向軌道，鐵路路網圖如圖一所示。圖中圓圈代表車站，裡面的數字代表車站編號；連接兩座車站的線代表軌道。由此圖可知，總共有兩個鐵路網，分別由車站0, 1 , 2, 3以及車站4, 5, 6組成。其中由車站0, 1, 2, 3 組成的鐵路網會被停用一條軌道，至於另外一個由車站4, 5, 6組成的鐵路網則不會被停用任何軌道，因為任兩座相異的車站之間已經恰好由一條軌道路徑連通了。

輸入格式
第一列有兩個正整數N 和 M ( 2 ≤ N ≤ 103, M ≤ N×( N-1)/2 )，表示有N座車站和M條雙向軌道。接下來M列，每列有兩個相異整數A 和 B (0 ≤ A, B ≤ N-1)，兩個整數間以一個空白為間隔，表示車站A和車站B存在一條雙向軌道連通。兩座車站之間最多只會有一條鐵軌連通。測資保證每個鐵路車站至少連有一條軌道。
輸出格式
請輸出兩個正整數，兩數以一個空白隔開，分別表示「會被停用軌道的鐵路網個數」以及「不會被停用軌道的鐵路網個數」。

評分說明 此題目測資分成兩組，每組測資有多筆測試資料，需答對該組所有測試資料才能獲得該組分數，各組詳細限制如下。
第一組 (50 分)：所有鐵路網都會被停用鐵軌。
第二組 (50 分)：無特別限制。

may

1. //#include <iostream>
   
2. //#include <vector>
   
3. //#include <set>
   
4. #include <bits/stdc++.h>
   
5. using namespace std;
   
6. 
   
7. // 用於表示鐵路網的鄰接清單
   
8. vector<vector<int>> adjList;
   
9. vector<bool> visited;
   
10. 
    
11. // 記錄鐵路網中的車站數與邊數
    
12. int nodes, edges;
    
13. 
    
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. }
    
25. 
    
26. int main() {
    
27.     int N, M;//N點,M邊
    
28.     cin >> N >> M;
    
29. 
    
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]<<"#";
    
33. 
    
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.     }
    
41. 
    
42.     int reducible = 0;  // 會被停用軌道的鐵路網數量
    
43.     int irreducible = 0; // 不會被停用軌道的鐵路網數量
    
44. 
    
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函數
    
50. 
    
51.             // 計算邊數應為雙向，因此需除以 2
    
52.             edgeCount /= 2;
    
53. 
    
54.             // 如果邊數多於節點數 - 1，代表此鐵路網可簡化
    
55.             if (edgeCount > nodeCount - 1) {
    
56.                 reducible++;
    
57.             } else {
    
58.                 irreducible++;
    
59.             }
    
60.         }
    
61.     }
    
62. 
    
63.     // 輸出結果
    
64.     cout << reducible << " " << irreducible << endl;
    
65. 
    
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 條邊，無多餘軌道。