网站建设中的咨询服务,网站建设的系统设计,恩城seo的网站,网站建设制作确认单目录 1 基础知识2 模板3 工程化 1 基础知识
二分图#xff1a;每条边连接的起点和终点#xff0c;分别属于集合A和集合B。
一个图是二分图#xff0c;当且仅当#xff0c;图中不含奇数环#xff08;即#xff0c;回环中的结点数目是奇数#xff09;。
染色法判定二分… 目录 1 基础知识2 模板3 工程化 1 基础知识
二分图每条边连接的起点和终点分别属于集合A和集合B。
一个图是二分图当且仅当图中不含奇数环即回环中的结点数目是奇数。
染色法判定二分图的关键步骤为
初始化颜色数组color[1~n] 0。遍历每一个结点a如果它没有被染色将其染色为1即dfs(a, 1)。如果没有矛盾则说明该图是二分图否则不是。
bool dfs(int x, int c) {color[a] c;//递归处理它的子结点for (auto b : g[a]) {if (!color[b]) {if (!dfs(b, 3 - c)) return false; } else {if (color[b] c) return false;}}return true;
}2 模板
int n; // n表示点数
int h[N], e[M], ne[M], idx; // 邻接表存储图
int color[N]; // 表示每个点的颜色-1表示未染色0表示白色1表示黑色// 参数u表示当前节点c表示当前点的颜色
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] -1){if (!dfs(j, !c)) return false;}else if (color[j] c) return false;}return true;
}bool check()
{memset(color, -1, sizeof color);bool flag true;for (int i 1; i n; i )if (color[i] -1)if (!dfs(i, 0)){flag false;break;}return flag;
}3 工程化
题目1请判断该图是否为二分图。
#include iostream
#include cstring
#include vectorusing namespace std;const int N 1e5 10;
int n, m;
vectorvectorint g(N);
int color[N];bool dfs(int a, int c) {color[a] c;//看结点a能走到哪儿for (auto b : g[a]) {if (!color[b] !dfs(b, 3 - c)) return false;if (color[b] color[b] c) return false;}return true;
}int main() {cin n m;int a, b;while (m--) {cin a b;g[a].emplace_back(b);g[b].emplace_back(a);}bool flag true;for (int i 1; i n; i) {if (!color[i] !dfs(i, 1)) {flag false;break;}}if (flag) {cout Yes endl;} else {cout No endl;}return 0;
}
