首页 > 编程语言 >算法提高课 第四章 数据结构之并查集

算法提高课 第四章 数据结构之并查集

时间：2022-08-29 23:27:47浏览次数：89  
标签：结点 数据结构 return int 查集 集合 include find 第四章

image

一、并查集

image

1250. 格子游戏

思路 O(mlog(n))

  1. 将图中的每个点看作并查集的结点，每个被画的边看作合并相邻的点的操作
  2. 将图中所有点按行或列优先，从1~n*m进行编号
  3. 每次进行合并时，当两个结点属于一个集合时，说明找到了一个封闭的圈

题解

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 201*24001;

int p[N],n,m;

int turn(int x,int y) //二维编号转化为一维编号
{
    return (x-1)*m + y;
}

int find(int x) //合并操作
{
    if(p[x]!=x) return p[x] = find(p[x]);
    return p[x];
}


int main()
{
    cin>>n>>m;
    for(int i = 1;i<=n*m;i++) p[i] = i;
    for(int k = 1;k<=m;k++)
    {
        int x,y,a,b;
        char c;
        cin>>x>>y>>c;
        if(c == 'D') 
        {
            a = turn(x,y),b = turn(x+1,y);
        }
        else
        {
            a = turn(x,y),b = turn(x,y+1);
        }
        a = find(a),b = find(b);
        if(a==b) //每次进行合并时，当两个结点属于一个集合时，说明找到了一个封闭的圈
        {
            cout<<k<<endl;
            return 0;
        }
        else p[a] = b;//否则进行合并
    }
    puts("draw");//找不到封闭的圈
    return 0;
}

1252. 搭配购买

思路 O(N^2)：并查集+01背包

先用并查集将捆绑商品进行合并，再做一遍01背包问题

题解

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010;

int p[N],v[N],w[N];
int f[N];
int n,m,vol;

int find(int x)
{
    if(p[x]!=x) p[x] = find(p[x]);
    return p[x];
}
void merge(int a,int b)
{
    a = find(a),b = find(b);
    if(a!=b) //注意：只有非共同集合才可进行合并
    {
        
        v[a] += v[b];
        w[a] += w[b];
        p[b] = a;
    }
    return;
}
int main()
{
    cin>>n>>m>>vol;
    for(int i = 1;i<=n;i++)
    {
        cin>>v[i]>>w[i];
        p[i] = i;
    }
    while (m -- )
    {
        int a,b;
        cin>>a>>b;
        merge(a,b);
    }
    for(int i = 1;i <= n;i++)
    {
        if(p[i] == i) //只对祖先结点做01背包
        {
            for(int j = vol;j>=v[i];j--)
            {
                f[j] = max(f[j],f[j-v[i]] + w[i]);
            }
        }
    }
    
    cout<<f[vol]<<endl;
    return 0;
}

237. 程序自动分析

思路：离散化

image
由于变量的数据范围过大1e9，且约束关系使用到的变量个数最多为2e5，因此要离散化，由于无需关注变量间的大小关系，因此用无需离散化即可。

  1. 离散化
  2. 将所有相等条件的变量所在集合进行合并
  3. 对所有不等条件的变量进行判断，是否属于一个集合，属于则矛盾

题解

无序离散化

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;

const int N = 1e5 + 10;

map<int,int>S;
int T,n,cnt;
int p[N*2];
bool f;
struct Equ
{
    int x,y,e;
}equ[N]; //存储所有变量的关系

int get(int x) //将x进行无序离散化，返回离散化后的值
{
    if(!S.count(x)) //若未进行离散化，则先离散化
    {
        S[x] = ++cnt; //对于每个数，返回唯一的值即可，故可用序号作为离散化后的值，从1开始
    }
    return S[x];
}
int find(int x)
{
    if(p[x]!=x) p[x] = find(p[x]);
    return p[x];
}
void merge(int a,int b)
{
    a = find(a),b = find(b);
    if(a!=b)
    {
        p[a] = b;
    }
    return;
}
int main()
{
    scanf("%d", &T);
    while(T--)
    {
        f = true;
        cnt = 0;
        scanf("%d", &n);
        S.clear();
        for(int i = 0;i<n;i++)
        {
            int a,b,e;
            scanf("%d%d%d", &a, &b,&e);
            equ[i] = {get(a),get(b),e};//注意：存储离散化后的值，必须离线处理
        }
        for(int i = 1;i<=cnt;i++)
        {
            p[i] = i;
        }
        for(int i = 0;i<n;i++) //先将所有相等关系合并到一个集合
        {
            int a = equ[i].x,b = equ[i].y;
            if(equ[i].e)
            {
                merge(a,b);
            }
        }
        for(int i = 0;i<n;i++) //再进行矛盾分析，对于不等的两个变量，若它们在一个集合，说明矛盾
        {
            int a = equ[i].x,b = equ[i].y;
            if(!equ[i].e)
            {
                if(find(a) == find(b))
                {
                    f = false;
                    break;
                }
            }
        }
        if(f) puts("YES");
        else puts("NO");
    }
    return 0;
}

