算法1: DFS
#include <iostream>
#include <vector>
using namespace std;
int n, m, u, v;
bool dfs(vector<vector<int>>& g, int cur, int color, vector<int>& colors) {
colors[cur] = color;
for (const auto& nxt : g[cur]) {
if (colors[nxt] == color) return false; // conflict
if (colors[nxt] == -1 && !dfs(g, nxt, color ^ 1, colors)) return false;
}
return true;
}
int main(void) {
cin >> n >> m;
// build the undirected graph
vector<vector<int>> g(n + 1); // adjacency list
// -1: UNKNOWN, 0: RED, 1: BLUE
vector<int> colors(n + 1, -1);
while (m--) {
cin >> u >> v;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
// The graph may be has multiple connected components!
for (int i = 1; i <= n; ++i)
if (colors[i] == -1 && !dfs(g, i, 0, colors)) return puts("No"), 0;
puts("Yes");
}
算法2:BFS
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int n, m, u, v;
bool bfs(vector<vector<int>>& g, int start, vector<int>& colors) {
queue<int> q{{start}};
colors[start] = 0;
while (not q.empty()) {
const int cur = q.front(); q.pop();
const int curColor = colors[cur];
for (const auto& nxt : g[cur]) {
if (colors[nxt] != -1 && colors[nxt] == curColor) return false; // conflict
if (colors[nxt] == -1) { // 没有染过色
colors[nxt] = curColor ^ 1;
q.emplace(nxt);
}
}
}
return true;
}
int main() {
cin >> n >> m;
vector<vector<int>> g(n + 1);
// -1: UNKNOWN, 0: RED, 1: BLUE
vector<int> colors(n + 1, -1);
// build the undirected graph
while (m--) {
cin >> u >> v;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
for (int i = 1; i <= n; ++i)
if (colors[i] == -1 && !bfs(g, i, colors)) return puts("No"), 0;
puts("Yes");
}
BFS的代码,写的不好大家见谅