并查集

关于并查集,真的是头发都焦的没得了,先说说我对并查集的理解,并查集说白了就是类似于学生时代的小团体,只要关系性质是一样的,
就是一个团体,是一个集合。往往许多题上有很明显的关系条件的时候,就可以让并查集出马了。
整个并查集的运用就是在对关系的充分理解以及运用的基础上,且并查集往往和其他一起考察。

poj2912

题意

有n个人分成3组玩石头剪刀布,同一组的人出的都是一样的;
只有一个人是裁判,随意出;
找出哪个是才判,并且判断在进行到哪一局时可以判断出裁判。

分析

  • 0~N-1 维护 <
  • N~2N-1 维护 =
  • 2N~3N-1 维护 >

且为了避免输入的时候有 1<2 2="" 、="">1这种情况,维护之后就会发生错误,所以对符号两边的数字大小要进行处理。
维护之后,枚举裁判,由裁判的游戏都跳过,如果剩下的没发生矛盾,这就是一个裁判,另外关于他在什么时候
判定这个人是裁判的,我是看的别人的方法:
看看我们枚举其他人时,比如我们假设第一个人是裁判时,第二局出错了,那说明第二句就断定了第一个人不是裁判;
以此来算,我们找到裁判后,其他所有的出错局数最大的就是我们判断的步数;因为到了这一步,可以断定其他人都不是裁判了;

源码(WA)

#include<iostream>
#include<vector>
using namespace std;

vector<int> par;
vector<int> rank;
#define maxv 510
bool judge[maxv];
int pos[maxv];
int N, M;
struct Node{
int a, b;
char op;
};
Node step[2100];

void init(int n){
par.clear();
rank.clear();
par.reserve(n);
rank.reserve(n);
for (int i = 0; i < n;i++){
par.push_back(i);
rank.push_back(0);
}
}

int find(int a){
if(par.at(a)==a)
return a;
return par.at(a) = find(par.at(a));
}

void unite(int a, int b){
a = find(a);
b = find(b);
if(a==b)
return;
if(rank.at(a)<rank.at(b))
par.at(a) = b;
else{
par.at(b) = a;
if(rank.at(a)==rank.at(b))
rank.at(a)++;
}
}

bool same(int a, int b){
return find(a)==find(b);
}

int main(){
while(cin>>N>>M){
init(N * 3); //0~N-1 小于, N~2N-1 等于, 2N~3N-1 大于
for (int i = 0; i < N;i++){
judge[i] = true;
pos[i] = -1;
}
for (int i = 0; i < M;i++){
cin >> step[i].a >> step[i].op >> step[i].b;
switch(step[i].op){
case '=':
break;
case '<':
if(step[i].a>step[i].b){
swap(step[i].a, step[i].b);
step[i].op = '>';
}
break;
case '>':
if(step[i].a>step[i].b){
swap(step[i].a, step[i].b);
step[i].op = '<';
}
break;
}
}
int count = 0;
bool flag = false;
for (int j = 0; j < N;j++){
init(N * 3);
for (int i = 0; i < M;i++){
flag = false;
if(step[i].a==j||step[i].b==j)
continue;
switch(step[i].op){
case '<':
if(same(step[i].a+N,step[i].b+N)||same(step[i].a+2*N,step[i].b+2*N)){
judge[j] = false;
pos[j] = i + 1;
flag = true;
break;
}
unite(step[i].a, step[i].b);
break;
case '=':
if(same(step[i].a,step[i].b)||same(step[i].a+2*N,step[i].b+2*N)){
judge[j] = false;
pos[j] = i + 1;
flag = true;
break;
}
unite(step[i].a+N,step[i].b+N);
break;
case '>':
if(same(step[i].a+N,step[i].b+N)||same(step[i].a,step[i].b)){
judge[j] = false;
pos[j] = i + 1;
flag = true;
break;
}
unite(step[i].a+2*N,step[i].b+2*N);
break;
}
if(flag==true)
break;
}
}
int res = 0;
int maxRes = 0;
for(int k=0;k<N;k++){
if(judge[k]==true){
count++;
res = k;
}
else{
if(maxRes<pos[k])
maxRes = pos[k];
}
}
if(count==0)
cout << "Impossible" << endl;
else if(count>1){
cout << "Can not determine" << endl;
}
else{
cout << "Player " << res << " can be determined to be the judge after " << maxRes <<" lines" << endl;
}
}
return 0;
}