有序离散化

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

const int N = 1e5 + 10;

int T,n,cnt;
int p[N*2];
bool f;
struct Equ
{
    int x,y,e;
}equ[N]; //存储所有变量的关系

vector<int>alls;

int find(int x)
{
    if(p[x]!=x) p[x] = find(p[x]);
    return p[x];
}
void merge(int a,int b)
{
    a = find(a),b = find(b);
    if(a!=b)
    {
        p[a] = b;
    }
    return;
}

int get(int x)
{
    int l = 0,r = alls.size() - 1;
    while(l<r)
    {
        int mid = l+r>>1;
        if(x <= alls[mid]) r = mid;
        else l = mid + 1;
    }
    return l + 1;
}
int main()
{
    scanf("%d", &T);
    while(T--)
    {
        f = true;
        cnt = 0;
        scanf("%d", &n);
        alls.clear();

        for(int i = 0;i<n;i++)
        {
            int a,b,e;
            scanf("%d%d%d", &a, &b,&e);
            equ[i] = {a,b,e};//注意：存储离散化后的值，必须离线处理
            alls.push_back(a),alls.push_back(b);
        }
        sort(alls.begin(),alls.end());
        alls.erase(unique(alls.begin(),alls.end()),alls.end());
        cnt = alls.size();
        for(int i = 1;i<=cnt;i++)
        {
            p[i] = i;
        }
        for(int i = 0;i<n;i++) //先将所有相等关系合并到一个集合
        {
            equ[i].x = get(equ[i].x);
            equ[i].y = get(equ[i].y);
            int a = equ[i].x,b = equ[i].y;
            if(equ[i].e)
            {
                merge(a,b);
            }
        }
        for(int i = 0;i<n;i++) //再进行矛盾分析，对于不等的两个变量，若它们在一个集合，说明矛盾
        {
            int a = equ[i].x,b = equ[i].y;
            if(!equ[i].e)
            {
                if(find(a) == find(b))
                {
                    f = false;
                    break;
                }
            }
        }
        if(f) puts("YES");
        else puts("NO");
    }
    return 0;
}

238. 银河英雄传说

思路：并查集+维护距离

路径压缩中d[]距离的维护

  • d[x]:当前结点x到父节点p[x]的距离，find操作后会变成到集合根结点的距离
  • 合并集合时，假设把集合b挂到集合a下面，则集合b中所有元素的px变为a的根结点，此时到px距离需加上a的元素个数。
  • 我们运用前缀和思想，路径压缩时只给b集合的根结点的距离加上a的元素个数
  • 在路径压缩时，通过递归会给b中所有元素的距离加上a的元素个数
    image
    image

题解

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 30010;

int p[N];
int cnt[N];//当前集合的个数
int d[N]; //d[x]:结点x到p[x]的距离
int T,n;

int find(int x) //带距离p[x]维护的路径压缩与返回根结点
{
    if(p[x] != x) 
    {
        int root = find(p[x]);//先对p[x]进行操作，并找到根结点
        d[x] += d[p[x]]; //压缩后p[x]变为根结点，距离变为到px的距离+px到根结点的距离
        p[x] = root;//将根节点赋值给px，完成路径压缩
    }
    return p[x];//返回根结点
}
void merge(int a,int b) //a<-b 把b接到a上,前缀和思想：a集合中的d[]不变，b集合中的所有d[]加上cnt[pa]
{
    int pa = find(a),pb = find(b);
    if(pa!=pb)
    {
        p[pb] = pa;
        d[pb] += cnt[pa]; //给b的到根结点的距离加集合a中元素个数即可，后面路径压缩(find)操作会给b集合的
        //所有d[]加上cnt[pa]
        cnt[pa] += cnt[pb]; //合并时维护元素个数
    }
    return;
}

