路由侠怎么做网站映射,观澜小学 网站建设,wordpress always,手机版桂林生活网官网二分图当且仅当一个图中不含奇数环
1.染色法
简单来说#xff0c;将顶点分成两类#xff0c;边只存在于不同类顶点之间#xff0c;同类顶点之间没有边。
e.g. 如果判断一个图是不是二分图#xff1f; 开始对任意一未染色的顶点染色。 判断其相邻的顶点中#xff0c;若未…二分图当且仅当一个图中不含奇数环
1.染色法
简单来说将顶点分成两类边只存在于不同类顶点之间同类顶点之间没有边。
e.g. 如果判断一个图是不是二分图 开始对任意一未染色的顶点染色。 判断其相邻的顶点中若未染色则将其染上和相邻顶点不同的颜色。 若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图若颜色不同则继续判断。 bfs和dfs可以搞定 注意如果有三个点另外成环整个环是一个孤立环其他都满足二分图但是这个孤立不满足二分图二分图的点不一定连通。所以要遍历每一个点。 1.dfs思路
#include iostream
#include cstring
#include algorithm
using namespace std;
const int N200010;
int e[N], ne[N], idx;//邻接表存储图
int h[N];
int n,m;
int color[N];
void add(int a, int b)//邻接表插入点和边
{e[idx] b, ne[idx] h[a], h[a] idx;
}
bool dfs(int a,int c){color[a]c;for(int ih[a];i!-1;ine[i]){int je[i];if(!color[j]){if(!dfs(j,3-c)){return false;}}else{if(color[j]c){return false;}}}return true;
}
int main(){memset(h, -1, sizeof h);//初始化邻接表cin n m;for(int i 1; i m; i)//读入边{int a, b;cin a b;add(a, b), add(b, a);}for(int i1;in;i){if(!color[i]){if(!dfs(i,1)){puts(No);return 0;}}}puts(Yes);return 0;
}
2.bfs思路
#include iostream
#include cstring
#include algorithm
#include queue
using namespace std;
const int N200010;
int e[N], ne[N], idx;//邻接表存储图
int h[N];
int n,m;
int color[N];queueint q;
void add(int a, int b)//邻接表插入点和边
{e[idx] b, ne[idx] h[a], h[a] idx;
}
bool bfs(int a){color[a]1;q.push(a);while(q.size()){auto tq.front();q.pop();for(int ih[t];i!-1;ine[i]){int je[i];if(!color[j]){color[j]3-color[t];q.push(j);}else if(color[j]color[t]) return false;}}return true;
}
int main(){memset(h, -1, sizeof h);//初始化邻接表cin n m;for(int i 1; i m; i)//读入边{int a, b;cin a b;add(a, b), add(b, a);}for(int i1;in;i){if(!color[i]){if(!bfs(i)){puts(No);return 0;}}}puts(Yes);return 0;
}
2.匈牙利算法 要了解匈牙利算法必须先理解下面的概念 匹配在图论中一个「匹配」是一个边的集合其中任意两条边都没有公共顶点。 最大匹配一个图所有匹配中所含匹配边数最多的匹配称为这个图的最大匹配。 这篇文章把这个算法讲的很有意思
趣写算法系列之--匈牙利算法_匈牙利算法基本原理-CSDN博客 简单来说就是 遍历所有男生 让该男生考虑所有心动女生 如果当前女生单身或者该女生的对象找了备胎该女生就接受该男生 最坏时间复杂度 O(nm)和其它最大流问题一样实际比较快 #include cstring
#include iostream
#include algorithmusing 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 ih[x];i!-1;ine[i]){int je[i];if(!st[j]){st[j]1;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;
} 在上述代码中有一个令人费解的东西就是st数组的作用其实直白的理解如果你每次不把st重新置为false那剩下的人一看到前面的妹子st已经为true不去让妹子的对象换掉这个妹子直接就放弃了会影响最后结果。
我们通过一个实际案例理解一下 不难看出st数组主要是在两个人连接了一个妹子的的时候才有用 这个st的存在让find在本次找的时候原来的那个男生不会再找这个妹子只会找其他的。 还有一种理解st的理解可以参考操作系统中锁的概念。假如说左边的是进程右边的是资源。当进程i要访问资源j时为了避免其他进程在此时访问资源j需要对资源j加一个“锁”即st[j] true。当进程i访问完资源时为了让后续其他进程也能访问资源需要把锁解开即memset(st, false, sizeof st)。
