算法

并查集

2019-06-05  本文已影响0人  Vincy_ivy

并查集是什么

并查集是一种用来管理元素分组情况的数据结构。并查集可以高效地进行如下操作。不过需要注意并查集虽然可以进行合并操作，但是却无法进行分割操作

 

并查集的结构

并查集也是使用树形结构实现的，不过不是二叉树。


分组和对应的树的例子

每个元素对应一个节点，每个组对应一棵树。在并查集中，哪个节点是哪个节点的父亲以及树的形状等信息无需多家关注，整体组成一个树形结构才是重要的。
 

（1）初始化

我们准备n个节点来表示n个元素。最开始时没有边。



 

（2）合并

像下图一样，从一个组的根向另一个组的根连边，这样两棵树就变成了一棵树，也就是把两个组合并为了一个组。


合并的例子

（3）查询

为了查询两个节点是否属于同一组，我们需要沿着树向上走，来查询包含这个元素的树的根是谁。如果两个节点走到了同一个根，那么就可以知道他们属于同一组。
在下图，2和5都走到了1，因此他们为同一组。另一方面，由于7走到的是6，因此与2和5属于不同组


查询的例子

 

并查集实现中的注意点

在树形数据结构中，如果发生了退化的情况，那么复杂度就会变得很高。因此有必要避免退化

在此之上，不仅仅是所查询的节点，在查询过程中向上经过的所有节点，都改为直接连到根上。这样再次查询这些节点时，就可以很快知道根是谁了。


路径压缩例子2

 

并查集的复杂度

 

并查集的实现

下面是并查集的实现的例子。在例子中，用编号代表每个元素，数组par表示的是父亲的编号，par[x]=x时，x是所在的树的根

int par[MAX_N];//父亲
int rank[MAX_N];//树的高度

//初始化n个元素
void init(int n){
    for(int i=0;i<n;i++){
        par[i]=i;
        rank[i]=0;
    }
} 

//查询树的根
int find(int x){
    if(par[x]==x)
        return x;
    else
        return par[x]=find(par[x]);
} 

//合并x和y所属的集合
void unite(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y)
        return;
    if(rank[x]<rank[y]){
        par[x]=y
    }else{
        par[y]=x;
        if(rank[x]==rank[y])
            rank[x]++;  
    }
} 

//判断x和y是否属于同一个集合
bool same(int x,int y){
    return find(x)==find(y);
}

 
 

食物链

这道题一直TLE的原因居然是cout和cin//翻白眼，虽然我早就知道可能会有这种后果~
题解
思路：
由于N和K很大，所以必须高效地维护动物之间的关系，并快速判断是否产生了矛盾。并查集是维护 “属于同一组” 的数据结构，但是在本题中，并不只有属于同一类的信息，还有捕食关系的存在。因此需要开动脑筋维护这些关系。
对于每只动物i创建3个元素i-A, i-B, i-C, 并用这3N个元素建立并查集。这个并查集维护如下信息：
① i-x 表示 “i属于种类x”。
②并查集里的每一个组表示组内所有元素代表的情况都同时发生或不发生。
例如，如果i-A和j-B在同一个组里，就表示如果i属于种类A那么j一定属于种类B，如果j属于种类B那么i一定属于种类A。因此，对于每一条信息，只需要按照下面进行操作就可以了。
1）第一种，x和y属于同一种类———合并x-A和y-A、x-B和y-B、x-C和y-C。
2）第二种，x吃y—————————合并x-A和y-B、x-B和y-C、x-C和y-A。
不过在合并之前需要先判断合并是否会产生矛盾。例如在第一种信息的情况下，需要检查比如x-A和y-B或者y-C是否在同一组等信息。
unite(x,y);表示xy同类
unite(x,y+N);表示x吃y
unite(x,y+2N);表示y吃x

代码

