图论——二分图
二分图:
图中所有点可以分成两个点集,使得图中所有边都是在集合之间的,即,同一个集合内的点之间没有边。
1、所有二分图算法
2、染色法
用于判断一个图是否是二分图。
重要性质:一个图是二分图,当且仅当该图中不含奇数环(环中边数量是奇数)。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10;
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;
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()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while (m--)
{
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
int flag = true;
for (int i = 1; i <= n; i++)
if (!color[i])
{
if (!dfs(i, 1))
{
flag = false;
}
}
if (flag) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}
考虑一个问题:
dfs
里面把 if( !dfs(j, 3 - c) ) return false;
改成直接return dfs(j, 3 - c);
为什么不行?
注意下面两段代码的区别:
①
if ( !color[j] )
if (!dfs(j , 3 - c)) return false;
②
if ( !color[j] )
return dfs(j , 3 - c);
①只可能返回 false
(或根本不返回),永远不会返回 true
,即,只会在dfs
失败的情况下返回主函数,dfs
成功不会返回主函数。
而②可能返回 true
或false
,即,dfs
成功或失败都返回主函数。
对于dfs
失败的情况,只要一个dfs
失败,那这个图肯定不是二分图,不用继续遍历其他的邻点。
但对于dfs
成功的情况,一个dfs
染色的可能只是图中的一个连通块,一个连通块符合二分图并不代表整个图是二分图,所以不能直接返回true
还要继续遍历其他的邻点,只有所有的dfs
都是true,整个图才是二分图。
上面的话总结的普遍一点:
对于返回false
的情况,只要局部返回false
,那整体肯定是false
的。但对于返回true
的情况,局部返回 true
并不代表整体也是true
,所以不能直接根据局部的true
就断定整体的true
,还需要继续遍历,只有所有的局部都是true
,整体才是true
。
3、匈牙利算法
给定一个二分图,求它的最大匹配。
实际运行时间一般远小于O(n*m)
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 510, M = 1e5 + 10;
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;
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()
{
cin >> n1 >> n2 >> m;
memset(h, -1, sizeof h);
while (m--)
{
int a, b;
cin >> a >> b;
add(a, b);
}
int res = 0;
for (int i = 1; i <= n1; i++)
{
memset(st, false, sizeof st);
if (find(i)) res++;
}
cout << res << endl;
return 0;
}