二分图、匈牙利算法

2024-04-03 14:28
文章标签 算法 二分 匈牙利

本文主要是介绍二分图、匈牙利算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

一，二分图

CodeForces 687A NP-Hard Problem

力扣 785. 判断二分图

二，完全二分图

1，完全二分图

2，K2,3

3，K3,3

三，匈牙利算法

1，二分图最大匹配

2，其他图论问题

一，二分图

一般我们研究二分图默认指的是无向图。

二分图是指，可以把图中的顶点分成两个集合，使得每个集合中的所有点之间都是互不相连的。

	//判断是不是二分图, 节点编号是0到n-1static bool isTwoDivGraph(int n, UndirectedGraphData<int> &g) {UnionDif unions(n);for (auto e : g.edges) {unions.find(e.a);unions.find(e.b);if (unions.inSame(e.a, e.b)) {if (int(unions.getDif(e.a) + unions.getDif(e.b)) % 2)return false;}else {unions.merge(e.a, e.b,1);}}return true;}

CodeForces 687A NP-Hard Problem

题目：

Description

Recently, Pari and Arya did some research about NP-Hard problems and they found the minimum vertex cover problem very interesting.

Suppose the graph G is given. Subset A of its vertices is called a vertex cover of this graph, if for each edge uv there is at least one endpoint of it in this set, i.e.  or  (or both).

Pari and Arya have won a great undirected graph as an award in a team contest. Now they have to split it in two parts, but both of them want their parts of the graph to be a vertex cover.

They have agreed to give you their graph and you need to find two disjoint subsets of its vertices A and B, such that both A and B are vertex cover or claim it's impossible. Each vertex should be given to no more than one of the friends (or you can even keep it for yourself).

Input

The first line of the input contains two integers n and m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000) — the number of vertices and the number of edges in the prize graph, respectively.

Each of the next m lines contains a pair of integers ui and vi (1  ≤  ui,  vi  ≤  n), denoting an undirected edge between ui and vi. It's guaranteed the graph won't contain any self-loops or multiple edges.

Output

If it's impossible to split the graph between Pari and Arya as they expect, print "-1" (without quotes).

If there are two disjoint sets of vertices, such that both sets are vertex cover, print their descriptions. Each description must contain two lines. The first line contains a single integer k denoting the number of vertices in that vertex cover, and the second line contains kintegers — the indices of vertices. Note that because of m ≥ 1, vertex cover cannot be empty.

Sample Input

Input

4 2
1 2
2 3

Output

1
2 
2
1 3 

Input

3 3
1 2
2 3
1 3

Output

-1

题目大意就是把图分成二分图，如果不能的话，输出-1，如果能的话，分别输出2个部分的点的数量和点的标号。

代码：

#include<iostream>
#include<string.h>
using namespace std;int list[100005];
int fenzu[100005];int main()
{int n, m;cin >> n >> m;int fx, fy;memset(list, 0, sizeof(list));memset(fenzu, 0, sizeof(fenzu));int x, y;int zu = 1;while (m--){cin >> x >> y;		if (list[x] == 0){if (list[y] == 0){fenzu[x] = zu;fenzu[y] = zu;list[x] = 1;list[y] = 2;zu++;}else{fenzu[x] = fenzu[y];list[x] = 3 - list[y];}}else{if (list[y] == 0){fenzu[y] = fenzu[x];list[y] = 3 - list[x];}else{fx = fenzu[x];fy = fenzu[y];if (fx == fy){if (list[x] == list[y]){cout << "-1";return 0;}}else{					if (list[x] == list[y]){for (int i = 1; i <= n; i++)if (fenzu[i] == fy){fenzu[i] = fx;list[i] = 3 - list[i];}}					else for (int i = 1; i <= n; i++)if (fenzu[i] == fy)fenzu[i] = fx;}}}}int sum = 0;for (int i = 1; i <= n; i++)if (list[i] == 1)sum++;cout << sum << endl;for (int i = 1; i <= n; i++)if (list[i] == 1)cout << i<<" ";cout << endl << n - sum << endl;for (int i = 1; i <= n; i++)if (list[i] != 1)cout << i << " ";return 0;
}

可惜超时了，在test14超时了，test14估计是n和m非常大的了。

前面13个test都过了，想必这个代码是没有问题的，就是效率的问题。

很显然，主要的效率问题就是，在唯一的while循环里面，有1个从1到n的循环，只为了检索一些特定的目标出来。

所以很显然，我应该使用队列。

抛弃这个思想，用队列来做，其实很简单，只要记录每个点的所有邻居即可。

代码：

#include<iostream>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;vector<int>v[100005];
queue<int>q;
int list[100005];int main()
{int n, m;cin >> n >> m;int x, y;while (m--){cin >> x >> y;	v[x].insert(v[x].end(),y);v[y].insert(v[y].end(),x);}int k, key = 1;memset(list, 0, sizeof(list));vector< int >::iterator p;while (1){while (list[key])key++;if (key > n)break;q.push(key);list[key] = 1;while (!q.empty()){k = q.front();q.pop();for (p = v[k].begin(); p != v[k].end(); p++){if (list[*p] == list[k]){cout << "-1";return 0;}if (list[*p] == 0){q.push(*p);list[*p] = 3 - list[k];}}}}int sum = 0;for (int i = 1; i <= n; i++)if (list[i] == 1)sum++;cout << sum << endl;for (int i = 1; i <= n; i++)if (list[i] == 1)cout << i<<" ";cout << endl << n - sum << endl;for (int i = 1; i <= n; i++)if (list[i] != 1)cout << i << " ";return 0;
}

