点击打开链接poj 2492
思路:带权并查集
分析:
1 用rank[i] = 0表示关系相同,用rank[i] = 1表示关系不同
2 在输入的时候把两个元素之间的关系建立起来,然后判断当前的两个元素是否在同一个集合里面,如果是则判断是不是属于同一个类型即可。
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN = 2010;
int father[MAXN];
int rank[MAXN];
void init(int n){
memset(rank , 0 , sizeof(rank));
for(int i = 1 ; i <= n ; i++)
father[i] = i;
}
int find(int x){
if(father[x] != x){
int fa = father[x];
father[x] = find(fa);
rank[x] = (rank[x]+rank[fa])%2;
}
return father[x];
}
bool solve(int x , int y){
int fx = find(x);
int fy = find(y);
if(fx != fy){
father[fx] = fy;
rank[fx] = (rank[y]+1-rank[x]+2)%2;
return true;
}
else{
return rank[x] != rank[y];
}
}
int main(){
int n , m , x , y;
int cas = 1 , Case;
scanf("%d" , &Case);
while(Case--){
scanf("%d%d" , &n , &m);
init(n);
bool isOk = true;
printf("Scenario #%d:\n" , cas++);
while(m--){
scanf("%d%d" , &x , &y);
if(!solve(x , y))
isOk = false;
}
if(!isOk)
puts("Suspicious bugs found!");
else
puts("No suspicious bugs found!");
puts("");
}
return 0;
}
分享到:
相关推荐
poj2492 A Bug's Life并查集应用的扩展,希望可以给大家带来用处
北大POJ2586-Y2K Accounting Bug 解题报告+AC代码
北大POJ2488-A Knight's Journey 解题报告+AC代码
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
北大POJ2031-Building a Space Station【Prim+计算几何】 POJ2031-Building a Space Station【Prim+计算几何】
poj分类poj分类poj分类poj分类
POJ2528-Mayor's posters 测试数据。数据来源:Alberta Collegiate Programming Contest 2003.10.18 – 问题G
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj-2528 Mayor's posters 测试数据及答案
北大POJ1005-I Think I Need a Houseboat 解题报告+AC代码
北大POJ1691-Painting A Board 【拓扑+DFS】 解题报告+AC代码