[关闭]
@LinKArftc 2015-08-14T11:51:06.000000Z 字数 6847 阅读 1133

并查集

数据结构 并查集

总结

做了一天的并查集，发现并查集其实并没有自己想象的那么简单，子节点与父节点的关系 rela[i] 递推还有需要记录的状态信息还是挺麻烦的，不过做了一天之后，发现还是挺水的，基本都差不多，就看自己能不能找到需要记录的状态信息和关系递推了。

例题

poj 1182

经典的食物链
这题有个大坑，就是不能多组数据读入，调了一上午，最终看discuss才发现这个坑，快哭了都ToT
需要记录子节点与父节点的关系 rela[i], 0表示同类，1 吃，2 被吃，然后就是递推了

  1. /*
  2. ID: LinKArftc
  3. PROG: 1182.cpp
  4. LANG: C++
  5. */
  7. #include <cstdio>
  8. #include <iostream>
  9. #include <cstring>
  10. #include <algorithm>
  11. using namespace std;
  13. const int maxn = 50010;
  14. int n, k;
  15. int rela[maxn];//0 same, 2 eat, 3 eaten;
  16. int father[maxn];
  18. void init() {
  19.     for (int i = 1; i <= n; i ++) {
  20.         father[i] = i;
  21.         rela[i] = 0;
  22.     }
  23. }
  25. int find(int a) {
  26.     if (father[a] == a) return a;
  27.     int fa = father[a];
  28.     father[a] = find(father[a]);
  29.     rela[a] = (rela[a] + rela[fa] + 3) % 3;
  30.     return father[a];
  31. }
  33. void unin(int op, int a, int b) {
  34.     int x = find(a);
  35.     int y = find(b);
  36.     father[y] = x;
  37.     rela[y] = (3 + rela[a] - rela[b] - op) % 3;
  38. }
  40. int main() {
  41.     scanf("%d %d", &n, &k);
  42.     int ans = 0;
  43.     int op, a, b;
  44.     init();
  45.     for (int i = 1; i <= k; i ++) {
  46.         scanf("%d %d %d", &op, &a, &b);
  47.         if (a > n || b > n) ans ++;
  48.         else if (a == b && op == 2) ans ++;
  49.         else {
  50.             int x = find(a);
  51.             int y = find(b);
  52.             if (x == y) { // relation sure
  53.                 if (op == 1 && rela[a] != rela[b]) ans ++;
  54.                 if (op == 2 && (rela[a] - rela[b] + 3) % 3 != 1) ans ++;
  55.             } else unin(op - 1, a, b);
  56.         }
  57.     }
  58.     printf("%d\n", ans);
  60.     return 0;
  61. }

poj 1703 帮派

跟上一题差不多

  1. /*
  2. ID: LinKArftc
  3. PROG: 1703.cpp
  4. LANG: C++
  5. */
  7. #include <cstdio>
  8. #include <iostream>
  9. #include <cstring>
  10. #include <algorithm>
  11. using namespace std;
  13. const int maxn = 100010;
  14. int father[maxn];
  15. int rela[maxn];//1 same, 0 dif;
  17. int n, m;
  19. void init() {
  20.     for (int i = 1; i <= n; i ++) {
  21.         father[i] = i;
  22.         rela[i] = 1;
  23.     }
  24. }
  26. int find(int a) {
  27.     int x = father[a];
  28.     if (x != a) {
  29.         father[a] = find(x);
  30.         if (rela[a] == rela[x]) rela[a] = 1;
  31.         else rela[a] = 0;
  32.     }
  33.     return father[a];
  34. }
  36. void unin(int a, int b) {
  37.     int x = find(a);
  38.     int y = find(b);
  39.     if (x != y) {
  40.         father[x] = y;
  41.         if (rela[a] == rela[b]) rela[x] = 0;
  42.         else rela[x] = 1;
  43.     }
  44. }
  46. int main() {
  47. //    freopen("input.txt", "r", stdin);
  49.     int T;
  50.     int a, b;
  51.     char op;
  52.     scanf("%d", &T);
  53.     while (T --) {
  54.         scanf("%d %d", &n, &m);
  55.         init();
  56.         for (int i = 1; i <= m; i ++) {
  57.             scanf(" %c %d %d", &op, &a, &b);
  58.             if (op == 'A') {
  59.                 int x = find(a);
  60.                 int y = find(b);
  61.                 if (x != y) {
  62.                     printf("Not sure yet.\n");
  63.                     continue;
  64.                 }
  65.                 if (rela[a] == rela[b]) {
  66.                     printf("In the same gang.\n");
  67.                     continue;
  68.                 } else {
  69.                     printf("In different gangs.\n");
  70.                     continue;
  71.                 }
  72.             } else {
  73.                 unin(a, b);
  74.             }
  75.         }
  76.     }
  78.     return 0;
  79. }

