当前位置: 首页 > article >正文

《灵珠觉醒:从零到算法金仙的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]

http://www.kler.cn/a/587073.html

相关文章:

  • 【NLP】 9. 处理创造性词汇 词组特征(Creative Words Features Model), 词袋模型处理未知词,模型得分
  • 【黑马点评|项目】万字总结(下)
  • Python软件和搭建运行环境
  • C++进阶——map和set的使用
  • Python在数据处理中的应用:从入门到精通
  • Linux date 命令使用指南
  • 用Python打造AI玩家:挑战2048,谁与争锋
  • Socket服务器和客户端
  • 安装SQL数据库并且在jupyter中连接,运行
  • 回溯法--力扣第17题“电话号码的字母组合”(java)
  • 【初级篇】如何使用DeepSeek和Dify构建高效的企业级智能客服系统
  • stable Diffusion 中的 VAE是什么
  • Maximize Rating
  • [动手学习深度学习]24. AlexNet
  • 神经网络的基本知识
  • 补充二分LIS
  • 【公务员考试】高效备考指南
  • 2018年全国职业院校技能大赛高职组-计算机网络应用竞赛竞赛样题F卷
  • 【C++】—— 一篇文章解决面试 继承菱形继承
  • A SURVEY ON POST-TRAINING OF LARGE LANGUAGE MODELS——大型语言模型的训练后优化综述——第一部分