首页 > 代码库 > poj 1703

poj 1703

题目大意:

城市里有两个帮派,D a b 代表ab不是一个帮派的,A a b是问你这两个人事不是同一帮派的;

考察并查集

有两种算法;

第一种算法:D a b 的时候将a 和b+n  放到一个并查集,a+n和b放到一个并查集里;

我们就会得到如下的一个图;

1      1+n

2        2+n

3      3+n

n      n+n

重点来了如果1 与 2 在同一并查集,就说明1与2之间一定能找到一些线段相连,

而这些线段一定是偶数个,所以1与2一定是一伙的;

如果1与2+n相连那么同理,他俩不是一伙的;

其他情况就输出判断不了;

上代码

#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int maxa = 100005;
int father[maxa*2];
int Find(int i){//printf("*");
if(father[i] == i)
return i;
return father[i] = Find(father[i]);
}
int main(){
int t, n, m;
scanf("%d", &t);
while(t--){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n*2; i++)
father[i] = i;
while(m--){//printf("%d\n", m);
char c;
int a, b;
//printf("*");
scanf("\n%c%d%d", &c, &a, &b);
//printf("%d %d", a, b);
if(c == ‘D‘){
int fa = Find(a);
int fb = Find(b+n);
father[fa] = fb;
fa = Find(a+n);
fb = Find(b);
father[fa] = fb;
}else{
if(Find(a) == Find(b))
printf("In the same gang.\n");//printf("*");
else if(Find(a) == Find(b+n) || Find(a+n) == Find(b))
printf("In different gangs.\n");
else
printf("Not sure yet.\n");
}
}
}
}

==================================华丽的分割线===========================================================

第二种方法:

核心代码如下

int find(int i){
if(i == father[i])
return i;
int tt = find(father[i]);
rank[i] = (rank[i] + rank[father[i]])%2;
father[i] = tt;
return father[i];
}
int uniform(int a, int b){
int fa = find(a);
int fb = find(b);
rank[fa] = (rank[a] + rank[b] +1)%2;
father[fa] = fb;
}

rank的值有两种0和1,分别代表两种帮派。

所有的根节点rank都为零

uniform部分:对a的最上级修改,如果是对a修改的话那么显然应该将a修改成rank[b]+1;而a的rank值如果为零那么a的最上级就应该就和a一样修改成rank[b]+1;

当a不等于0时就不用说了;

接下来看find部分:

边查询的时候对rank[i]修改

如果上一级rank一样,那么就修改,由于递归的特性修改当前值的时候上一级已经修改过了,所以可以保证正确性

而算法正确性的跟本保证在与每次修改都会father都会指向根结点,而且根结点的rank为零

这样就保证了如果根节点发生变化find的时候rank[I]的值只会改变一次(这句话很重要)

以上就是算法的正确性;

上代码

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const int maxa = 100005;
int father[maxa];
int rank[maxa];
int find(int i){
if(i == father[i])
return i;
int tt = find(father[i]);
rank[i] = (rank[i] + rank[father[i]])%2;
father[i] = tt;
return father[i];
}
int uniform(int a, int b){
int fa = find(a);
int fb = find(b);
rank[fa] = (rank[a] + rank[b] +1)%2;
father[fa] = fb;
}
int main(){
int t, m, n;
scanf("%d", &t);
while(t--){
scanf("%d%d", &n, &m);
for(int i = 1; i <=n ; i++)
rank[i] = 0;
for(int i = 1; i <= n; i++){
father[i] = i;
}
while(m--){
char c;
int a, b;
scanf("\n%c%d%d", &c, &a, &b);
if(c == ‘D‘){
uniform(a, b);
}else{
if(n == 2){
printf("In different gangs.\n");
continue;
}
if(find(a) == find(b))
if(rank[a] == rank[b])
printf("In the same gang.\n");
else
printf("In different gangs.\n");
else
printf("Not sure yet.\n");
}
}
}
}