int main()
{
    scanf("%d", &T);
    for (int i = 1; i <= N; i ++ )
    {
        p[i] = i;
        cnt[i] = 1;
        //d[i] = 0;
        
    }
    while(T--)
    {
        char op[2];
        int x,y;
        scanf("%s%d%d", op,&x, &y);
        if(op[0] == 'M')
        {
            merge(x,y);
        }
        else
        {
            int px = find(x),py = find(y);
            if(x == y) //二者相等间隔个数为0
            { 
                cout << 0 << endl;
                continue;
            }
            if(px != py)//二者不在同一个集合
            {
                cout<< -1 <<endl;
                continue;
            }
            cout<<abs(d[x] - d[y]) - 1<<endl; //间隔元素个数 = 距离 - 1
        }
    }
    return 0;
}

239. 奇偶游戏

思路1(带权并查集+无序离散化)

带权并查集(边权d[]表示01关系)
image
image
image
设S[L,R]为区间[L,R]中1的个数，根据前缀和S[L,R] = S[1,R] - S[1,L-1]，
若S[L,R]为偶数，则S[R]与S[L-1]奇偶性相同(奇-奇=偶，偶-偶=偶)
若S[L,R]为奇数，则S[R]与S[L-1]奇偶性不同
设d[x]为x与p[x]的关系，0为奇偶性一致，1为奇偶性不一致

  • 若x与y奇偶性相同，且属于同一集合，则d[x]和d[y]表示二者与根结点的关系，(d[x] + d[y]) % 2则为x与y的关系，此时应该为0，否则产生矛盾。
  • 若x与y奇偶性相同，但属于不同集合，则需要按照要求进行合并,假设将x所在集合挂到y集合的下面，x与y的关系为(d[x] + d[px] + d[y]) % 2,此时应该为0，则d[px] = (d[x] + d[y]) % 2(非负等价)
  • 若x与y奇偶性不同，且属于同一集合，则d[x]和d[y]表示二者与根结点的关系，(d[x] + d[y]) % 2则为x与y的关系，此时应该为1，否则产生矛盾。
  • 若x与y奇偶性不同，但属于不同集合，则需要按照要求进行合并,假设将x所在集合挂到y集合的下面，x与y的关系为(d[x] + d[px] + d[y]) % 2,此时应该为1，则d[px] = (1 + d[x] + d[y]) % 2(非负等价)

无序离散化
本题序列长度很大，但问题数量不大，因此使用到的区间端点不多，可以用无序离散化

题解1

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <string>

using namespace std;

const int N = 10010;

int n,m;
int p[N],d[N];
unordered_map<int,int>S;

int get(int x) //无序离散化
{
    if(!S.count(x))
    {
        S[x] = ++n;
    }
    return S[x];
}