关于

做题最怕遇到的就是这种情况,所有的能找到的数据都过了,但是提交上去就WA了,一天了,还是没改对,所以先放在这里,以后再遇到
类似的题或者再做这个专题的时候,再回过来看看。

后续(3.18)

经好友良某的提醒,终于找出了逻辑上的错误,果然还是分析的时候不够细致啊。
在上述代码中,如果输入1<22<3,那么就会并到一起时就会默认1<3了,这看起来没什么不对,但这是个划拳游戏啊,是不可能得到1<3的。

poj1308

题意

tree
判断是否是一棵树,如图中只有3不是。

分析

这题可以用树的性质来做,但因为我是做的专题,就从并查集的角度来分析:

  • 如果一个节点有两个父节点,不是树,相当于关系矛盾了。
  • 如果有环(自环),不是树
  • 如果全部节点不在一个集合里,不是树

源码(MLE)

#include<iostream>
#include<vector>
using namespace std;

vector<int> par;
int maxCin = 0;


void init(){
maxCin = 0;
par.clear();
par.reserve(0);
}

int find(int a){
if(par.at(a)==a)
return a;
return par.at(a) = find(par.at(a));
}

void unite(int a, int b){
int temp = a > b ? a : b;
if(temp>maxCin){
maxCin = temp;
for (int i = par.size(); i < maxCin + 1;i++){
par.push_back(i);
}
}
par.at(b) = a;
}

bool helpsame(int a, int b){
int temp = a > b ? a : b;
if(temp>maxCin){
maxCin = temp;
for (int i = par.size(); i < maxCin + 1;i++){
par.push_back(i);
}
}
if(par.at(b)!=b)//该节点已经有父节点
return true;
else
return false;
}

bool same(int a, int b){//用来查是否只存在一个连通分量
return find(a) == find(b);
}

int main(){
int a, b;
init();
int count = 0;
bool flag = false;
while(cin>>a>>b){
if(a==-1&&b==-1)
break;
else if(a==0&&b==0){
// for (int k = 0; k < par.size();k++){
// int x = find(k);
// cout << x << " ";
// }
count++;
if(flag==true)
cout << "Case " << count << " is not a tree." << endl;
else{
for (int i = 0; i < par.size();i++){
if(par.at(i)==i)
continue;
for (int j = 0; j < par.size();j++){
if(par.at(j)==j)
continue;
if(!same(i,j))
flag = true;
break;
}
if(flag==true)
break;
}
if(flag==true)
cout << "Case " << count << " is not a tree." << endl;
else
cout << "Case " << count << " is a tree." << endl;
}
init();
flag = false;
}
else{
if(helpsame(a,b)){
flag = true;
//cout << "a" << a << "--" << b << endl;
}
else if(a==b){
flag = true;
//cout << a << "--" << b << "b" << endl;
}
else{
unite(a, b);
}
}
}
return 0;
}

关于

这道题我读完题之后,第一反应就是没给输入的范围,自然而然的就用vector来实现。
而且我的代码是那么的节约内存了都,怎么都不明白怎么会MLE的。
网上的代码我复制过来提交了的,居然AC了,那份代码还是默认的输入的数据大小不会超过100!

poj1417

emmmm

题意:好人说的真话,坏人说的谎话。
这道题题读了半天才读懂,后来发现读懂了还是不会做,而且绕口,比如:
如果一个人说他自己是好人,他究竟是好人还是坏人。
emmmmm,留着,以后再来。