表面上有3层循环，实际上外面的2层while循环是有限制的，合起来也就是大约n而已。

里面的循环就更不用说了，3层循环合起来也就是大约n而已。

所以这个算法还是很快的，果然AC了。

力扣 785. 判断二分图

存在一个 无向图 ，图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给你一个二维数组 graph ，其中 graph[u] 是一个节点数组，由节点 u 的邻接节点组成。形式上，对于 graph[u] 中的每个 v ，都存在一条位于节点 u 和节点 v 之间的无向边。该无向图同时具有以下属性：

  • 不存在自环（graph[u] 不包含 u）。
  • 不存在平行边（graph[u] 不包含重复值）。
  • 如果 v 在 graph[u] 内，那么 u 也应该在 graph[v] 内（该图是无向图）
  • 这个图可能不是连通图，也就是说两个节点 u 和 v 之间可能不存在一条连通彼此的路径。

二分图 定义：如果能将一个图的节点集合分割成两个独立的子集 A 和 B ，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，就将这个图称为 二分图 。

如果图是二分图，返回 true ；否则，返回 false 。

示例 1：

输入：graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
输出：false
解释：不能将节点分割成两个独立的子集，以使每条边都连通一个子集中的一个节点与另一个子集中的一个节点。

示例 2：

输入：graph = [[1,3],[0,2],[1,3],[0,2]]
输出：true
解释：可以将节点分成两组: {0, 2} 和 {1, 3} 。

提示：

  • graph.length == n
  • 1 <= n <= 100
  • 0 <= graph[u].length < n
  • 0 <= graph[u][i] <= n - 1
  • graph[u] 不会包含 u
  • graph[u] 的所有值 互不相同
  • 如果 graph[u] 包含 v，那么 graph[v] 也会包含 u

c++代码：

class Solution {
public:bool isBipartite(vector<vector<int>>& graph) {map<int, vector<int>>m;for (int i = 0; i < graph.size(); i++)m[i] = graph[i];UndirectedGraphData<int> g(m);return UndirectedGraph::isTwoDivGraph(m.size(), g);}
};

rust代码：

struct Union{fa:Vec<usize>,dif:Vec<i32>,
}
impl Union{fn find(& mut self,x:usize)->usize{if self.fa[x] == x{return x;}Union::find(self,self.fa[x]);self.dif[x] += self.dif[self.fa[x]];self.fa[x] = self.fa[self.fa[x]];return self.fa[x];}fn in_same(& mut self,x:usize,y:usize)->bool{return Union::find(self,x) == Union::find(self,y);}fn merge(& mut self,x:usize,y:usize,x_sub_y:i32)->(){Union::find(self,x);let fax = self.fa[x];self.dif[fax] = x_sub_y - self.dif[x];self.fa[fax] = y;}
}impl Solution {pub fn is_bipartite(graph: Vec<Vec<i32>>) -> bool {let mut fa=Vec::new();let mut dif=Vec::new();for i in 0..graph.len(){fa.push(i);dif.push(0);}let mut opt = Union{fa:fa,dif:dif};for x in 0..graph.len(){for y in graph[x].clone(){let y = y as usize;if opt.in_same(x, y){if (opt.dif[x]+opt.dif[y])%2 == 0{return false;}}else{opt.merge(x, y, 1);}}}return true;}
}

二，完全二分图

1，完全二分图

完全二分图是一种特殊的二分图，可以把图中的顶点分成两个集合，使得第一个集合中的所有顶点都与第二个集合中的所有顶点相连。

2，K2,3

3，K3,3

三，匈牙利算法

1，二分图最大匹配

思路：

从0开始，逐步扩展。

扩展方法：寻找类似于0-1-2-3-4-5的路径，把匹配“1-2 3-4”调整成匹配“0-1 2-3 4-5”，匹配数加1。

示例：

调整前：

寻找路径：

调整后：

模板代码：

参考ACM模板

2，其他图论问题

待更新

这篇关于二分图、匈牙利算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

原文地址:
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.chinasem.cn/article/873164。

相关文章

Java中的雪花算法Snowflake解析与实践技巧

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.
阅读更多...
使用雪花算法产生id导致前端精度缺失问题解决方案

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面：本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.
阅读更多...
Springboot实现推荐系统的协同过滤算法

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品（如商品、电影、音乐等）的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法（Collaborativ
阅读更多...
openCV中KNN算法的实现

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库，它提供了各
阅读更多...
springboot+dubbo实现时间轮算法

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n
阅读更多...
SpringBoot实现MD5加盐算法的示例代码

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.
阅读更多...
Java时间轮调度算法的代码实现

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组（时间轮）和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时
阅读更多...
如何通过Golang的container/list实现LRU缓存算法

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣：146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.
阅读更多...
golang字符串匹配算法解读

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt（KMP）算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串（称为
阅读更多...
通俗易懂的Java常见限流算法具体实现

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》：本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2