二分图算法

算法"/>

二分图算法

文章目录

• • 二分图
  • • 染色法
    • 匈牙利算法
    • 参考

二分图

染色法

二分图当且仅当图中不含奇数环。由于图中不含有奇数环，所以染色过程中一定没有矛盾。
860. 染色法判定二分图
给定吧一个n个点m条边的无向图，图中可能存在重边和自环。
请你判断这个图是否是二分图。
输入格式
第一行两个整数n和m。
接下来m行，每行包含两个整数u和v，表示u和v之间存在一条边。
输出格式
如果给定图是二分图，则输出Yes，否则输出No。
数据范围
1 ≤ n , m ≤ 1 0 5 1\leq n,m \leq 10^5 1≤n,m≤105
输入样例：

4 4
1 3
1 4
2 3
2 4

输出样例：

Yes

代码

#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 100010, M = 200010;int n, m;
int h[N], e[M], ne[M], idx;
int color[N];void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}bool dfs(int u, int c) {color[u] = c;for (int i = h[u]; i != -1; i = ne[i]) {int j = e[i];if (!color[j]) {if (!dfs(j, 3 - c)) return false;} else if (color[j] == c) return false;}return true;
}int main() {scanf("%d%d", &n, &m);memset(h, -1, sizeof h);while (m --) {int a, b;scanf("%d%d", &a, &b);add(a, b), add(b, a); }bool flag = true;for (int i = 1; i <= n; i ++) if (!color[i]) {if (!dfs(i, 1)) {flag = false;break;}}if (flag) puts("Yes");else puts("No");return 0;
}

匈牙利算法

861. 二分图的最大匹配
给定一个二分图，其中左半部分包含n1个点（编号1-n1), 右半部分包含n2个点（编号1-n2）, 二分图包含m条边。数据保证任意一条边的两个端点都不可能在同一部分中。
求二分图的最大匹配数。
输入格式
第一行包含三个整数n1，n2和m.
接下来m行，每行包含两个整数u和v，表示左半部点集中的点u和右半部点集中的点v之间存在一条边。
输出格式
输出一个整数，表示二分图的最大匹配数。
数据范围
1 ≤ n 1 , n 2 ≤ 500 1\le n1, n2 \le 500 1≤n1,n2≤500,
1 ≤ u ≤ n 1 1\le u \leq n1 1≤u≤n1,
1 ≤ v ≤ n 2 1 \leq v \leq n2 1≤v≤n2,
1 ≤ m ≤ 1 0 5 1 \leq m \leq10^5 1≤m≤105
输入样例

2 2 4
1 1
1 2
2 1
2 2

输出样例

2

代码

#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 510, M = 100010;int n1, n2, m;
int h[N], e[M], ne[M], idx;
int match[N];
bool st[N];void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}bool find(int x) {for (int i = h[x]; i != -1; i = ne[i]) {int j = e[i];if (!st[j]) {st[j] = true;if (match[j] == 0 || find(match[j])) {match[j] = x;return true;}}}return false;
}int main() {scanf("%d%d%d", &n1, &n2, &m);memset(h, -1, sizeof h);while(m --) {int a, b;scanf("%d%d", &a, &b);add(a, b);}int res = 0;for (int i = 1; i <= n1; i ++) {memset(st, false, sizeof st);if (find(i)) res ++;}printf("%d\n", res);return 0;
}

参考

搜索与图论（三）