本文主要是介绍A Bug's Life POJ - 2492(一题多解，二分图思路)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
今天看《挑战》看到一种新的算法，二分图染色问题，然后突然想起之前做的一道带权并查集问题详细见链接
二分图问题是给定一个图判断能否将其染色保证任意两相连点的颜色不一样（只能染两种颜色～）
代码
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;const int maxn = 2200;vector<int> G[maxn];
int color[maxn];int n, m;bool dfs(int u, int c) {color[u] = c;for(int i = 0; i < G[u].size(); i++) {if (color[G[u][i]] == c) return false;if (color[G[u][i]] == 0 && !dfs(G[u][i], -c)) return false;}return true;
}void solve() {for(int i = 1; i <= n; i++) {if (color[i] == 0) {if (!dfs(i, 1)) {printf("Suspicious bugs found!\n\n");return;}}}printf("No suspicious bugs found!\n\n");
}int main() {// freopen("input.txt", "r", stdin);int T;int u, v;int kase = 0;scanf("%d", &T);while(T--) {memset(color, 0, sizeof(color));scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++) {G[i].clear();}while(m--) {scanf("%d%d", &u, &v);G[u].push_back(v);G[v].push_back(u);}printf("Scenario #%d:\n", ++kase);solve();}return 0;
}
这篇关于A Bug's Life POJ - 2492(一题多解，二分图思路)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