#include<cstdio>
#include<iostream>
using namespace std;
const int MAX_K = 150010;
const int MAX_N = 1e5+20;
int N,K;
int T[MAX_K],X[MAX_K],Y[MAX_K];
int par[3*MAX_N],rank[3*MAX_N];//T为信息类型 
//初始化n个元素
void init(int n){
    for(int i=0;i<n;i++){
        par[i]=i;
        rank[i]=0;
    }
} 

//查询树的根
int find(int x){
    if(par[x]==x)
        return x;
    else
        return par[x]=find(par[x]);
} 

//合并x和y所属的集合
void unite(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y)
        return;
    if(rank[x]<rank[y]){
        par[x]=y;
    }else{
        par[y]=x;
    }
    if(rank[x]==rank[y])
            rank[x]++;
} 

//判断x和y是否属于同一类 
bool same(int x,int y){
    return find(x)==find(y);
}

void solve(){
    init(N*3); 
    
    int ans=0;
    for(int i=0;i<K;i++){
        int t=T[i];
        int x=X[i]-1,y=Y[i]-1;//把输入变成0···N-1的范围
        
        //不正确编号
        if(x<0||N<=x||y<0||N<=y){
            ans++;
            continue;
        } 
                                                //第一种如果1 x y即：本条给定的信息是：x与y是同类
        if(t==1){
            //x和y属于同一类的信息
// 如果x吃y并且y也吃x，矛盾！说明此条信息有误
            if(same(x,y+N)||same(x,y+2*N)){
                ans++;
            }else{// 否则，x与y为同类的动物，则合并他们
                unite(x,y);
                unite(x+N,y+N);
                unite(x+2*N,y+2*N);
            }
        }else{                                      //第二种 
            //x吃y的信息
 // 如果x与y是同类或者y吃x，又矛盾，说明此条信息有误
            if(same(x,y)||same(x,y+2*N)){
                ans++;
            }else{// 否则，x可以吃y，则将这条关系添加到集合中
                unite(x,y+N);
                unite(x+N,y+2*N);
                unite(x+2*N,y);
            }
        }
    }
    printf("%d\n",ans);
}


int main(){
    cin>>N>>K;
    for(int i=0;i<K;i++)
        scanf("%d%d%d",&T[i],&X[i],&Y[i]);
    //初始化并查集
    //元素x，x+N，x+2*N 分别代表x-A，x-B，x-C
    solve();
    return 0;
}

 

畅通工程

#include<cstdio>
#include<iostream>
using namespace std;
const int MAX_K = 150010;
const int MAX_N = 1e5+20;
int n,m,par[1001];
//初始化n个元素
void init(int n){
    for(int i=1;i<=n;i++){
        par[i]=i;
    }
}

int find(int x){
    if(par[x]==x){
        return x;
    }else{
        return par[x]=find(par[x]);
    }
}

void unite(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y)
        return;
    if(x!=y)
        par[x]=y;

}

bool same(int x,int y){
    return find(x)==find(y);
}
int main(){
    int a,b;
    //freopen("data","r",stdin);
    while(~scanf("%d",&n)){
        if(n==0)
            break;
        else{
            scanf("%d",&m);
            int sum=0;          
            init(n);//n为节点
            //结合在一起 
            for(int i=0;i<m;i++){
                scanf("%d%d",&a,&b); 
                unite(a,b);
            }
            //如果根节点相同，则为同一组
            for(int i=1;i<=n;i++){
                if(par[i]==i)
                    sum++;
            }   
            printf("%d\n",sum-1);
        }
    
    }

    
    return 0;
}

 

The Suspects

每一个人与第一个人进行合并，再观察n个学生里有谁和第一个是同一组

#include<cstdio>
#include<iostream>
using namespace std;
int n,m,par[30001];
//初始化n个元素
void init(int n){
    for(int i=0;i<n;i++){
        par[i]=i;
    }
}

int find(int x){
    if(par[x]==x){
        return x;
    }else{
        return par[x]=find(par[x]);
    }
}

void unite(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y)
        return;
    if(x!=y){
        par[x]=y;
    }   
}

