題目背景與核心問題
在動漫世界裡，三角戀總是令人頭疼：愛麗絲愛鮑伯，查理也愛鮑伯，但愛麗絲討厭查理。現在給定 n 個角色，任意兩人之間要么相互喜歡，要么相互討厭，不存在中立狀態。我們希望避開兩種讓人不悅的三角關係：一種是「兩對相愛、一對相恨」（A-B 相愛、B-C 相愛、A-C 相恨），另一種是「三對全恨」（A-B、B-C、C-A 全部相恨）。換句話說，任意三人組成的三角形中，合法的關係只有「三對全愛」或「一對相愛、兩對相恨」。
給定 m 條已知關係（喜歡或討厭），請計算填補剩餘關係的方案數，使得所有三角形都滿足上述條件。答案對 1,000,000,007 取模。
關鍵洞察：關係的傳遞性與二分圖結構
將「喜歡」視為 1，「討厭」視為 0。對於任意三點 A、B、C，合法三角形的邊權和只能是 3（全 1）或 1（一個 1、兩個 0）。這意味著：
- 若 A 喜歡 B、B 喜歡 C，則 A 必須喜歡 C（否則構成 1-1-0 的非法三角形）。因此「喜歡」關係具有傳遞性，會形成若干個內部全互相喜歡的團。
- 若 A 討厭 B，則 A 所在團體的所有人都討厭 B 所在團體的所有人（否則會出現 1-0-0 或 0-0-1 的非法組合）。
綜上，每個連通塊必然是一個完全二分圖：將點分為 X、Y 兩集，集內邊權為 1（相愛），集間邊權為 0（相恨）。因此問題轉化為：在每個連通塊內進行 0/1 染色，若出現衝突則無解（答案為 0）；若所有連通塊均合法，設共有 k 個連通塊，則方案數為 2^(k-1)（因為整體翻轉所有顏色不改變關係）。
算法流程
- 建圖：每條已知關係對應一條帶權邊（1 表同色，0 表異色）。
- DFS/BFS 染色：對每個未訪問節點，指定顏色 0，沿邊傳播（權為 1 時顏色相同，權為 0 時顏色相反）。若發現矛盾，直接輸出 0。
- 統計連通塊數 k，答案初始為 (MOD+1)/2（即 2^0），每發現一個新連通塊將答案乘 2（模 MOD），相當於計算 2^(k-1)。
複雜度分析
時間複雜度 O(n + m)，空間複雜度 O(n + m)，完全滿足 n, m ≤ 100,000 的限制。
參考代碼（C++）
#include
using namespace std;
const int MOD = 1000000007;
const int MAXN = 100005;
vector> adj[MAXN];
int color[MAXN];
bool ok = true;
void dfs(int u) {
for (auto [v, w] : adj[u]) {
if (color[v] == -1) {
color[v] = w ? color[u] : 1 - color[u];
dfs(v);
} else {
if (w && color[v] != color[u]) ok = false;
if (!w && color[v] == color[u]) ok = false;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
while (cin >> n >> m) {
for (int i = 1; i <= n; ++i) adj[i].clear();
for (int i = 0; i < m; ++i) {
int a, b, c; cin >> a >> b >> c;
adj[a].push_back({b, c});
adj[b].push_back({a, c});
}
fill(color + 1, color + n + 1, -1);
ok = true;
long long ans = (MOD + 1) / 2; // 2^0
for (int i = 1; i <= n; ++i) {
if (color[i] == -1) {
ans = (ans * 2) % MOD;
color[i] = 0;
dfs(i);
}
}
if (!ok) ans = 0;
cout << ans << '\n';
}
return 0;
}
