题目链接:poj 2492 A Bug's Life
题目大意:一个博士在做一个关于动物性爱的实验,给出n和m,表示有n个虫子,和m次性交,每次给出两个虫子的序号,表示这两只虫子发生过关系。问说是否有发生同性恋的可能。
解题思路:带权并查集裸体。
#include <stdio.h>
#include <string.h>
const int N = 1e6+5;
int n, m, f[N], v[N];
int getfar(int x) {
if (x != f[x]) {
int t = f[x];
f[x] = getfar(f[x]);
v[x] = (v[x] + v[t])%2;
}
return f[x];
}
void init () {
scanf("%d%d", &n, &m);
for (int i = 0; i <= n; i++) {
f[i] = i;
v[i] = 0;
}
}
bool judge () {
bool flag = false;
int a, b;
for (int i = 0; i < m; i++) {
scanf("%d%d", &a, &b);
int p = getfar(a), q = getfar(b);
if (p == q) {
if (v[a] == v[b]) flag = true;
} else {
f[q] = p;
v[q] = v[a] + 1 - v[b];
}
}
return flag;
}
int main () {
int cas;
scanf("%d", &cas);
for (int i = 1; i <= cas; i++) {
init ();
printf("Scenario #%d:\n%s bugs found!\n", i, judge() ? "Suspicious" : "No suspicious");
if (i != cas) printf("\n");
}
return 0;
}
分享到:
相关推荐
poj2492 A Bug's Life并查集应用的扩展,希望可以给大家带来用处
POJ 1988 并查集。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
poj 食物链代码.带权并查集,关键是找到其中的一些关系式.
北大POJ2586-Y2K Accounting Bug 解题报告+AC代码
这份代码用C++实现了经典算法并查集,来源于poj题目1182
北大POJ2488-A Knight's Journey 解题报告+AC代码
并查集基础 acm 算法 poj oi 并查集基础.ppt
poj 1611 The Suspects 代码 并查集的应用
POJ1089 并查集可以解决 并查集加路径压缩
数据结构并查集的相关资料,包括几篇并查集的论文,还有POJ上面几道关于并查集的题目的源代码
Net<br>Pku acm 3278 Catch That Cow<br>Pku acm 2253 Frogger<br>Pku acm 1062 昂贵的聘礼 Pku acm 1125 Stockbroker Grapevine Pku acm 1611 The Suspects Pku acm 2492 A Bug's Life 更多请访问:...
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ1584-A Round Peg in a Ground Hole 解题报告+AC代码
北大POJ2262-Goldbach's Conjecture 解题报告+AC代码
北大POJ2388-Who's in the Middle 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
里面有非常详细的对于POJ 2411的解题报告,相信对于初学动态规划和深度优先搜索的同学来说有很好的帮助作用。
poj 3294 Life Forms.md
北大POJ1942-Paths on a Grid 解题报告+AC代码
poj 4003 Bob’s Race.md