做网站的实施过程,企业建设H5响应式网站的5大好处6,花木网站模版,高端网站建设kgu图论——二分图
二分图通俗解释 有一个图#xff0c;将顶点分成两类#xff0c;边只存在不同类顶点之间#xff0c;同类顶点之间设有边。称图 G 为二部图#xff0c;或称二分图#xff0c;也称欧图。 性质
二分图不含有奇数环图中没有奇数环#xff0c;一定可以转换为二…图论——二分图
二分图通俗解释 有一个图将顶点分成两类边只存在不同类顶点之间同类顶点之间设有边。称图 G 为二部图或称二分图也称欧图。 性质
二分图不含有奇数环图中没有奇数环一定可以转换为二分图
判断二分图——染色法dfs 可以用二染色方式染色那么就是二分图 代码 输入格式 第一行包含两个整数 n 和 m。 接下来 m 行每行包含两个整数 u 和 v表示点 u 和点 v 之间存在一条边。 输出格式 如果给定图是二分图则输出 Yes否则输出 No。 #include cstring
#include iostreamusing namespace std;const int N 1e5 10, M 2e5 10;// 链式前向星
int h[N], e[M], ne[M], idx;void add(int a, int b) {e[idx] b;ne[idx] h[a];h[a] idx ;
}// 各个点的颜色0 未染色1 是红色2 是黑色
int color[N];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() {memset(h, -1, sizeof h);int n, m;cin n m;while (m --) {int a, b;cin 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;
}二分图的最大匹配——匈牙利算法(详细证明请见《算法导论》) 匹配在图论中一个「匹配」是一个边的集合其中任意两条边都没有公共顶点。 最大匹配一个图所有匹配中所含匹配边数最多的匹配称为这个图的最大匹配 完美匹配如果一个图的某个匹配中所有的顶点都是匹配点那么它就是一个完美匹配。 交替路从一个未匹配点出发依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。 增广路从一个未匹配点出发走交替路如果途径另一个未匹配点出发的点不算则这条交替 路称为增广路agumenting path。 代码 输入格式 第一行包含三个整数 n1、 n2 和 m。 接下来 m 行每行包含两个整数 u 和 v表示左半部点集中的点 u 和右半部点集中的点 v 之间存在一条边。 输出格式 输出一个整数表示二分图的最大匹配数。 #include cstring
#include iostream
#include algorithmusing namespace std;const int N 510, M 100010;int h[N], e[M], ne[M], idx;void add(int a, int b) {e[idx] b;ne[idx] h[a];h[a] idx ;
}int match[N];
bool st[N];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] || find(match[j])) {match[j] x;return true;}}}return false;
}int main() {memset(h, -1, sizeof h);int n1, n2, m;cin n1 n2 m;while (m --) {int a, b;cin a b;add(a, b);}int res 0;for (int i 1; i n1; i ) {memset(st, 0, sizeof st);if (find(i)) res ;}cout res endl;return 0;
}