bool same(int x,int y){
    return find(x)==find(y);
}
int main(){
    int x,y,k;
//  freopen("data","r",stdin);
    while(scanf("%d%d",&n,&m)!=EOF&&(n||m)){
        init(n);
        for(int i=0;i<m;i++){
            //给出集合每个集合人数以及第一个人的编号 
            scanf("%d%d",&k,&x);
            k--;
            while(k--){
                scanf("%d",&y);
                unite(x,y);
            }
        }
        int sum=0;
        for(int i=0;i<n;i++)
            if(find(i)==par[0])
                sum++;
        printf("%d\n",sum);
        
    }
    return 0;
}

 

家族

#include<cstdio>
#include<iostream>
using namespace std;
int n,m,p,par[30001];
//初始化n个元素
void init(int n){
    for(int i=0;i<n;i++){
        par[i]=i;
    }
}

int find(int x){
    if(par[x]==x){
        return x;
    }else{
        return par[x]=find(par[x]);
    }
}

void unite(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y)
        return;
    if(x!=y){
        par[x]=y;
    }   
}

bool same(int x,int y){
    return find(x)==find(y);
}
int main(){
//  freopen("data","r",stdin);
    scanf("%d%d%d",&n,&m,&p);
    init(n);
    int a,b;
    for(int i=0;i<m;i++){
        scanf("%d%d",&a,&b);
        unite(a,b);
    }
    for(int i=0;i<p;i++){
        scanf("%d%d",&a,&b);
        if(find(a)==find(b))
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}

 

P1525 关押罪犯

这里的排序只是因为市长要根据最大的事件来进行判断。
“应如何分配罪犯，才能使Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？”这句话嘛，在使最大的事件不发生，求不得不发生的事件的最大值
以下是某个dalao的“敌人的敌人就是朋友”原则
（1）先把所有的矛盾关系按照矛盾值从大到小排一遍序，
（2）接下来每次操作取出一个关系，看矛盾的两个人x和y是否已经分配到同一个集合中（并查集找父亲即可），那么还分如下两种情况：
如果在一起那么显然会打起来（会出现矛盾），那么直接输出当前的边权（矛盾值）即可（此时保证是最小矛盾值，因为已经排序了）
如果不在同一组，则按照“敌人的敌人就是朋友”的原则，把x与y的其他敌人分在同一组，y与x的其他敌人分在同一组
不断进行以上操作最终可以得到答案

#include<cstdio>
#include<iostream>
//#include<bits/stdc++.h>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,p,par[300001],b[30001];
//初始化n个元素
struct ele{
    int a,b,p;
}ele[300001];

bool cmp(struct ele &x,struct ele &y){
    return x.p>y.p;
}

void init(int n){
    for(int i=1;i<=n;i++){
        par[i]=i;
    }
}

int find(int x){
    if(par[x]==x){
        return x;
    }else{
        return par[x]=find(par[x]);
    }
}

void unite(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y)
        return;
    if(x!=y){
        par[x]=y;
    }   
}

bool same(int x,int y){
    return find(x)==find(y);
}
int main(){
//  freopen("testdata.in","r",stdin);
    scanf("%d%d",&n,&m);
    init(n);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&ele[i].a,&ele[i].b,&ele[i].p);
    }
    sort(ele+1,ele+m+1,cmp);
    for(int i=1;i<=m+1;i++){
        if(find(ele[i].a)==find(ele[i].b)){
            printf("%d",ele[i].p);
            break;
        }else{
            if(!b[ele[i].a])//标记“敌人” 
                b[ele[i].a]=ele[i].b;
            else{
                unite(b[ele[i].a],ele[i].b);//将敌人的敌人合并 
            }
            if(!b[ele[i].b])
                b[ele[i].b]=ele[i].a;
            else{
                unite(b[ele[i].b],ele[i].a);
            }
        }    
    }
    return 0;
}
上一篇下一篇

猜你喜欢

热点阅读