点击打开链接poj 1703
思路: 简单带权并查集
分析:
1 题目要询问给定的x和y是否是同一个动物
2 我们假设如果不同,那么权值为1,否则为0。因此对于给定的x和y,那么如果x和y不在一个集合里面那么就是不确定,否则就可以根据rank来判断是什么关系
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 1e5+10;
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(x != father[x]){
int fa = father[x];
father[x] = find(fa);
rank[x] += rank[fa];
rank[x] %= 2;
}
return father[x];
}
void output(int x , int y , int fx , int fy){
if(fx != fy)
puts("Not sure yet.");
else{
if(rank[x] == rank[y])
puts("In the same gang.");
else
puts("In different gangs.");
}
}
int main(){
char ch;
int x , y;
int cas , n , m;
scanf("%d" , &cas);
while(cas--){
scanf("%d%d%*c" , &n , &m);
init(n);
while(m--){
scanf("%c %d %d%*c" , &ch , &x , &y);
int fx = find(x);
int fy = find(y);
if(ch == 'A'){
output(x , y , fx , fy);
}
else{
if(fx != fy){
father[fx] = fy;
rank[fx] = (rank[y]+1-rank[x]+2)%2;
}
}
}
}
return 0;
}
分享到:
相关推荐
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ3278-Catch That Cow 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj分类poj分类poj分类poj分类
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
搜索......................................................
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
北大POJ1159-Palindrome 解题报告+AC代码
poj 百练 题目分类 poj 百练 题目分类
POJ1083的代码,POJ1083的代码,POJ1083的代码
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
poj 1001答案
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
POJ1048,加强版的约瑟夫问题 难度中等
北大POJ2002-Squares 解题报告+AC代码
POJ2968代码有用,欢迎下载,POJ代码