首页 > 代码库 > POJ 2492 A Bug's Life
POJ 2492 A Bug's Life
PS: 开始我用二分染色做了一下这道题目, 今天再用并查集解此题。 关键是表示二元关系。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int maxn = 2010; int f[maxn]; int mark[maxn]; int n, m; bool flag; //Accepted 676K 750MS G++ 1230B 2014-05-07 20:02:20 int getFather(int x) { if(x==f[x]) return x; int t = f[x]; f[x] = getFather(f[x]); mark[x] = (mark[x]+mark[t])%2; return f[x]; } void make(int a, int b) { int t1 = getFather(a); int t2 = getFather(b); if(t1 != t2) { f[t1] = t2; if((mark[a]+mark[b])%2==0) { mark[t1] = 1; } } else { if(mark[a]==mark[b]) { flag = false; } } } int main() { int x, y; int T; scanf("%d", &T); for(int t = 1; t <= T; t++) { scanf("%d%d", &n, &m); memset(mark, 0, sizeof(mark)); flag = true; for(int i = 1; i <= n; i++) f[i] = i; for(int i = 0; i < m; i++) { scanf("%d%d", &x, &y); make(x, y); } printf("Scenario #%d:\n", t); if(flag) { printf("No suspicious bugs found!\n"); } else { printf("Suspicious bugs found!\n"); } printf("\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。