poj 1988 堆叠问题

题意：
当前节点所在集合放到目标节点所在集合上，询问当前节点下面有多少节点

思路：
cnt[i] 记录该集合是第几个加入该集合的
sum[i] 该集合中元素个数
注意 cnt[i] 初始化为 0， 方便后面路径压缩时关系递推

  1. /*
  2. ID: LinKArftc
  3. PROG: 1988.cpp
  4. LANG: C++
  5. */
  7. #include <cstdio>
  8. #include <iostream>
  9. #include <cstring>
  10. #include <algorithm>
  11. using namespace std;
  13. const int maxn = 30010;
  15. int father[maxn];
  16. int cnt[maxn];  // 第几个加入该集合
  17. int sum[maxn];  // 该集合中元素个数
  19. void init() {
  20.     for (int i = 0; i < maxn; i ++) {
  21.         father[i] = i;
  22.         sum[i] = 1;
  23.         cnt[i] = 0; //从 0 开始方便 line41 计算
  24.     }
  25. }
  27. int find(int a) {
  28.     if (a != father[a]) {
  29.         int fa = father[a];
  30.         father[a] = find(fa);
  31.         cnt[a] += cnt[fa];
  32.     }
  33.     return father[a];
  34. }
  36. void unin(int a, int b) {
  37.     int x = find(a);
  38.     int y = find(b);
  39.     if (x != y) {
  40.         father[y] = x;
  41.         cnt[y] += sum[x];
  42.         sum[x] += sum[y];
  43.     }
  44. }
  46. int main() {
  47. //    freopen("input.txt", "r", stdin);
  49.     init();
  50.     int n, p;
  51.     char op;
  52.     int a, b;
  53.     scanf("%d", &p);
  54.     while (p --) {
  55.         scanf(" %c", &op);
  56.         if (op == 'M') {
  57.             scanf("%d %d", &a, &b);
  58.             unin(a, b);
  59.         } else {
  60.             scanf("%d", &a);
  61.             int x = find(a);
  62.             printf("%d\n", sum[x] - cnt[a] - 1);
  63.         }
  64.     }
  66.     return 0;
  67. }

poj 1308 判断一个图是不是树

这题有个大坑，0 0 也就是空树也是树。。哔了狗了。。。

  1. /*
  2. ID: LinKArftc
  3. PROG: 1308.cpp
  4. LANG: C++
  5. */
  7. #include <cstdio>
  8. #include <iostream>
  9. #include <cstring>
  10. #include <algorithm>
  11. using namespace std;
  13. const int maxn = 1010;
  15. int father[maxn];
  16. int vis[maxn];
  18. void init() {
  19.     for (int i = 1; i < maxn; i ++) father[i] = i;
  20.     memset(vis, 0, sizeof(vis));
  21. }
  23. int find(int a) {
  24.     if (a != father[a]) father[a] = find(father[a]);
  25.     return father[a];
  26. }
  28. void unin(int a, int b) {
  29.     int x = find(a);
  30.     int y = find(b);
  31.     if (x != y) father[y] = x;
  32. }
  34. int main() {
  35. //    freopen("input.txt", "r", stdin);
  36.     int caseNo = 1;
  37.     int a, b;
  38.     init();
  39.     bool flag = false;
  40.     while (~scanf("%d %d", &a, &b)) {
  41.         if (a == -1 && b == -1) break;
  42.         if (a == 0 && b == 0) {
  43.             if (flag == false) {
  44.                 int cnt = 0;
  45.                 for (int i = 1; i < maxn; i ++) {
  46.                     if (vis[i] && (i == father[i])) cnt ++;
  47.                 }
  48.                 if (cnt <= 1) printf("Case %d is a tree.\n", caseNo ++);
  49.                 else printf("Case %d is not a tree.\n", caseNo ++);
  50.             }
  51.             init();
  52.             flag = false;
  53.             continue;
  54.         }
  55.         if (flag) continue;
  56.         vis[a] = 1;
  57.         vis[b] = 1;
  58.         int x = find(a);
  59.         int y = find(b);
  60.         if (a == b || (a != b && x == y)) {
  61.             printf("Case %d is not a tree.\n", caseNo ++);
  62.             flag = true;
  63.         } else {
  64.             unin(a, b);
  65.         }
  66.     }
  68.     return 0;
  69. }

