• 并查集及其应用

    并查集的基本操作:

    1.合并两个集合

    2.查询两个元素的祖宗节点

    扩展:

    1.记录每个集合的大小 将集合大小绑定到代表元素节点上 就是并查集的思想 (不是每个元素都是正确的 但是代表元素是正确的)

    2.记录每个点到根节点的距离 绑定到每个元素身上 因为每个元素到根节点的距离都是不一样的

    边带权的并查集

    边带权并查集，顾名思义，就是各个结点之间带有权值的并查集，在查询和合并时可以维护结点之间的权值。边带权并查集可以用于统计每个节点到树根之间路径上的一些信息。

    扩展域并查集

    扩展域用以维护较抽象的对象之间的逻辑关系，由于有点抽象，所以理解起来有点费劲。

    扩展域将数据之间的关系分类，将对象之间不同的关系种类分开讨论，并在这些数据之间建立联系。

    假定现在要维护要k类集合 如果k不大两个都行  k大就选边带权

     

    1.格子游戏

    信息学奥赛一本通（C++版）在线评测系统

    题意问第一次连成圈是什么时候

    分析一下形成环的条件就是在连边的时候 边的两个端点已经在一个集合里面了 直接并查集

    细节：把两位坐标转换为一维 (x,y)-->x*n+y x y从0开始

    1. #include 
    2. using namespace std;
    3. const int N=40010;
    4. int n,m;
    5. int p[N];
    6. int find(int x)
    7. {
    8.     if(p[x]!=x) p[x]=find(p[x]);
    9.     return p[x];
    10. }
    11. int get(int x,int y)
    12. {
    13.     return x*n+y;
    14. }
    15. int main()
    16. {
    17.     cin>>n>>m;
    18.     for(int i=0;i
    19.         p[i]=i;
    20.     int res=0;
    21.     for(int i=1;i<=m;i++)
    22.     {
    23.         int x,y;
    24.         char d;
    25.         cin>>x>>y>>d;
    26.         x--,y--;
    27.         int a=get(x,y);
    28.         int b;
    29.         if(d=='D')
    30.         {
    31.             b=get(x+1,y);
    32.         }
    33.         else b=get(x,y+1);
    34.         int pa=find(a),pb=find(b);
    35.         if(pa==pb)
    36.         {
    37.             res=i;
    38.             break;
    39.         }
    40.         p[pa]=pb;
    41.     }
    42.     if(!res) puts("draw");
    43.     else cout<
    44.     return 0;
    45. }

    2.搭配购买

    信息学奥赛一本通（C++版）在线评测系统

    分析过后就可以知道我们每次只能去买一组云 然后会得到一个体积和价值 那么这不就是01背包吗

    让后用并查集维护好每一组就ok了

    看起来像有依赖的背包问题 但是不是 因为这里要买一个物品就要把全部物品都买了 而有依赖的背包问题是要买后者就要买前者这种条件

    1. #include 
    2. using namespace std;
    3. const int N=10010;
    4. int n,m,vol;
    5. int v[N],w[N];
    6. int p[N];
    7. int f[N];
    8. int find(int x)
    9. {
    10.     if(p[x]!=x) p[x]=find(p[x]);
    11.     return p[x];
    12. }
    13. int main()
    14. {
    15.     cin>>n>>m>>vol;
    16.     for(int i=1;i<=n;i++)
    17.         p[i]=i;
    18.     for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    19.     while(m--)
    20.     {
    21.         int a,b;
    22.         cin>>a>>b;
    23.         int pa=find(a),pb=find(b);
    24.         if(pa!=pb)
    25.         {
    26.             v[pb]+=v[pa];
    27.             w[pb]+=w[pa];
    28.             p[pa]=pb;
    29.         }
    30.     }
    31.     for(int i=1;i<=n;i++)
    32.         if(p[i]==i)
    33.         {
    34.             for(int j=vol;j>=v[i];j--)
    35.                 f[j]=max(f[j],f[j-v[i]]+w[i]);
    36.         }
    37.     cout<
    38.     return 0;
    39. }

    3.程序自动分析

    237. 程序自动分析 - AcWing题库

    由于数据范围很大 但是操作数很小 所以要离散化

    1.约束条件的顺序是无所谓的 所以可以先考虑所有的相等元素 这里是不会有矛盾的

    2.再去考虑所有不等的元素 如果不等的元素已经在一个集合了 那肯定是矛盾的

    并查集维护就行了

    1. #include 
    2. using namespace std;
    3. const int N=2000010;
    4. int n,m;
    5. int p[N];
    6. unordered_map<int,int> mp;
    7. struct node
    8. {
    9.     int x,y;
    10.     int e;
    11. }query[N];
    12. int find(int x)
    13. {
    14.     if(p[x]!=x) p[x]=find(p[x]);
    15.     return p[x];
    16. }
    17. int get(int x)
    18. {
    19.     if(mp.count(x)==0) mp[x]=++n;
    20.     return mp[x];
    21. }
    22. int main()
    23. {
    24.     int t;
    25.     cin>>t;
    26.     while(t--)
    27.     {
    28.         n=0;
    29.         mp.clear();
    30.         cin>>m;
    31.         for(int i=0;i
    32.         {
    33.             int x,y,e;
    34.             cin>>x>>y>>e;
    35.             query[i]={get(x),get(y),e};
    36.         }
    37.         for(int i=1;i<=n;i++) p[i]=i;
    38.         for(int i=0;i
    39.         {
    40.             if(query[i].e==1)
    41.             {
    42.                 int pa=find(query[i].x),pb=find(query[i].y);
    43.                 p[pa]=pb;
    44.             }
    45.         }
    46.         bool has_conflict=false;
    47.         for(int i=0;i
    48.             if(query[i].e==0)
    49.             {
    50.                 int pa=find(query[i].x),pb=find(query[i].y);
    51.                 if(pa==pb)
    52.                 {
    53.                     has_conflict=true;
    54.                     break;
    55.                 }
    56.             }
    57.         if(has_conflict) puts("NO");
    58.         else puts("YES");
    59.     }
    60.     return 0;
    61. }

    4.奇偶游戏

    239. 奇偶游戏 - AcWing题库

    用前缀和的思想去思考 s[ l ~ r ]中有奇数个1代表 s[ r ] - s[ l - 1 ] 中有奇数个1 代表s[r]和s[l-1]奇偶性不同    偶数个1的话就是s[r]和s[l-1]奇偶性相同

    但是奇偶性无矛盾一定可以推出来该问题无矛盾？

    令a[i]=| s[i]-s[i-1] | 一定可以构造出来一个无矛盾的方案 所以是等价的

    带边权并查集

     代码

    1. #include
    2. using namespace std;
    3. const int N=1e4+10;
    4. int p[N],d[N];//s表示集合的长度，d表示每个点到根节点的距离
    5. int n,m;
    6. unordered_map<int,int> ha;
    7. int get(int x)
    8. {
    9.     if(!ha.count(x)) ha[x]=++n;
    10.     return ha[x];
    11. }
    12. int find(int x)
    13. {
    14.     if(p[x]!=x) 
    15.     {
    16.         int root=find(p[x]);
    17.         d[x]^=d[p[x]];//更新路径长其他的值
    18.         p[x]=root;
    19.     }
    20.     return p[x];
    21. }
    22. int main()
    23. {
    24.     cin>>n>>m;
    25.     n=0;
    26.     int res=m;
    27.     for(int i=0;i//初始化
    28.     for(int i=1;i<=m;i++)
    29.     {
    30.         int a,b;
    31.         string type;
    32.         cin>>a>>b>>type;
    33.         a=get(a-1),b=get(b);//获取离散化后的值
    34.         int t=0;
    35.         if(type=="odd") t=1;//假如是奇数
    36.         int pa=find(a),pb=find(b);
    37.         if(pa==pb)//假如在一个集合
    38.         {
    39.           if((d[a]^d[b])!=t)//假如跟t不同类
    40.           {
    41.              res=i-1;
    42.              break;
    43.           }
    44.         }
    45.         else//反之不在一个集合就合并
    46.         {
    47.             p[pa]=pb;
    48.             d[pa]=d[a]^d[b]^t;//合并到同一类中
    49.         }
    50.     }
    51.     cout<
    52.     return 0;
    53. }

    扩展域并查集

     

    1. #include
    2. using namespace std;
    3. const int N=2e4+10,M=N/2;//M是分界线在0-M是偶数，大于M是奇数
    4. int p[N],d[N];//s表示集合的长度，d表示每个点到根节点的距离
    5. int n,m;
    6. unordered_map<int,int> ha;
    7. int get(int x)
    8. {
    9.     if(!ha.count(x)) ha[x]=++n;
    10.     return ha[x];
    11. }
    12. int find(int x)
    13. {
    14.     if(p[x]!=x) p[x]=find(p[x]);
    15.     return p[x];
    16. }
    17. int main()
    18. {
    19.     cin>>n>>m;
    20.     n=0;
    21.     int res=m;
    22.     for(int i=0;i//初始化
    23.     for(int i=1;i<=m;i++)
    24.     {
    25.         int a,b;
    26.         string type;
    27.         cin>>a>>b>>type;
    28.         a=get(a-1),b=get(b);//获取离散化后的值
    29.         int a1=find(a),a2=find(a+M),b1=find(b),b2=find(b+M);//获取a跟b的偶数和奇数情况
    30.         if(type=="odd")//假如是奇数类型
    31.         {
    32.             if(a1==b1||a2==b2)//但是a跟b同类了
    33.             {
    34.                 res=i-1;
    35.                 break;
    36.             }
    37.             p[a1]=b2;//反之把a的偶数合并到b的奇数
    38.             p[a2]=b1;//反之把a的奇数合并到b的偶数
    39.         }
    40.         else//假如是偶数
    41.         {
    42.             if(a1==b2||a2==b1)//假如不同类
    43.             {
    44.                 res=i-1;
    45.                 break;
    46.             }
    47.             p[a1]=b1;//把偶数合并到偶数里
    48.             p[a2]=b2;//把奇数合并到奇数里
    49.         }
    50.     }
    51.     cout<
    52.     return 0;
    53. }

    5.银河英雄传说

    238. 银河英雄传说 - AcWing题库

    题目的两个操作：1.合并集合 2.两点间距离 用并查集维护到根节点的距离就行了

    1.让排头当根节点

    2.d[pa]=size[pb]

    3.size[pb]+=size[pa]

     

     

    看到这里会不会有疑惑 就是说明明我是find完pa pb以后再将d[pa]=size[pb] size[pb]+=size[pa]的那为什么可以能维护每个点道根节点的距离的 也就是这段代码

    1.         if(op[0]=='M')
    2.         {
    3.             int pa=find(a),pb=find(b);
    4.             if(pa!=pb)
    5.             {
    6.                 d[pa]=s[pb];
    7.                 s[pb]+=s[pa];
    8.                 p[pa]=pb;
    9.             }
    10.         }

     其实呢更新每个点到根节点的距离是在查询的时候更新的

    1.         else
    2.         {
    3.             int pa=find(a),pb=find(b);//这里更新的捏
    4.             if(pa!=pb) puts("-1");
    5.             else printf("%d\n",max(0,abs(d[a]-d[b])-1));
    6.         }

    完整代码 

    1. #include 
    2. using namespace std;
    3. const int N=30010;
    4. int n,m;
    5. int p[N],s[N],d[N];
    6. int find(int x)
    7. {
    8.     if(p[x]!=x)
    9.     {
    10.         int root=find(p[x]);
    11.         d[x]+=d[p[x]];
    12.         p[x]=root;
    13.     }
    14.     return p[x];
    15. }
    16. int main()
    17. {
    18.     cin>>m;
    19.     for(int i=1;i<=N;i++)
    20.     {
    21.         p[i]=i;
    22.         s[i]=1;
    23.     }
    24.     while(m--)
    25.     {
    26.         char op[2];
    27.         int a,b;
    28.         cin>>op>>a>>b;
    29.         if(op[0]=='M')
    30.         {
    31.             int pa=find(a),pb=find(b);
    32.             if(pa!=pb)
    33.             {
    34.                 d[pa]=s[pb];
    35.                 s[pb]+=s[pa];
    36.                 p[pa]=pb;
    37.             }
    38.         }
    39.         else
    40.         {
    41.             int pa=find(a),pb=find(b);
    42.             if(pa!=pb) puts("-1");
    43.             else printf("%d\n",max(0,abs(d[a]-d[b])-1));
    44.         }
    45.     }
    46.     return 0;
    47. }

  • 相关阅读:
    IMU用于飞行坐姿校正
    DX 的 HLSL 和 GL 的 GLSL的 矩阵构建的行列区别
    五、程序员指南：数据平面开发套件
    上行取消指示 DCI format 2_4
    css-表头筛选的特定样式
    基于SpringBoot+Redis的前后端分离外卖项目-苍穹外卖(一)
    基于Java+vue前后端分离旅游景点管理系统设计实现(源码+lw+部署文档+讲解等)
    区块链私链搭建出现错误
    数字人惯性动作捕捉技术服务，激发吉祥物IP创新活力
    前端vue实现页面加水印文字 单个页面所有页面加水印（更新版）
  • 原文地址：https://blog.csdn.net/lee_14141/article/details/127424649