題意#
Uolevi 的班上有 \(n\) 個學生，另外還有 \(m\) 對好朋友關係。你的任務是幫他們分成兩個不同的隊伍，唯一的條件是：「不能有任何一對好朋友被分在同一個隊伍裡」。
如果可以成功分隊，請印出每個學生被分到哪一隊（輸出 1 或 2，任意一種合法的分法皆可）；如果不管怎麼分，都一定會有好朋友被塞在同一隊被迫互相廝殺，就印出 IMPOSSIBLE。
思路#
這題本質上就是「二分圖（Bipartite Graph）」的判定問題。我們要確認一張圖的節點，能不能單純被塗成兩種顏色，而且所有相鄰的節點（也就是牽涉到好朋友關係的兩個人）顏色都不一樣。
要解二分圖，最經典的做法就是「圖著色（Graph Coloring）」，可以用 DFS 或 BFS 來實作，概念都一樣。這裡我們採用 DFS 會簡單乾脆一點。
我們會依序巡視每一個學生，如果他還沒有被分到任何隊伍，我們就先私自把他指派到「第 1 隊」，然後沿著他的朋友圈開始深搜（DFS）。每次找到他的好朋友，就強制把對方分進「另一隊」（利用 3 - 原隊伍編號 的技巧，可以輕易達成 1 變 2、2 變 1 的切換）。
如果在深搜的過程中，我們不幸撞見某個好朋友「剛好被分在跟自己同一隊」，那就代表產生了衝突。此時我們就可以立刻宣告這班學生的交友關係太過錯綜複雜，絕對湊不齊兩個單純的隊伍，直接翻桌（記錄 flag = 0 表示無解）即可。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
vector<vector<int>> v;
vector<int> vis; // 用來記錄分隊狀態：0 表示未分隊，1 表示隊伍 1，2 表示隊伍 2
int flag = 1; // 判斷是否能成功分隊的旗標
// 透過 DFS 將相鄰的好朋友分到不同的隊伍（經典二分圖著色）
void dfs(int x) {
for (auto u : v[x]) {
if (!vis[u]) {
vis[u] = 3 - vis[x]; // 小技巧：將 1 轉 2，將 2 轉 1
dfs(u); // 繼續往深處著色
}
else if (flag) {
// 如果朋友 u 已經有隊伍了，檢查他的隊伍是不是跟 x 一樣
// 如果撞隊了，flag 就會變成 0（false），代表發生衝突不可能完成
flag = vis[x] != vis[u];
}
}
}
signed main() { WA();
int n, m; cin >> n >> m;
v.resize(n+1);
vis.resize(n+1);
// 讀入所有的好朋友關係（建立雙向無向圖）
while (m--) {
int a, b; cin >> a >> b;
v[a].pb(b);
v[b].pb(a);
}
// 可能有多個不連通的朋友圈，每個學生都要當頭試試看
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
vis[i] = 1; // 隨意指派未分隊的頭為 1 號隊伍
dfs(i);
}
}
if (flag) {
// 分隊成功，印出所有學生的所屬隊伍
for (int i = 1; i <= n; i++) cout << vis[i] << ' ';
}
else {
// 抓到衝突代表交友關係無法被切成二分圖，輸出無解
cout << "IMPOSSIBLE\n";
}
}
