没有满分的人必看！错误在这里！

P3367 【模板】并查集

寒·Kun @ 2018-07-21 19:50:52

本人最近正好在学并查列，发现了一个很容易错的东西！

转自 @封禁用户f8617dda的博客

  1. 并查列其实就是一棵树，把合并在一起的就作为父子关系，其实就是树中的“父亲表示法”

定义如下：

struct Node{
    int father;//父亲
}s[MAXN];//数组

  1. 很多人都不知道，其实有些数合并后他们就在同一个格子里面了。但很多时候在判断一个数是否是他的父亲或者他是我的父亲，但那个树假如是与一个树合并了的，那岂不是父亲就是合并的树？

错误代码如下：

switch(z){
    case 1:{
        s[y].father=x;
        break;
    }
    case 2:{
        if(s[y].father==x||s[x].father==y){
    printf("Y\n");
}else{
    printf("N\n");
}
    break;
    }
}

千万不可以这样！

所以就用到了并查列中的化简：就是如果一个树找目前的父亲，一定会找到这棵树的根。然而在查找的过程中，就可以把他的父亲的父亲标示移到他找到的根，这样一直下去就行了。

有需要知识课件的，私聊我（ 封禁用户名f8617dda）

记得点赞哦！

by Nero_Claudius @ 2018-07-21 19:57:36

@美玉无瑕 这玩意叫并查集Union Set。。。

by Nero_Claudius @ 2018-07-21 20:00:06

还有判断是否有共同祖先这样不就行了吗：

int find(int x){return (x==f[x])?x:f[x]=find(f[x])}
if(find(x)==find(y))cout<<"Y\n";
cout<<"N\n";

by 御·Dragon @ 2018-07-21 20:02:12

@DARTH_VADER 大佬我们交朋友把

by Taduro @ 2018-07-21 20:09:41

而且并查集肯定是路径压缩啊

by kitakami @ 2018-07-21 20:14:04

%%%大佬都学到并查列了，我才学到动态划分

by AThousandSuns @ 2018-07-21 20:14:28

@多弗桃 按秩合并教你做人（可持久化的毒瘤卡空间）

by 御·Dragon @ 2018-07-21 20:17:25

@DARTH_VADER @多弗桃 @AThousandSuns

求助！

#include<bits/stdc++.h>
using namespace std;
const int MAXN=200010;
struct Node{
    int father;
    int d;
}s[MAXN];
int n,m,z,x,y,k;
int dg(int p,int o){
    if(s[p].father==o)return 1;
    if(s[p].father!=s[p].d){
        p=s[p].father;
        dg(p,o);
    }
    if(s[p].father==s[p].d)return 0; 
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        s[i].d=i;
    }
    for(int i=1;i<=m;i++){
        scanf("%d",&z);
        scanf("%d %d",&x,&y);
        switch(z){
            case 1:{
                s[y].father=x;
                break;
            }
            case 2:{
                if(dg(y,x))printf("Y\n");
                else printf("N\n");
                break;
            }
        }
    }
    return 0;
}

by 御·Dragon @ 2018-07-22 10:21:12

@DARTH_VADER @多弗桃 @萝莉大法好 @AThousandSuns

改了一下，再次求助

#include<bits/stdc++.h>
using namespace std;
const int MAXN=20010;
int s[MAXN];
int n,m,z,x,y,k;
int fin(int p){
    if(s[p]==0)return p;
    fin(s[p]);
}
int main(){
    cin>>n>>m; 
    for(int i=1;i<=m;i++){
        scanf("%d",&z);
        scanf("%d %d",&x,&y);
        switch(z){
            case 1:{
                s[y]=x;
                break;
            }
            case 2:{ 
                if(fin(y)==fin(x))printf("Y\n");
                else printf("N\n");
            }
        }
    }
    return 0;
}
//样例过了，但10分

by Nero_Claudius @ 2018-07-22 10:31:16

@封禁用户名f8617dda 本人AC代码

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

const int N=10010;

int n,m,z,x,y;

struct Unionset{
    private:
        int f[N];
    public:
        Unionset(){
            for(int i=1;i<=n;i++)f[i]=i;
        }
        int find(int x){if(x==f[x])return x;return f[x]=find(f[x]);}
        void merge(int x,int y){x=find(x),y=find(y);if(x!=f[y])f[y]=x;return;}
};

int main(){
    cin>>n>>m;
    Unionset U;
    for(int i=0;i<m;i++){
        cin>>z>>x>>y;
        if(z==1)U.merge(x,y);
        else{if(U.find(x)==U.find(y))cout<<"Y\n";else cout<<"N\n";}
    }return 0;
}

by 御·Dragon @ 2018-07-22 10:34:38

@DARTH_VADER 当然感谢你的好意，但是只要求用本人的超烂算法搞懂就行了。谢谢！

| 下一页