染色法

二分图一、定义二、应用三、算法模板① 染色法模板② 匈牙利模板 - 邻接表③ 匈牙利模板 - 邻接矩阵废话不多说，本苟蒻发文，有任何问题欢迎大佬斧正~（＞人＜；） 一、定义图的节点由两个集合 u、v…

文章目录前言Part 1：染色法判定二分图1.题目描述输入格式输出格式数据范围输入样例输出样例 2.算法 Part 2：匈牙利算法求二分图的最大匹配1.题目描述输入格式输出格式数据范围输入样例输出样例 2.算法前言本篇博客将介绍两种二分图有关的算法&#xf…

知识概览一个图是二分图当且仅当图中不含奇数环（奇数环是边数为奇数的环）。图中不含奇数环，染色过程中一定没有矛盾。染色法判定二分图算法时间复杂度O(n m)。例题展示题目链接 860. 染色法判定二分图 - AcWing题库https://www.acwing.…

题面题解二分图定义：图中点可分为两个集合，每个集合中的点互不相邻二分图性质：当且仅当图中不含奇数环(充要条件) 2. 对于染色过程，我们用树/图的深度遍历，如果当前节点没有染色，就将其染成1&#xff0c…

题面题解我们将罪犯当作点，罪犯之间的仇恨关系当作点与点之间的无向边，边的权重就是罪犯之间的仇恨值，那么原来的问题就转化成了把所有点分成两组，使得各组内的边的权重的最大值最小我们在[0,1e9] 之间二分枚举最大权值x&#…