- //#include <iostream>
- //#include <vector>
- //#include <algorithm>
- //#include <cmath>
- #include <bits/stdc++.h>
- using namespace std;
- // 用來檢查一組學生是否存在朋友關係（違規組合）
- bool isValidGroup(const vector<int>& group, const vector<vector<bool>>& friends) {
- for (int i = 0; i < group.size(); i++) {
- for (int j = i + 1; j < group.size(); j++) {
- if (friends[group[i]][group[j]]) {
- return false; // 存在朋友關係，組合不合法
- }
- }
- }
- return true;
- }
- // 遞迴分組的核心函數
- void divideGroups(int student, vector<vector<int>>& groups, const vector<vector<bool>>& friends, int& minDifference, int N) {
- if (student > N) { // 所有學生都已分組
- int maxSize = 0, minSize = N;
- for (const auto& group : groups) {
- maxSize = max(maxSize, (int)group.size());
- minSize = min(minSize, (int)group.size());
- }
- minDifference = min(minDifference, maxSize - minSize);
- return;
- }
- for (auto& group : groups) {
- group.push_back(student); // 嘗試將當前學生加入該組
- if (isValidGroup(group, friends)) {
- divideGroups(student + 1, groups, friends, minDifference, N); // 遞迴分配下一位學生
- }
- group.pop_back(); // 回溯
- }
- }
- int main() {
- int N, M;
- cin >> N >> M;
- vector<vector<bool>> friends(N + 1, vector<bool>(N + 1, false));
- // 讀取朋友關係
- for (int i = 0; i < M; i++) {
- int X, Y;
- cin >> X >> Y;
- friends[X][Y] = friends[Y][X] = true;
- }
- // 初始化三組
- vector<vector<int>> groups(3);
- int minDifference = N; // 設置為最大可能值
- divideGroups(1, groups, friends, minDifference, N);
- // 如果無法找到合法分組，minDifference 不會被更新
- if (minDifference == N) {
- cout << -1 << endl;
- } else {
- cout << minDifference << endl;
- }
- return 0;
- }
- /*
- 5 5
- 1 2
- 2 3
- 3 4
- 4 5
- 1 5
- */
程式邏輯解釋
輸入處理與資料結構設置：
使用 friends 矩陣記錄朋友關係，friends[j] = true 表示學生 i 和 j 是朋友。
使用三個向量的 groups 表示分成的三組學生。
核心檢查函數 isValidGroup：
檢查某組內是否有任意兩位學生是朋友。
如果有朋友關係，則該組不合法。
分組遞迴邏輯 divideGroups：
對每位學生嘗試加入三個組中的一個。
如果當前組合合法，則遞迴處理下一位學生。
如果全部學生分組完成，計算三組最大與最小人數的差值，並更新最小差值。
結果輸出：
如果分組後的最小差值未被更新，表示無法找到合法分組，輸出 -1。
否則輸出最小差值。
輸入與輸出範例解析
範例1：
輸入：
複製程式碼
5 5
1 2
2 3
3 4
4 5
1 5
輸出：
複製程式碼
1
解釋： 分組為 [1, 4], [2, 5], [3]，最大人數為 2，最小人數為 1，差值為 1。
範例2：
輸入：
複製程式碼
4 6
1 2
1 3
1 4
2 3
2 4
3 4
輸出：
diff
複製程式碼
-1
解釋： 無法找到合法分組，因為所有學生彼此都是朋友。
範例3：
輸入：
複製程式碼
6 1
1 2
輸出：
複製程式碼
0
解釋： 分組為 [1, 2], [], [] 或其他方式，最大與最小人數的差值為 0。
這段程式碼適合解決此問題並兼具清晰的邏輯與效率。
-------------------------------------------------------------------------------
size_t j = i + 1 是 C++ 程式碼中的一部分，定義了一個無符號整數型別變數 j，並將它初始化為 i + 1 的值。
詳細解釋
size_t:
這是一種無符號整數型別，通常用於表示非負數的大小或索引值。
它的具體大小（位元數）依據作業系統和編譯器而定，通常是 32 位或 64 位。
使用 size_t 可以避免索引或大小計算中出現負數的情況。
j = i + 1:
表示將變數 j 的值設置為變數 i 的值加 1。
在上下文中，這是用來遍歷 group 中的每個元素時，確保 j 起始於 i 的下一個位置，避免重複檢查自己。
背景功能
在這段程式碼中，for (size_t j = i + 1; j < group.size(); ++j) 是一個內層迴圈，用來檢查組內的任意兩位學生是否有朋友關係。起始值 i + 1 確保只檢查 i 之後的學生，避免冗餘的檢查（如檢查 friends[group][group[j]] 和 friends[group[j]][group] 是重複的）。
在程式碼中，for (auto& group : groups) 是一個範圍式 for 迴圈（C++11 引入的語法），其作用是逐一遍歷容器 groups 中的每個元素。
詳細解釋
關鍵詞 auto&：
auto：讓編譯器自動推斷變數 group 的型別，根據 groups 的元素型別推斷出 group 是 vector<int>&（一個整數向量的參考）。
&：使用參考，允許直接修改 groups 中的每個子向量，而不需要複製。
groups 容器：
groups 是一個包含三個向量的容器，類型為 vector<vector<int>>，每個向量表示一組學生的編號。
作用：
這段程式碼的目的，是將當前的學生嘗試加入三個組中的某一組。
由於 group 是參考，對 group 的修改會直接影響到 groups 容器內的對應子向量。
範例
假設：
vector<vector<int>> groups = {{1}, {2}, {3}};
範圍式 for 的運行如下：
第一次迴圈：group 參考 groups[0]（內容為 {1}）。
第二次迴圈：group 參考 groups[1]（內容為 {2}）。
第三次迴圈：group 參考 groups[2]（內容為 {3}）。
對 group 的操作會直接改變 groups 對應的內容。
程式片段意圖
該迴圈在遞迴過程中逐一嘗試將學生加入每個組，並利用參考特性避免不必要的複製操作，提升程式效能。
-------------------------------------------------------------------
為什麼N要+1
N + 1 是用於初始化 friends 二維矩陣的大小，其中 N 是學生的數量。以下是為什麼需要加 1 的詳細解釋：
背景
在程式中，friends 是一個二維布林矩陣，用來記錄學生之間的朋友關係。大小為 (N + 1) x (N + 1)，每個元素 friends[X][Y] 表示學生 X 和學生 Y 是否是朋友。
為什麼要加 1
學生編號從 1 開始：
題目中提到，學生的編號是從 1 到 N。
為了方便直接使用學生編號作為矩陣的索引，矩陣需要有 N + 1 行和列。
例如，對於 5 位學生，矩陣索引會是 0 到 5。其中索引 0 不使用，而索引 1 到 5 對應學生。
避免偏移計算：
如果矩陣大小僅為 N x N，則需要將學生編號減 1（例如 friends[X-1][Y-1]）來進行索引操作，這樣會增加程式的複雜性。
增加矩陣的大小到 N + 1 後，可以直接使用學生編號（如 friends[X][Y]）而不需要額外的轉換。
結論
將矩陣大小設定為 N + 1 是為了讓程式碼更簡潔、直觀，並且符合題目中學生編號從 1 開始的設定。如果有其他問題，歡迎進一步詢問！
-------------------------------------------------------------
解釋 group.pop_back();
這一行程式碼的作用是回溯，用來撤銷前面的一次狀態改變，讓程式可以嘗試其他可能的分組方式。
背景
在遞迴函數 divideGroups 中，我們使用以下邏輯來嘗試分組：
加入學生：利用 group.push_back(student)，將當前學生加入某一組。
檢查組合合法性：透過 isValidGroup 函數檢查組內是否有違規（存在朋友）。
進入下一層遞迴：若組合合法，遞迴處理下一位學生。
回溯：用 group.pop_back()，將學生從該組移除，恢復組的原始狀態，然後嘗試將學生加入其他組。
回溯的必要性
避免重複狀態：每次嘗試不同分組時，都需要恢復原本的狀態，否則後續嘗試會受到之前選擇的影響。
完整探索所有可能解：回溯機制允許程式依序探索所有可能的分組情況，以找到最佳解。
範例
假設目前有 3 位學生，程式試圖將第 1 位學生加入第 1 組：
加入學生 1：group[0] = {1}。
遞迴嘗試學生 2：
將學生 2 加入第 1 組後，group[0] = {1, 2}。
發現違規（例如，學生 1 和 2 是朋友），需要回溯。
執行 pop_back()，group[0] 恢復為 {1}。
再嘗試將學生 2 加入其他組。
小結
group.pop_back(); 是遞迴與回溯算法的核心部分之一，確保每一次遞迴執行後，狀態能恢復初始，以便探索其他解決方案。如果沒有這行程式碼，分組狀態將無法正確更新，導致程式結果不正確。 |