poj 2524 宗教信仰

并查集的最简单模型了

  1. /*
  2. ID: LinKArftc
  3. PROG: 2524.cpp
  4. LANG: C++
  5. */
  7. #include <cstdio>
  8. #include <iostream>
  9. #include <cstring>
  10. #include <algorithm>
  11. using namespace std;
  13. int father[50005];
  14. int find(int x) {
  15.     if (x != father[x]) father[x] = find(father[x]);
  16.     return father[x];
  17. }
  19. int main() {
  20.     int n, m;
  21.     int i, j;
  22.     int num;
  23.     int a, b;
  24.     j = 1;
  25.     while (cin >> n >> m && (n || m)) {
  26.         num = n;
  27.         for (i = 0; i < n; i ++) father[i] = i;
  28.         for (i = 0; i < m; i++) {
  29.             cin >> a >> b;
  30.             int x = find(a);
  31.             int y = find(b);
  32.             if (x != y) {
  33.                 father[y] = x;
  34.                 num --;
  35.             }
  36.         }
  37.         printf("Case %d: %d\n", j, num);
  38.         j ++;
  39.     }
  40.     return 0;
  41. }

poj 2492 臭虫中的同性恋

相对于食物链的三性 两性问题比较简单

  1. /*
  2. ID: LinKArftc
  3. PROG: 2492.cpp
  4. LANG: C++
  5. */
  7. #include <cstdio>
  8. #include <iostream>
  9. #include <cstring>
  10. #include <algorithm>
  11. using namespace std;
  13. const int maxn = 2010;
  14. int n, q;
  15. int father[maxn];
  16. int rela [maxn]; // 0 same, 1 dif
  18. void init() {
  19.     for (int i = 1; i <= n; i ++) father[i] = i;
  20.     memset(rela, 0, sizeof(rela));
  21. }
  23. int find(int a) {
  24.     if (a != father[a]) {
  25.         int fa = father[a];
  26.         father[a] = find(father[a]);
  27.         rela[a] = (rela[a] + rela[fa]) % 2;
  28.     }
  29.     return father[a];
  30. }
  32. void unin(int a, int b) {
  33.     int x = find(a);
  34.     int y = find(b);
  35.     if (x != y) {
  36.         father[x] = y;
  37.         rela[x] = (rela[a] + rela[b] + 1) % 2;
  38.     }
  39. }
  41. int main() {
  42. //    freopen("input.txt", "r", stdin);
  44.     int T, caseNo = 1;
  45.     int a, b;
  46.     scanf("%d", &T);
  47.     while (T --) {
  48.         printf("Scenario #%d:\n", caseNo ++);
  49.         scanf("%d %d", &n, &q);
  50.         init();
  51.         bool flag = false;
  52.         for (int i = 1; i <= q; i ++) {
  53.             scanf("%d %d", &a, &b);
  54.             if (flag) continue;
  55.             int x = find(a);
  56.             int y = find(b);
  57.             if (x == y) {
  58.                 if (rela[a] == rela[b]) {
  59.                     flag = true;
  60.                     printf("Suspicious bugs found!\n\n");
  61.                     continue;
  62.                 }
  63.             }
  64.             else unin(a, b);
  65.         }
  66.         if (flag == false) printf("No suspicious bugs found!\n\n");
  67.     }
  69.     return 0;
  70. }

