回復 1# may - //#include <iostream>
- //#include <vector>
- //#include <queue>
- #include <bits/stdc++.h>
- using namespace std;
- vector<int> adj[100005]; // 鄰接表
- int color[100005]; // 記錄每個節點的顏色 (0: 未染色, 1: 顏色1, 2: 顏色2)
- bool isBipartite(int N) {
- queue<int> q;
- q.push(1); // 從節點 1 開始
- color[1] = 1;
- while (!q.empty()) {
- int node = q.front();
- q.pop();
- for (int neighbor : adj[node]) {
- if (color[neighbor] == 0) { // 若還沒染色，給不同的顏色
- color[neighbor] = (color[node] == 1) ? 2 : 1;
- q.push(neighbor);
- }
- }
- }
- return true;
- }
- int main() {
- int N, M;
- cin >> N >> M;
- for (int i = 0; i < M; i++) {
- int X, Y;
- cin >> X >> Y;
- adj[X].push_back(Y);
- adj[Y].push_back(X);
- }
- if (N == 1) {
- cout << 1 << endl; // 只有 1 個節點，只需 1 種顏色
- } else {
- isBipartite(N);
- cout << 2 << endl; // 樹是二分圖，最多需要 2 種顏色
- }
- return 0;
- }
正確解法：使用 BFS 來檢查是否需要 2 或 1 種顏色
因為：
樹一定是連通的，且無環
樹總是二分圖（最多需要 2 種顏色）
我們可以用 BFS 或 DFS 來二分著色：
如果整棵樹只有 1 個節點，那麼只需要 1 種顏色。
否則，因為樹是二分圖，最少需要 2 種顏色。
------------------------------------------
解釋
建立鄰接表：
讀取 N 和 M。
用 adj[X].push_back(Y) 來存儲連接關係。
使用 BFS 進行二分著色：
用 queue<int> 來進行廣度優先搜索（BFS）。
color 存儲每個節點的顏色（1 或 2）。
若相鄰節點還沒染色，就賦予不同顏色，並加入隊列繼續搜尋。
輸出 2：
除非 N == 1，否則樹必定是二分圖，只需 2 種顏色。
時間複雜度分析
建構鄰接表： O(N)
BFS 遍歷所有節點： O(N)
總時間複雜度： O(N)
------------------------------
測資:
測資00：最小測資 (只有 1 個雷達)
輸入
1 0
預期輸出
1
解析：只有 1 個雷達，僅需 1 種頻率。
測資 01：鏈狀樹
輸入
5 4
1 2
2 3
3 4
4 5
預期輸出
2
解析：這是一條線狀樹，像這樣：
1 - 2 - 3 - 4 - 5
可以使用交替頻率（例如 1, 2, 1, 2, 1），因此最多只需要 2 種頻率。
測資 02：星狀樹
輸入
6 5
1 2
1 3
1 4
1 5
1 6
預期輸出
2
解析：這是 星狀樹，所有雷達都連接到節點 1：
2
|
1 - 3
|
4
|
5
|
6
可以讓 1 使用顏色 1，其他所有相鄰節點 (2, 3, 4, 5, 6) 使用顏色 2，所以只需要 2 種顏色。
測資 03：完全二元樹
輸入
7 6
1 2
1 3
2 4
2 5
3 6
3 7
預期輸出
2
解析：這是一棵二元樹：
1
/ \
2 3
/ \ / \
4 5 6 7
根節點 1 使用顏色 1
2 和 3 使用顏色 2
4, 5, 6, 7 使用顏色 1
因此只需要 2 種頻率。
測資 04：隨機樹
輸入
8 7
1 2
1 3
2 4
2 5
3 6
3 7
6 8
預期輸出
2
解析：
1
/ \
2 3
/ \ / \
4 5 6 7
|
8
仍然是二分圖，最多只需要 2 種頻率。
這 5 筆測資涵蓋了： ✅ 最小情況 (N=1)
✅ 線性結構（鏈狀樹）
✅ 星狀樹
✅ 完全二元樹
✅ 隨機樹 |
