采用DFS和黑白二著色的方法判定二分圖

vector<int> g[maxn];//鄰接表 int color[maxn];//1,2分別代表黑色和白色，0表示還沒著色，調用前要把color數組初始化為0 bool bipartite(int u) {//判斷結點u所在的聯通分量是否為二分圖 for (int i = 0; i < g[u].size(); ++i) {int v = g[u][i];//枚舉每條邊(u,v) if (color[v] && color[u] == color[v]) return false;//結點v已經著色，且和結點u顏色沖突 if (0 == color[v]) {color[v] = 3 - color[u];//給結點v著與結點u相反的顏色 if (!bipartite(v)) return false;}}return true; }

改寫成BFS，這樣搜索不會造成棧溢出，變量的意義與之前的相同

vector<int> g[maxn]; int color[maxn];bool bfs() {for (int i = 1; i <= n; ++i) {if (g[i].size() > 0 && 0 == color[i]) {queue<int> que;while (!que.empty()) que.pop();que.push(i);while (!que.empty()) {int u = que.front();que.pop();for (int i = 0; i < g[u].size(); ++i) {int v = g[u][i];if (color[v] && color[v] == color[u]) return false;if (color[v] == 0) {color[v] = 3 - color[u];que.push(v);}}}}}return true; }

模板題 hihocoder1121
題目鏈接 https://vjudge.net/problem/HihoCoder-1121

#include<bits/stdc++.h> using namespace std;const int maxn = 10050;int n, m; vector<int> g[maxn]; int color[maxn];void init() {memset(color, 0, sizeof(color));for (int i = 0; i < maxn; ++i) g[i].clear(); }bool bfs() {for (int i = 1; i <= n; ++i) {if (g[i].size() > 0 && 0 == color[i]) {queue<int> que;while (!que.empty()) que.pop();que.push(i);while (!que.empty()) {int u = que.front();que.pop();for (int i = 0; i < g[u].size(); ++i) {int v = g[u][i];if (color[v] && color[v] == color[u]) return false;if (color[v] == 0) {color[v] = 3 - color[u];que.push(v);}}}}}return true; }int main() {int t;scanf("%d", &t);while (t--) {init();scanf("%d%d", &n, &m);for (int i = 1; i <= m; ++i) {int from, to;scanf("%d%d", &from, &to);g[from].push_back(to);g[to].push_back(from);}bool ok = bfs();printf("%s\n", ok ? "Correct" : "Wrong");}return 0; }

轉載于:https://www.cnblogs.com/wafish/p/10465444.html

總結

以上是生活随笔為你收集整理的二分图的判定（模板）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。