poj 2236 无线网络

很久之前写的了

  1. /*************************************************************************
  2.   > File Name: 2236.cpp
  3.   > Author: LinKArftc
  4.   > Created Time: 2015/6/4 LinK 01:32:24
  5.  *************************************************************************/
  7. #include <cstdio>
  8. #include <iostream>
  9. #include <cstring>
  10. #include <algorithm>
  11. #include <cmath>
  12. using namespace std;
  13. #define MAXN 1010
  15. int n, rank[MAXN], pa[MAXN], rep[MAXN];
  17. struct Node {
  18.     int x, y;
  19. } pos[MAXN];
  21. void init() {
  22.     for (int i = 1; i <= n; i ++) {
  23.         rank[i] = 0;
  24.         pa[i] = i;
  25.     }
  26. }
  27. int find(int x) {
  28.     if (x != pa[x]) pa[x] = find(pa[x]);
  29.     return pa[x];
  30. }
  31. void uion(int x, int y) {
  32.     x = find(pa[x]);
  33.     y = find(pa[y]);
  34.     if (x != y)  {
  35.         if (rank[x] < rank[y]) pa[x] = y;
  36.         else {
  37.             pa[y] = x;
  38.             if (rank[x] == rank[y]) rank[x] ++;
  39.         }
  40.     }
  41. }
  43. double dis(int a, int b) {
  44.     Node x, y;
  45.     x = pos[a];
  46.     y = pos[b];
  47.     return sqrt(1.0*(x.x-y.x)*(x.x-y.x) + 1.0*(x.y-y.y)*(x.y-y.y));
  48. }
  50. int main() {
  51. //    freopen("input.txt", "r", stdin);
  52.     char c;
  53.     int x, y, cnt;
  54.     double d;
  55.     scanf("%d%lf", &n, &d);
  56.     for (int i = 1; i <= n; i ++) scanf("%d %d", &pos[i].x, &pos[i].y);
  57.     cnt = 0;
  58.     init();
  59.     while (~scanf(" %c %d", &c, &x)) {
  60.         if (c == 'O') {
  61.             for (int i = 0; i < cnt; i ++) {
  62.                 if (dis(rep[i], x) <= d) uion(rep[i], x);
  63.             }
  64.             rep[cnt ++] = x;
  65.         } else {
  66.             scanf("%d", &y);
  67.             if (find(x) == find(y)) printf("SUCCESS\n");
  68.             else printf("FAIL\n");
  69.         }
  70.     }
  71.     return 0;
  72. }

poj 1611 疑似患者

简单，很久之前写的代码，稍微改下代码风格

  1. /*
  2. ID: LinKArftc
  3. PROG: 1611.cpp
  4. LANG: C++
  5. */
  7. #include <cstdio>
  8. #include <iostream>
  9. #include <cstring>
  10. #include <algorithm>
  11. using namespace std;
  13. const int maxn = 30010;
  15. int father[maxn];
  16. int tmp[maxn];
  18. int find(int x) {
  19.     if (x != father[x]) father[x] = find(father[x]);
  20.     return father[x];
  21. }
  23. void unin(int a, int b) {
  24.     int x = find(a);
  25.     int y = find(b);
  26.     if (x != y) father[x] = y;
  27. }
  30. int main() {
  31. //    freopen("input.txt", "r", stdin);
  33.     int n, k;
  34.     while (~scanf("%d %d", &n, &k)) {
  35.         if (n == 0 && k == 0) break;
  36.         for (int i = 0; i < n; i ++) father[i] = i;
  37.         for (int i = 1; i <= k; i ++) {
  38.             int m, t1, t2;
  39.             scanf("%d %d", &m, &t1);
  40.             for (int j = 2; j <= m; j ++) {
  41.                 scanf("%d", &t2);
  42.                 unin(t1, t2);
  43.             }
  44.         }
  45.         int ans = 1;
  46.         for (int i = 1; i < n; i ++) {
  47.             if (find(i) == find(0)) ans ++;
  48.         }
  49.         printf("%d\n", ans);
  50.     }
  52.     return 0;
  53. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注