个人网站开发盈利模式,创意咨询策划公司,商标注册需要多久,给别人做网站会连累自己吗数据结构、算法总述#xff1a;数据结构/算法 C/C-CSDN博客 二分图#xff1a;节点由两个集合组成#xff0c;且两个集合内部没有边的图。换言之#xff0c;存在一种方案#xff0c;将节点划分成满足以上性质的两个集合。 染色法
目的#xff1a;验证给定的二分图是否可… 数据结构、算法总述数据结构/算法 C/C-CSDN博客 二分图节点由两个集合组成且两个集合内部没有边的图。换言之存在一种方案将节点划分成满足以上性质的两个集合。 染色法
目的验证给定的二分图是否可以进行二色染色 时间复杂度是 O(nm) 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;
} 题目 860. 染色法判定二分图 - AcWing题库https://www.acwing.com/problem/content/862/ 匈牙利算法 我们可以看做一个月老在牵红线现在左边是男生右边是女生互相都有心仪的对象我们就要尽量每一个男生都好。然后就出现了一个图。 我们先看第一个男生他有两个心仪的对象先看第一个女生还是单身那就选第一个然后看下一位也是第一个单身就她了。但是第三位男生就出问题了他只有一位心仪的对象但是呢那位已经有对象了但是这位男生还是不放弃找到那个男朋友说“要不你换一换”。我们再一看确实还有一个备胎单身就换一个这样两个人都好最后一个也很正常直接匹配。所以总结出十六字真言待字闺中据为己有名花有主求他放手。 所以说这也告诉我们不要轻易放弃最后悔的不是做错而是错过。 时间复杂度 O(n*m)实际运形时间远小于n*m int n1, n2; // n1表示第一个集合中的点数n2表示第二个集合中的点数
int h[N], e[M], ne[M], 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] 0 || find(match[j])){match[j] x;return true;}}}return false;
}// 求最大匹配数依次枚举第一个集合中的每个点能否匹配第二个集合中的点
int res 0;
for (int i 1; i n1; i )
{memset(st, false, sizeof st);if (find(i)) res ;
} 题目 861. 二分图的最大匹配 - AcWing题库https://www.acwing.com/problem/content/863/
