《灵珠觉醒:从零到算法金仙的C++修炼》卷三·天劫试炼(48)戮魂幡染节点 - 二分图检测(着色法)
《灵珠觉醒:从零到算法金仙的C++修炼》卷三·天劫试炼(48)戮魂幡染节点 - 二分图检测(着色法)
哪吒在数据修仙界中继续他的修炼之旅。这一次,他来到了一片神秘的戮魂幡林,林中有一面巨大的幡旗,旗身缠绕着复杂的图结构。幡旗的入口处有一块巨大的石碑,上面刻着一行文字:“欲破此林,需以戮魂幡之力,染节点,二分图显真身。”
哪吒定睛一看,石碑上还有一行小字:“图的邻接表表示为[ (0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (2, 4), (3, 4) ]
,该图是二分图。”哪吒心中一动,他知道这是一道关于二分图检测的难题,需要通过着色法来判断图是否为二分图。
暴力解法:戮魂幡的初次尝试
哪吒心想:“要判断二分图,我可以尝试所有可能的着色方式。”他催动戮魂幡之力,从图中的一个节点开始,逐个节点着色,试图找到一种合法的着色方案。
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 1000;
vector<int> adj[MAXN];
int color[MAXN];
bool dfs(int u, int c) {
color[u] = c;
for (int v : adj[u]) {
if (color[v] == -1) {
if (!dfs(v, 1 - c)) return false;
} else if (color[v] == c) {
return false;
}
}
return true;
}
bool isBipartite(int n) {
memset(color, -1, sizeof(color));
for (int i = 0; i < n; ++i) {
if (color[i] == -1) {
if (!dfs(i, 0)) return false;
}
}
return true;
}
int main() {
int n = 5;
int edges[] = {
0, 1, 0, 2, 1, 2, 1, 3, 2, 3, 2, 4, 3, 4};
for (int i = 0; i < sizeof(edges)/sizeof(edges[0]); i += 2) {
int u = edges[i], v = edges[i+1];
adj[u].push_back(v);
adj[v]