int find(int x) //带距离维护的找到集合根结点
{
    if(p[x]!=x)
    {
        int root = find(p[x]);
        d[x] += d[p[x]];
        p[x] = root;
    }
    return p[x];
}
int main()
{
    cin>>n>>m;
    n = 0;
    for(int i = 1;i<=N;i++)
    {
        p[i] = i;
    }
    int ans = m;
    for(int k = 1;k<=m;k++)
    {
        int l,r;
        string op;
        cin>>l>>r>>op;
        l = get(l-1),r = get(r);
        int pl = find(l),pr = find(r);
        if(op[0] == 'e') //同类
        {
            if(pl == pr) //同一集合
            {
                if((d[l] + d[r]) % 2 != 0) //但是关系距离为1，不同类，矛盾
                {
                    ans = k - 1;
                    break;
                }
            }
            else //不同集合，需要合并，且关系距离为0
            {
                p[pl] = pr;
                d[pl] = (d[l] + d[r]) % 2;
            }
        }
        else //不同类
        {
            if(pl == pr) //同一集合 
            {
                if((d[l] + d[r]) % 2 == 0)//但是关系距离为0，同类，矛盾
                {
                    ans = k - 1;
                    break;
                }
            }
            else //不同集合，需要合并，且关系距离为1
            {
                p[pl] = pr;
                d[pl] = (d[l] + d[r] + 1) % 2;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

思路2：扩展域写法

p[x]:x属于第0类的集合根结点，p[x + Base]:x属于第1类的集合的根结点

题解2

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <string>

using namespace std;

const int N = 20020,Base = N/2;

int n,m;
int p[N],d[N];
unordered_map<int,int>S;

int get(int x) //无序离散化
{
    if(!S.count(x))
    {
        S[x] = ++n;
    }
    return S[x];
}

int find(int x) 
{
    if(p[x]!=x) p[x] = find(p[x]);
    return p[x];
}
int main()
{
    cin>>n>>m;
    n = 0;
    for(int i = 1;i<=N;i++)
    {
        p[i] = i;
    }
    int ans = m;
    for(int k = 1;k<=m;k++)
    {
        int l,r;
        string op;
        cin>>l>>r>>op;
        l = get(l-1),r = get(r);
        int pl = find(l),pr = find(r);
        //p[x]:x属于第0类的集合根结点，p[x + Base]:x属于第1类的集合的根结点
        if(op[0] == 'e') //同类
        {
            if(find(l + Base) == find(r) || find(l) == find(r + Base)) //不同类属于一个集合，矛盾
            {
                ans = k - 1;
                break;
            }
            //同类合并
            p[find(l)] = find(r);
            p[find(l + Base)] = find(r + Base);
        }
        else //不同类
        {
            if(find(l) == find(r) || find(l + Base) == find(r + Base))//同类属于一个集合，矛盾
            {
                ans = k - 1;
                break;
            }
            
            //不同类合并
            p[find(l + Base)] = find(r);
            p[find(l)] = find(r + Base);
        }
    }
    cout<<ans<<endl;
    return 0;
}

标签：结点,数据结构,return,int,查集,集合,include,find,第四章
From： https://www.cnblogs.com/zjq182/p/16610476.html

相关文章

  • 【Perl】常见数据结构与算法
    #二分查找usestrict;subbinary_search{my($target,@v)=@_;my$left=0;my$right=@v-1;while($left<$right){my$mid=......
  • 04第四章：Docker镜像
    一、Docker镜像是什么1、镜像是什么？镜像：是一种轻量级、可执行的独立软件包，它包含运行某个软件所需的所有内容，我们把应用程序和配置依赖打包好形成一个可交付的运行环境(......
  • Redis主要数据结构以及应用场景
    String最常用的各式，以kv格式进行存储常用的场景在于对象json存储，以及对象缓存、分布式锁、计数器等。SETKEYVALUE存入字符串的键值对MSETkeyvalue[keyvalue......
  • 模拟赛 d （扫描线，三维偏序，线段树合并，并查集，线段树上二分）
    PRO题目大意：给定$N$个矩形，求连通块个数。($1\leqN,x_1,x_2,y-1,y_2\leq100000$)SOL乍一看就能知道是扫描线，不过这题的细节恐怖的要命。（std同样看不懂，自己魔改了一......
  • 数据结构
    数据一般分为线性结构(连续摆放的，节约空间)Array（数组）定长,连续分配内存空间，元素数据类型一致，可以使用下标访问,读取速度快,但是增删较慢ArrayList：不定长，连续分配内存,......
  • 考研数据结构与算法（七）图论
    @目录一、图的基本概念1.1图的定义1.2基本术语1.2.1有向图1.2.2无向图1.2.3简单图1.2.4多重图1.2.5完全图1.2.6子图1.2.7连通、连通分量、连通图1.2.8强连通1.2.......
  • 数据结构和算法的介绍
    声明：此系列以尚硅谷数据结构与算法（Java数据结构与算法）视频为主，包括其他大佬的文章（相关文中有引用注明来源）在此声明一次，后续文档中不再声明。目录数据结构和算法的关系算......
  • 模板——数据结构
    线段树维护区间最值以及满足最值的个数structSGT{ intmx[N<<2],tg[N<<2],su[N<<2]; #definemid((l+r)>>1) #definelc(u<<1) #definerc((u<<1)|1) voidbld(......
  • 21级数据结构与算法实验2——链表
    21级数据结构与算法实验2——链表28天7-1单链表的创建及遍历分数30作者陈晓梅单位广东外语外贸大学读入n值及n个整数，建立单链表并遍历输出。输入格式:读入n及......
  • 数据结构
    定义：数据结构是计算机存储、组织数据的方式。 数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。、 数据结构......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99