并查集和带权并查集-白红宇

并查集和带权并查集

阅读量：5120 次

发布时间：2019-06-13

本文共 7646 字，大约阅读时间需要 25 分钟。

　　这两天做了几道并查集的题目，hdu的联通工程啊more is better 啊，然后卡在hdu1829，带权的并查集，没搞懂，尝试写下来让思路清晰些。

并查集是一种维护不同集合，在此基础上实现快速判断，统计个数等等的算法。

基础的有find和join两个功能，其中join作用于接收新数据。

并查集应用场景的几个特点：

1.数据之间存在联系；

2.借由两个数据的联系，数据会被双向联通的结合成几个集合；

下面介绍下find和join的基本形式

const int maxn=1000;int p[maxn];//用于储存数据的根void init(int n){    for(int i=0;i

这种是将关系优化避免出现树变成一条路

还有一种如下

int find(int x){    if(p[x]==x)return x;    int tem=find(p[x]);    return tem;}

这种用递归的方法算

join函数：

void join(int x,int y){    int f1=find(x),f2=find(y);    if(f1!=f2)　　{   　　 p[f1]=f2; 　　}}

知道了这些，一些水题就可以做了

接着是在这个基础上的变化，如统计集合个数，一开始的想法是维护完数据后for一遍，实际这里可以发现，在p[]数组中，作为根节点的数据p[i]==i的，没有必要通过链表结构特点去找根节点。接着处理掉这个for循环：

再看看现在的思路，是通过遍历一遍p[]数组，统计满足p[i]==i的个数，假设为a。如果所有数据没有联通，那么集合个数为n，a=n-（原本p[i]==i的点的p[i]改变的次数），即在join函数中每次寻找到两个数据的根数据进行合并时加一个计数器，然后用n减去。可以这样实现：

int ans=n;void join(int x,int y){    int f1=find(x),f2=find(y);    if(f1!=f2)　　{   　　 p[f1]=f2;          ans--;　　}}

接着是找集合中元素个数的题1856，这个可以通过增加一个初始化为1的数组，每次合并同时对应合并，同时max取最大值

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               const int maxn = 10000005;#pragma warning(disable:4996)using namespace std;// freopen("john.in", "r", stdin);// freopen("john.out", "w", stdout);int p[maxn];int n[maxn];void pre(){ for (int i = 1;i < maxn;i++) { p[i] = i; n[i] = 1; }}int find(int x){ int r = x; while (r != p[r]) { r = p[r]; } int i = x; while (i != p[i]) { int j = p[i]; p[i] = r; i = j; } return r;}void join(int x, int y,int& ans){ int tem1 = find(x), tem2 = find(y); if (tem1 != tem2) { p[tem1] = tem2; n[tem2] += n[tem1]; ans = max(n[y], ans); }}int main(){ int t; while (~scanf("%d", &t)) { if (t == 0)puts("1"); else { int ans = 0; pre(); while (t--) { int i, j; scanf("%d%d", &i, &j); join(i, j, ans); } printf("%d\n", ans); } }}

还有一个应用是判断是否成环，如果join的两个数据p[]相同，则标记为成环，如1272这题，还要判断唯一性，可以用前面的方法，也可以通过图论中边数为定点数减一来判断

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               const int maxn = 100005;#pragma warning(disable:4996)using namespace std;// freopen("john.in", "r", stdin);// freopen("john.out", "w", stdout);int p[maxn];int flag;bool s[maxn];int find(int a){ while (a != p[a]) { a = p[a]; } return a;}void join(int a, int b){ int i = find(a), j = find(b); if (i != j) { p[i] = p[j]; } else flag = 0;}void pre(){ for (int i = 1;i < maxn;i++) { p[i] = i; s[i] = false; }}int main(){ int a, b; while (cin >> a >> b) { if (a == -1 && b == -1)break; if (a == 0 && b == 0)printf("Yes\n"); else { flag = 1; pre(); s[a] = true; s[b] = true; join(a, b); while (scanf("%d%d", &a, &b), (a || b)) { s[a] = true; s[b] = true; join(a, b); } if (flag) { int cnt = 0; for (int i = 1;i < maxn;i++) { if (s[i] && p[i] == i) { cnt++; } if (cnt > 1) { flag = 0; break; } } } if (flag)printf("Yes\n"); else printf("No\n"); } }}

然后是1198这题，这题没有显示的给出数据间的关系，需要对数据进行处理，但并查集的部分没有什么新东西

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               const int maxn = 550;#pragma warning(disable:4996)using namespace std;// freopen("john.in", "r", stdin);// freopen("john.out", "w", stdout);//上下左右分别为0123int list[11] = { 10,9,6,5,12,3,11,14,7,13,15 };char a[maxn][maxn];int ans;int n, m;int p[maxn*maxn+1];void pre(int n){ for (int i = 0;i < n;i++) { p[i] = i; }}int find(int x){ int r = x; while (r != p[r]) { r = p[r]; } return r;}void judge(int ai, int aj, int bi, int bj){ if (bi >= m || bj >= n)return; bool flag = false; int t1 = a[ai][aj] - 'A'; int t2 = a[bi][bj] - 'A'; if (ai == bi&&aj < bj) { if (((list[t1] ) & 1) && ((list[t2]>>1) & 1))flag = true; } else if (aj == bj&&ai < bi) { if(((list[t1] >> 2) & 1) && ((list[t2]>>3) & 1))flag = true; } if (flag) { int f1 = find(ai*n + aj), f2 = find(bi*n + bj); if (f1 != f2) { p[f1] = f2; ans--; } }}int main(){ //freopen("in.txt", "r", stdin); while (scanf("%d%d", &m, &n)!= EOF) { if (m == -1 || n == -1)break; pre(m*n); ans = n*m; for (int i = 0;i < m;i++) { scanf("%s", a[i]); } for (int i = 0;i < m;i++) { for (int j = 0;j < n;j++) { judge(i, j, i, j + 1); judge(i, j, i + 1, j); } } printf("%d\n", ans); }}

