【範例】二分圖判定
【題目敘述】https://tioj.ck.tp.edu.tw/problems/2062
【解題想法】二分圖染色（BFS）
- c[ i ]：第 i 個點的分類
- 0 表示尚未被分類
- 1 表示塗上第一種顏色
- -1表示塗上第二種顏色
- (Line-20) 枚舉所有點，確保所有的連通塊都會被處理。
- (Line-21) 全新的連通塊中號碼最小的，先塗 1。
- queue裡面存放的都是已經塗過顏色的點
- 相鄰已塗色的點，如果顏色與now相同，則不是二分圖。
- 遇到相鄰但尚未塗色的點，塗上另一種顏色。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 1000005;
int n, m, x, y, c[maxn];
vector <int> g[maxn], a, b;
queue <int> q;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++){
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
for (int i = 1; i < n; i++){
if (c[i]) continue;
c[i] = 1;
q.push(i);
while (!q.empty()){
int now = q.front();
q.pop();
if (c[now] == 1) a.push_back(now);
else b.push_back(now);
for (int j:g[now]){
if (c[j]){
if (c[j] == c[now]){
cout << "-1\n";
return 0;
}
}
else {
c[j] = -c[now];
q.push(j);
}
}
}
}
cout << a.size() << " " << b.size() << "\n";
for (int i:a){
cout << i << " ";
}
cout << "\n";
for (int i:b){
cout << i << " ";
}
cout << "\n";
}