一般的并查集，维护的是具有连通性、传递性的关系，例如亲戚的亲戚是亲戚。但是，有时候，我们要维护另一种关系：敌人的敌人是朋友。种类并查集就是为了解决这个问题而诞生的。

敌人关系是可以扩展的：捕食等等

例题洛谷P152 关押罪犯
开一个两倍大小的并查集。

开几倍要看有几种关系

例如，假如我们要维护4个元素的并查集，我们改为开8个单位的空间：

用1~4维护朋友关系（就这道题而言，是指关在同一个监狱的狱友），用5~8维护敌人关系（这道题里是指关在不同监狱的仇人）。现在假如我们得到信息：1和2是敌人，应该怎么办？

我们merge(1, 2+n), merge(1+n, 2);。这里n就等于4，但我写成n这样更清晰。对于1个编号为i的元素，i+n是它的敌人。所以这里的意思就是：1是2的敌人，2是1的敌人。
假如我们又知道2和4是敌人，我们merge(2, 4+n), merge(2+n, 4);

这里，1和4通过2+n这个元素间接地连接起来了——也就是敌人的敌人就是朋友。这就是种类并查集工作的原理。

  1. int fa[40005], rank[40005];  //以下为并查集
  2. int find(int a)
  3. {
  4.     return (fa[a] == a) ? a : (fa[a] = find(fa[a]));
  5. }
  6. int query(int a, int b)
  7. {
  8.     return find(a) == find(b);
  9. }
  10. void merge(int a, int b)
  11. {
  12.     int x = find(a), y = find(b);
  13.     if (_rank[x] >= _rank[y])
  14.         fa[y] = x;
  15.     else
  16.         fa[x] = y;
  17.     if (_rank[x] == _rank[y] && x != y)
  18.         _rank[x]++;
  19. }
  20. void init(int n)
  21. {
  22.     for (int i = 1; i <= n; ++i)
  23.     {
  24.         _rank[i] = 1;
  25.         fa[i] = i;
  26.     }
  27. }

模板和并查集没什么区别，具体区别在于使用merge的时候

例题

L2-010 排座位 (25 分)

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,m,k;
  5. //种类并查集
  6. int fa[2550],_rank[2550];
  7. int g[105][105];
  8. int find(int a){
  9.     return a==fa[a]?a:(fa[a] = find(fa[a]));
  10. }
  11. void merge(int a, int b){
  12.    int x = find(a), y = find(b);
  13.    if (_rank[x] >= _rank[y])
  14.         fa[y] = x;
  15.     else
  16.         fa[x] = y;
  17.     if (_rank[x] == _rank[y] && x != y)
  18.         _rank[x]++;
  20. }
  21. int query(int a, int b){
  22.     int f1=find(a),f2=find(b),f200=find(b+100);
  23.     if(f1 == f2){
  24.         if(g[a][b])return 3;
  25.         return 1;
  26.     }else{
  27.         if(g[a][b])return 4;
  28.         return 2;
  29.     }
  30. }
  31. void print(int q){
  32.     if(q==1)cout<<"No problem\n";
  33.     else if(q==2)cout<<"OK\n";
  34.     else if(q==3)cout<<"OK but...\n";
  35.     else if(q==4)cout<<"No way\n";
  36. }
  37. int main()
  38. {
  39.     ios::sync_with_stdio(false);
  40.     cin>>n>>m>>k;
  41.     for(int i = 0; i<2550;i++){fa[i]=i;_rank[i]=1;}
  42.     for(int i = 1; i<= m; i++){
  43.         int a, b, f;
  44.         cin>>a>>b>>f;
  45.         if(f==1){
  46.             merge(a,b);
  47.         }else{
  48.             g[a][b]=g[b][a]=1;
  49.         }
  50.     }
  51.     for(int i = 1;i<=k;i++){
  52.         int a,b;
  53.         cin>>a>>b;
  54.         int q = query(a,b);
  55.         print(q);
  56.     }
  58.     return 0;
  59. }

题目中所说朋友的朋友也是朋友，使用并查集把他们并到一个朋友圈中,但两个人只能有一种关系，故朋友和敌人不能用一个容器来记录，应该分开记录