然后是现在做的这题，关于带权并查集，还没有弄明白，1829，题意大概是选择动物，给出两个数据的性别相反，问是否出现前后矛盾的情况，上网看到一种解法，思路是开两个数组，每次接收数据，交换p[]中两个数据对应的值，如果有处理到两个数据的p[]相同，则错误。还有一种是带权并查集。做了一个晚上带权那种，还是有点没搞明白。

带权并查集多一个权值的数组，通过递归的find函数找到根节点。现在的问题是，每次找到根节点的过程和合并的过程，会让原本a->b->c的关系变成a->c,b->c每次更新后都要再次调整权值数组。网上的解释是把权值看成向量。例如sign[i]表示由i指向前一个节点的向量，那么改变后的指向由a->c，等于sign[a]+sign[p[a]]。

下面是代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               #pragma warning(disable:4996)using namespace std;// freopen("john.in", "r", stdin);// freopen("john.out", "w", stdout);const int maxn = 2002;int p[maxn];int sign[maxn];int find(int x){ if (p[x] == x) { return x; } int tem = p[x]; p[x] = find(p[x]); sign[x] = (sign[x] + sign[tem]) % 2;//用向量的思想来解释这个过程 return p[x];}void unit(int n){ for (int i = 1;i <= n;i++) { p[i] = i; sign[i] = 0; }}void join(int x, int y){ int f1 = find(x); int f2 = find(y); if (f1 != f2) { p[f1] = f2; sign[f1] = (1 + sign[y] - sign[x]) % 2; } find(x);}int main(){ freopen("in.txt", "r", stdin); int t; scanf("%d", &t); int cnt = 1; while (t--) { int n, m; scanf("%d%d", &n, &m); unit(n); bool flag = true; while (m--) { int i, j; scanf("%d%d", &i, &j); if(flag)join(i, j); if (sign[i] == sign[j]) { flag = false; } } printf("Scenario #%d:\n", cnt++); if (flag)printf("No suspicious bugs found!\n"); else printf("Suspicious bugs found!\n"); printf("\n"); }}

现在还有个地方没有很清楚，就是在join函数中的sign[f1]的更新，为什么可以直接由sign[x]和sign[y]关系推到？

想通了！在find的过程中已经让x链接到根节点了

2017/4/26

今天学习了poj那道经典的食物链，有三个状态，看了结题报告，有两个细微不同的思路，一个是在状态数组sign里存0，1，2代表被吃，同类，吃的关系，另一种是在sign中存三种动物的种类，区别在更新sign数组的表达式上似乎有所不同。

通过这道题，一方面加深了关于向量关系的理解，另一方面是感觉数设的卡诺图化简作为二进制码逻辑关系的化简，这种思路在这种题里意外的有用【捂脸】

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               #pragma warning(disable:4996)using namespace std;// freopen("john.in", "r", stdin);// freopen("john.out", "w", stdout);const int maxn = 50002;int p[maxn];int sign[maxn];void init(int n){ for (int i = 1;i <= n;i++) { p[i] = i; sign[i] = 0; }}int find(int x){ if (x == p[x])return x; int tem = p[x]; p[x] = find(p[x]); sign[x] = (sign[x] + sign[tem]) % 3; return p[x];}bool join(int x, int y, int d){ int f1 = find(x), f2 = find(y); if (f1 == f2) { if (d == 1 && sign[x] != sign[y])return false; if (d == 2) { if (sign[x] == 2 && sign[y] != 1)return false; if (sign[x] == 0 && sign[y] != 2)return false; if (sign[x] == 1 && sign[y] != 0)return false; } return true; } p[f1] = f2; if (d == 1) { sign[f1] = (sign[y] - sign[x] + 3) % 3; } if (d == 2) { sign[f1]=(sign[y] - sign[x] + 1 + 3) % 3; } find(x);//看看是否必要,可以ac，还是保留吧 return true;}int main(){// freopen("in.txt", "r", stdin); int n, k; scanf("%d%d", &n, &k); init(n); int ans = 0; while (k--) { int d, x, y; scanf("%d%d%d", &d, &x, &y); if (x > n || y > n) { ans++; continue; } if (x == y&&d==2) { ans++; continue; } if (!join(x, y, d))ans++;//小心添加错的关系而对正确的关系造成破坏 //判断还是在函数中好，因为在这里会重复做过的事，找到find（x），（y）然后讨论sign[x]sign[y]的关系 } printf("%d\n", ans);}

转载于:https://www.cnblogs.com/roffen/p/6763328.html

你可能感兴趣的文章