回復 1# may - #include<bits/stdc++.h>
- #define int long long //確保變數能夠處理較大的數值範圍，避免溢位。
- using namespace std;
- int n,m;
- signed main()//因#define int long long而main 函數必須傳回一個int 值，所以不能使用int main()。通常使用signed main，因為signed 等效替代於signed int，也就是有符號整數，這與int 別無二致，並且不會導致奇怪的CE。
- {
- int a,b,ans=0;
- cin>>n>>m;
- vector<int> path[n+1];//path[i]：儲存與雷達 i 相鄰的所有雷達編號,n+1：確保陣列索引從 1 開始，與輸入數據一致。
- int freq[n+1]={0}; //freq[i]：雷達 i 被分配的頻率值,初始化為 0，表示尚未分配頻率。
- for(int i=0;i<m;i++)
- {
- cin>>a>>b;
- path[b].push_back(a);
- path[a].push_back(b);
- }
- for(int i=1;i<=n;i++)
- {
- set<int> s; //set容器是用二元搜尋樹實現的一種集合，集合中每種元素只出現一次。count()是set容器中常用的函數。
- for(int j=0;j<path[i].size();j++)
- s.insert(freq[path[i][j]]);//建立 set<int> s，用來存放與 i 相鄰的雷達已經使用的頻率。freq[path[i][j]]：代表相鄰雷達 path[i][j] 的頻率，將這些頻率存入 set 中。
- int index=1;
- while(s.count(index))// set::count() 是C++ STL中的内置函数，它返回元素在集合中出现的次数。由于set容器仅包含唯一元素，因此只能返回1或0。
- index++;
- freq[i]=index;
- ans=max(ans,index);
- }
- cout<<ans<<endl;
- 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)
✅ 線性結構（鏈狀樹）
✅ 星狀樹
✅ 完全二元樹
✅ 隨機樹 |
