一、个人心得

个人理解：

并查集的本质是对传递性关系的维护

传递性关系：
如果在对象甲、对象乙和对象丙之间,甲对乙有某种关系,乙对丙也有这种关系,可以推出甲对丙也有这种关系,那么,这种关系就是传递关系.

具体的例子，比如关系：X和Y属于同一集合，Y和Z属于同一集合，可以推出X和Z属于同一集合，这也是普通并查集的应用（可以合并、查询集合，所以叫并查集233）

更复杂的传递关系：

①X和Y相距$d_1$，Y和Z相距为$d_2$,则可以推出X和Z的距离(这里的距离指同一方向）（可参考第9题，曼哈顿距离其实可以分解为水平和竖直方向的两种距离，也就是两种关系，然后分别维护）

②已知X和Y同性，Y和Z同性，可以推出X和Z同性，只要知道X和Y的性别相对关系，以及Y和Z的性别相对关系，就可以推出X和Z的性别相对关系（参考第10题）

③食物链（第5题）关系，石头剪子布关系，即三者循环克制的关系，已知A和B的关系及B和C的关系，可以推出A和C的关系

为什么并查集可以维护传递性关系呢？

因为并查集优越的地方在于其路径压缩能极大地减小时间复杂度。而在路径压缩后，每个点的父结点会变为根节点，破坏了点与点之间的连接关系。但是如果维护的是传递性关系，可以由两个点各自和根节点的关系推导出这两个点之间的关系。

对于复杂的传递性关系，需要用到带权并查集。具体写法可见：

普通并查集详解

详情可见 并查集及两种优化

带权并查集详解

详情可见带权并查集

题目链接

普通并查集：1、2、3、13、14
带权并查集：4、5、6、8、9、10、11
“点带权”并查集：12
贪心+路径压缩：7

梳理一下：
3、13、14都是很简单的入门模板题
1、2、7需要对并查集有一定的理解
带权并查集的几道题建议先理解了并查集之后再做

tips:还差三题，近期考试多，有空一定补上 咕咕咕
tips：补完了补完了

二、题解：

1.Wireless Network POJ - 2236

将所有可以互相连通的电脑放在一个集合中
对于O操作（修电脑），将该电脑与所有已经修好的电脑判断一下，若距离小于D，则合并集合
对于S操作（查询），直接查询两个电脑是否属于同一个集合即可

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;

typedef struct{
    
  int x,y;
  int index;
}pos;

int pre[1005];
pos p[1005];
pos repaired[1005];

void init(){
    
   for(int i=1;i<=1000;i++)
      pre[i]=i;
}

int root_find(int x){
    
   return pre[x]==x?x:pre[x]=root_find(pre[x]);
}

void join(int x,int y){
    
  int rx=root_find(x);
  int ry=root_find(y);
  if(rx!=ry)
    pre[rx]=ry;
}

double dis(pos a,pos b){
    
   return sqrt((double)(a.x-b.x)*(double)(a.x-b.x)+(double)(a.y-b.y)*(double)(a.y-b.y));
}

int main()
{
    
    init();
    int N,D;
    scanf("%d%d",&N,&D);
    for(int i=1;i<=N;i++)
        scanf(" %d %d",&p[i].x,&p[i].y);
    int cnt=0;
    char type;
    while(~scanf(" %c",&type)){
    
       if(type=='O') {
    
          int temp;
          scanf("%d",&temp);
          repaired[cnt].x=p[temp].x;
          repaired[cnt].y=p[temp].y;
          repaired[cnt].index=temp;
          for(int i=0;i<cnt;i++){
    
              if(dis(repaired[i],p[temp])<=D){
    

                  join(repaired[i].index,temp);
              }
          }
          cnt++;
       }
       else{
    
         int a,b;
         scanf(" %d %d",&a,&b);
         if(root_find(a)==root_find(b))
              printf("SUCCESS\n");
         else
              printf("FAIL\n");
       }

    }
    return 0;
}

2.The Suspects POJ - 1611

将所有可能会互相传染的人放在一个集合中

比如：
group1={学生1，学生2，学生3，学生7}；
group2={学生2，学生5，学生18}；

假设学生7是嫌疑人，则学生2也变成了嫌疑人，group2的所有学生也都是嫌疑人了
即，只要两个group有相同的学生，都应该放在同一个集合中。

处理完后，枚举所有学生，和0号学生属于同一个集合的就是suspect

#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <algorithm>
using namespace std;

int n,m;
int pre[30005];

void init(){
    
   for(int i=0;i<=30000;i++)
       pre[i]=i;
}

int root_find(int x){
    
   return pre[x]==x?x:pre[x]=root_find(pre[x]);
}

void join(int x,int y){
    
  int rx=root_find(x);
  int ry=root_find(y);
  if(rx!=ry){
    
      pre[rx]=ry;
  }
}

int main()
{
    
    while(~scanf("%d%d",&n,&m)){
    
         if(n==0&&m==0)  break;
         init();
         for(int i=0;i<m;i++){
    
             int k;
             scanf("%d",&k);
             int first;
             for(int j=0;j<k;j++){
    
                 int temp;
                 scanf("%d",&temp);
                 if(j==0)  first=temp;
                 else    join(temp,first);
             }
         }
         int root=root_find(0);
         int ans=1;
         for(int i=1;i<n;i++)
            if(root_find(i)==root)
                ans++;
         printf("%d\n",ans);
    }
    return 0;
}

3.How Many Tables HDU - 1213

大意：
题目给出哪些人属于同一个集合
判断集合个数

做法：
一开始令集合个数ans=N；
然后对于题目给出的：a和b是朋友（属于同一个集合）
若a和b根据之前的信息还不是一个集合的，则ans–
否则，ans不变，因为对于答案没有贡献

#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <algorithm>
using namespace std;

int n,m;
int pre[30005];

void init(){
    
   for(int i=0;i<=30000;i++)
       pre[i]=i;
}

int root_find(int x){
    
   return pre[x]==x?x:pre[x]=root_find(pre[x]);
}

bool join(int x,int y){
    
  int rx=root_find(x);
  int ry=root_find(y);
  if(rx!=ry)
      pre[rx]=ry;
  else
      return 0;
  return 1;
}

int main()
{
    
    int T;
    scanf("%d",&T);
    while(T--){
    
       init();
       int N,M;
       scanf("%d%d",&N,&M);
       int ans=N;
       for(int i=0;i<M;i++){
    
          int a,b;
          scanf("%d%d",&a,&b);
          if(join(a,b)) ans--;
       }
       printf("%d\n",ans);
    }
    return 0;
}

4.How Many Answers Are Wrong HDU - 3038

带权并查集详解见文章开头

这道题我想了很久才想明白
题目大意：

有n个数，编号1~n，FF会向TT询问m次，序号[a,b]上的数之和为多少。TT会说假话，所以有些区间和是错误（和之前的话相矛盾）的。题目保证如果给你的区间和和前面的区间和不矛盾的话，则这个区间和一定是对的。题目要求判断假话数量

①首先，如果我们知道了[a,b]和[b+1,c]上的数之和，则[a,c]上数之和是可以推出来的。

②如何保存这个信息？对于[a,b]上数之和，将其抽象为边的权值，即端点a和端点b之间的权值，则对于题目给出的m个[a,b]区间的和，就转化为了森林，端点相接的在同一棵树上（即树链）

为了方便处理，将[a,b]转化为（a,b]。好处是可以将[a,b]和[b+1,c]的端点拼起来

比如：

已知[4,7]上的数之和为5，将这个信息保存为：点3和点7之间有边相连，权值为5
已知[2,3]上的数之和为2，将这个信息保存为：点1和点3之间有边相连，权值为2

则点1和点7间的距离也可得到

③使用的数据结构：带权并查集，因为这道题中需要维护的信息显然具有传递性。

④在路径压缩以及两个树的合并时都需要更新d值，d[x]记录的是点x与其“父亲”之间的边的权值，依据这一点考虑d值的更新方式即可。

#include <cstdio>
using namespace std;

int pre[200005];
int d[200005];

int M,N;

void init(){
    
  for(int i=0;i<=200000;i++)
      pre[i]=i,d[i]=0;
}

int root_find(int x){
    
   if(x==pre[x])  return x;
   int root=root_find(pre[x]);
   d[x]+=d[pre[x]];
   return pre[x]=root;
}

void join(int x,int y,int _d){
    
   int rx=root_find(x);
   int ry=root_find(y);
   pre[rx]=ry;
   d[rx]=_d+d[y]-d[x];
}

int main()
{
    
    while(~scanf("%d%d",&N,&M)){
    
      int ans=0;
      init();
      for(int i=0;i<M;i++){
    
          int a,b,s;
          scanf("%d%d%d",&a,&b,&s);
          a--;
          int ra=root_find(a);
          int rb=root_find(b);
          if(ra!=rb) join(a,b,s);
          else if(d[a]-d[b]!=s) ans++;
      }
      printf("%d\n",ans);
    }
    return 0;
}

5.食物链 POJ - 1182

和上一题一样还是一道带权并查集的题，用权值储存每个点与其父结点的关系，0表示同类，1表示吃父结点，2则是被父结点吃。

权值的更新巧妙地用到了模运算

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

int pre[50005];
int rela[50005]; //0表示同类，1表示吃父节点，2表示被父节点吃

void init(){
    
  for(int i=0;i<=50000;i++)
      pre[i]=i,rela[i]=0;
}

int root_find(int x){
    
   if(x==pre[x])  return x;
   int root=root_find(pre[x]);
   rela[x]+=rela[pre[x]],rela[x]%=3;
   return pre[x]=root;
}

void join(int x,int y,int r){
    
  int rx=root_find(x);
  int ry=root_find(y);
  if(rx!=ry){
    
      pre[rx]=ry;
      rela[rx]=(r+rela[y]-rela[x]+3)%3;
  }
}

int main()
{
    
    init();
    int N,K;
    scanf("%d%d",&N,&K);
    int ans=0;
    for(int i=1;i<=K;i++){
    
       int D,X,Y;
       scanf("%d%d%d",&D,&X,&Y);
       if(X>N||Y>N){
    ans++;continue;}
       if(D==2&&X==Y) {
    ans++;continue;}
       int rx=root_find(X);
       int ry=root_find(Y);
       if(rx!=ry) {
    
           if(D==1)
              join(X,Y,0);
           else
              join(X,Y,1);
       }
       else{
    
          int fact=(rela[X]-rela[Y]+3)%3;//fact记录二者关系应该是什么
          if(D==1&&fact!=0) ans++;   
          else if(D==2&&fact!=1)  ans++;
       }

    }
    printf("%d\n",ans);
    return 0;
}

6.True Liars POJ - 1417

dp+带权并查集，dp蒟蒻做自闭了

题面：
正义阵营只会说真话，邪恶阵营只会说假话

共有n句话，形如x y a
表示：x说y属于正义或邪恶（x可以等于y）

其中a为yes或no（yes表示正义，no表示邪恶）

题目保证不会出现矛盾的情况。

分析：
对于 x y yes 这句话：
如果x是正义的（即说真话），则y必然也是正义的
若x是邪恶的，则其说的是假话，y必然也是邪恶的

所以，x y yes这句话表示x和y属于同一阵营
同理，可以推出x y no 表示x和y属于不同阵营

如果x=y：

x x yes 表明x和x属于同一阵营，废话
x x no 自相矛盾，不可能出现

综上，这道题需要我们维护的关系和第10题A Bug’s Life（POJ - 2492）很像，带权并查集即可。

我们可以用一个带权并查集（森林）维护题目给出的信息，但是要判断出到底哪些人属于正义，哪些人属于邪恶是很麻烦。

例：

2 2 1
1 2 yes
2 3 no

我们可以得到1和2属于同一阵营，3属于一个阵营，
结合有两个人是正义的，一个人是邪恶的这一信息，不难得到：

1和2是正义的，3是邪恶的

更复杂的例子：

5 4 3
1 2 yes
1 3 no
4 5 yes
5 6 yes
6 7 no

可以用并查集维护得到两棵树
①1、2、3 ：1、2为一个阵营，3为一个阵营
②4、5、6、7：4、5、6为一个阵营，7为一个阵营

结合有4个人是正义的，3个人是邪恶的这一信息

可以推出：3、4、5、6是正义的，其它为邪恶的

具体做法：

有n个集合，每个集合中都有两个阵营，一方为正义的、一方为邪恶的。
我们无从判断到底哪方是正义的、哪方是邪恶的，不如枚举。

那么每个集合都有两种可能，n个集合共有$2^n$种方案，如果其中能找到唯一的方案，满足正义、邪恶的人数满足题目要求，则这道题有解

代码:

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

const int maxn=1005;
int pre[maxn];
int rela[maxn];// 0 同类 1 异类
vector<int>tree[maxn];
vector<int>group_0[maxn]; // 与 根节点相同的子集
vector<int>group_1[maxn]; // 与 根节点不同的子集
int dp[maxn][maxn];

typedef struct{
    
  int a,b;//a 和根节点同类 b 异类
}Item;

Item item[maxn];

void init(){
    
  memset(dp,0,sizeof(dp));
  for(int i=1;i<=1000;i++){
    
      pre[i]=i,rela[i]=0;
      group_0[i].clear();
      group_1[i].clear();
      tree[i].clear();
  }
}

int root_find(int x){
    
  if(x==pre[x])  return x;
  int root=root_find(pre[x]);
  rela[x]^=rela[pre[x]];
  return pre[x]=root;
}

void join(int x,int y,int r){
    
   int rx=root_find(x);
   int ry=root_find(y);
   if(rx!=ry){
    
       rela[rx]=rela[x]^rela[y]^r;
       pre[rx]=ry;
   }
}


int main(){
    
  int n,p1,p2;
  while(cin>>n>>p1>>p2){
    
      if(!n&&!p1&&!p2)
          break;
      int x,y;
      string t;
      init();
      for(int i=1;i<=n;i++){
    
         cin>>x>>y>>t;
         int r;
         if(t=="yes")  r=0;
         else r=1;
         join(x,y,r);
      }

     if(p1==p2) {
    cout<<"no"<<endl;continue;}
     //先将并查集的森林转化为邻接矩阵存储便于后续操作
     for(int i=1;i<=p1+p2;i++){
    
         int root=root_find(i);
         tree[root].push_back(i);
     }

     //映射为连续的整数便于后续操作
     int cnt=1;
     for(int i=1;i<=p1+p2;i++){
    
          int t=tree[i].size();
          int num=0;
          if(t){
    
              for(int j=0;j<t;j++){
    
                   if(rela[tree[i][j]]==1)
                        group_1[cnt].push_back(tree[i][j]);
                   else{
    
                        group_0[cnt].push_back(tree[i][j]);
                        num++;
                   }
              }
              item[cnt].a=num;
              item[cnt].b=t-num;
              cnt++;
          }
     }
     // dp
     dp[0][0]=1;
     for(int i=1;i<cnt;i++){
    
         for(int j=0;j<=p1;j++){
    
           if(j-item[i].a>=0)
               dp[i][j]+=dp[i-1][j-item[i].a];
           if(j-item[i].b>=0)
               dp[i][j]+=dp[i-1][j-item[i].b];
         }
     }

     if(dp[cnt-1][p1]!=1){
    cout<<"no"<<endl;continue;}
     int value=p1;
     int num=0;
     int ans[maxn];
     for(int i=cnt-1;i>=1;i--){
    
         if(dp[i-1][value-item[i].a]==1){
    
            for(int j=0;j<group_0[i].size();j++)
                       ans[num++]=group_0[i][j];
            value-=item[i].a;
         }
         else{
    
            for(int j=0;j<group_1[i].size();j++)
                       ans[num++]=group_1[i][j];
            value-=item[i].b;
         }
     }

     sort(ans,ans+num);
     for(int i=0;i<num;i++)
        cout<<ans[i]<<endl;
     cout<<"end"<<endl;
  }
  return 0;
}

7.Supermarket POJ - 1456

这题虽然被归在并查集里，但其实主要考察的是贪心思想，也并没有卡贪心的朴素做法$O(N^2)$的时间，所以我把这题的思路另开了一篇博客讲：点此跳转

不过用并查集确实能进一步优化时间复杂度，可以学习一下

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

typedef struct{
    
  int profit;
  int deadline;
}product;

product p[10005];
int pre[100005];

bool cmp(product a,product b){
    
   if(a.profit!=b.profit)
       return a.profit>b.profit;
   return a.deadline>b.deadline;
}

int _find(int x){
    
   return pre[x]==-1?x:pre[x]=_find(pre[x]);
}

int main()
{
    
    int N;
    while(~scanf("%d",&N)){
    
       memset(pre,-1,sizeof(pre));
       for(int i=1;i<=N;i++)
         scanf("%d %d",&p[i].profit,&p[i].deadline);
  
       sort(p+1,p+N+1,cmp);
       int ans=0;
       for(int i=1;i<=N;i++){
    
           int time=_find(p[i].deadline);
           if(time>0){
    //如果为0则说明这个商品已经没有位置可以放了
              ans+=p[i].profit;
              pre[time]=time-1;
           }
       }

       printf("%d\n",ans);
    }
    return 0;
}

8.Parity game POJ - 1733

综合性较强的一题，感觉像第4题和第10题的结合，可以先看那两道题，再看这题：

①用带权并查集存储信息，并用异或来进行运算
②虽然区间端点值可能很大，但是个数很少，所以离散化处理即可

不会离散化可以看这篇：离散化

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

typedef struct{
    
   long long a,b;
   int parity;
}information;

information inform[5005];
long long  point[10005];
long long  mapping[10005];
int pre[10005];
int d[10005];
int cnt=0;
int num=0;

void init(){
    
  for(int i=0;i<=10000;i++)
       pre[i]=i,d[i]=0;
}

int root_find(int x){
    
   if(x==pre[x])  return x;
   int root=root_find(pre[x]);
   d[x]^=d[pre[x]];
   return pre[x]=root;
}

void join(int x,int y,int p){
    
  int rx=root_find(x);
  int ry=root_find(y);
  pre[rx]=ry;
  d[rx]=p^d[y]^d[x];
}

void discrete(){
    
   sort(point,point+cnt,less<long long>());
   for(int i=0;i<cnt;i++)
       if(!i||point[i]!=point[i-1])
             mapping[num++]=point[i];
}

int Query(long long x){
    
  return lower_bound(mapping,mapping+num,x)-mapping;
}

int main()
{
    
    init();
    int Len;
    scanf("%d",&Len);
    int N;
    scanf("%d",&N);
    for(int i=0;i<N;i++){
    
       char temp[5];
       scanf("%lld%lld %s",&inform[i].a,&inform[i].b,&temp);
       inform[i].a--;
       if(strcmp(temp,"odd")==0)
            inform[i].parity=1;
       else inform[i].parity=0;
       point[cnt++]=inform[i].a;
       point[cnt++]=inform[i].b;
     }
     discrete();
     int x=0;
     for(int i=0;i<N;i++){
    
        int qa=Query(inform[i].a);
        int qb=Query(inform[i].b);
        int ra=root_find(qa);
        int rb=root_find(qb);
        if(ra!=rb)  join(qa,qb,inform[i].parity);
        else if(d[qa]^d[qb]!=inform[i].parity)
           break;
        x++;
     }
     printf("%d\n",x);
    return 0;
}

9.Navigation Nightmare POJ - 1984

涉及大量的集合合并与查询的操作，用并查集是很好的选择，因为要保存集合内点之间的关系（距离），所以带权并查集

这道题巧妙的点在于：设置水平和竖直方向两种权值

坑点在于：并没有明显指出询问的时间（index）是非减的

距离这种具备累加性的关系，还是比较好写的

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

typedef struct{
    
  int f1,f2;
  int dis;
  char direct;
}road;

int N,M;
int pre[40005];
int horizonal[40005]; //记录和根节点水平方向的距离
int vertical[40005]; //记录和根节点竖直方向的距离
road r[40005];

void init(){
    
  for(int i=1;i<=40000;i++)
      pre[i]=i,vertical[i]=0,horizonal[i]=0;
}

int root_find(int x){
    
   if(x==pre[x]) return x;
   int root=root_find(pre[x]);
   horizonal[x]+=horizonal[pre[x]];
   vertical[x]+=vertical[pre[x]];
   return pre[x]=root;
}

void join(int x,int y,int h_dis,int v_dis){
    
  int rx=root_find(x);
  int ry=root_find(y);
  pre[rx]=ry;
  horizonal[rx]=h_dis+horizonal[y]-horizonal[x];
  vertical[rx]=v_dis+vertical[y]-vertical[x];
}

int main()
{
    
    init();
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;i++)
        scanf("%d%d%d %c",&r[i].f1,&r[i].f2,&r[i].dis,&r[i].direct);

    int K;
    scanf("%d",&K);
    int pos=1;
    while(K--){
    
       int index;
       int a,b;
       scanf("%d%d%d",&a,&b,&index);
       for(int i=pos;i<=index;i++){
    
           int temp_h=0,temp_v=0;
           if(r[i].direct=='E')  temp_h=r[i].dis;
           else if(r[i].direct=='W') temp_h=-1*r[i].dis;
           else if(r[i].direct=='N') temp_v=r[i].dis;
           else temp_v=-1*r[i].dis;
           join(r[i].f1,r[i].f2,temp_h,temp_v);
       }
       pos=index+1;
       int ra=root_find(a);
       int rb=root_find(b);

       if(ra!=rb) printf("-1\n");
       else printf("%d\n",abs(vertical[a]-vertical[b])+abs(horizonal[a]-horizonal[b]));
    }
    return 0;
}

10.A Bug’s Life POJ - 2492

和食物链那题很相似，但是更简单一点，可以用异或运算来维护点的关系，用0表示同性，1表示异性。（同性的同性，异性的异性结果都是同性；同性的异性或者异性的同性结果是异性，所以和异或运算契合，同则0，异则1）

#include<cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;

int pre[2005];
int d[2005];// 0表示和父结点同性，1表示异性

int root_find(int x){
    
   if(x==pre[x]) return x;
   int root=root_find(pre[x]);
   d[x]=d[x]^d[pre[x]];
   return pre[x]=root;
}

void join(int a,int b,int t){
    
  int ra=root_find(a);
  int rb=root_find(b);
  d[ra]=d[a]^d[b]^t;
  pre[ra]=rb;
}


int main() {
    
  int t;
  scanf("%d",&t);
  for(int Case=1;Case<=t;Case++){
    
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) pre[i]=i,d[i]=0;
    int flag=0;
    for(int i=1;i<=m;i++){
    
       int a,b;
       scanf("%d%d",&a,&b);
       int ra=root_find(a);
       int rb=root_find(b);
       if(ra!=rb)  join(a,b,1);
       else if(d[a]^d[b]!=1) flag=1;
    }
    printf("Scenario #%d:\n",Case);
    if(flag) printf("Suspicious bugs found!\n");
    else printf("No suspicious bugs found!\n");
    printf("\n");
  }
	return 0;
}

11.Rochambeau POJ - 2912

N个孩子（编号0~N-1）玩石头剪子布，每个人都只能固定选择一种玩法：即一直出石头/剪刀/布。唯一的例外是裁判，裁判会随机出。

题目给出M局游戏的结果，要求我们据其找到裁判。

分析：
用并查集维护孩子之间的克制关系
裁判会导致矛盾/假话的出现
枚举每个孩子，假设其为裁判。和该孩子有关的游戏不讨论，如果仍发现了矛盾的地方，说明这个孩子不可能是裁判

①如果可能为裁判的孩子数量大于1，说明题目给出的信息是不可能出现的结果
②如果没有找到可能为裁判的孩子，说明无法判断
③如果可能为裁判的孩子数量为1，则该孩子是裁判，还需要判断是在第几句话之后发现该孩子是裁判的。
才枚举的过程中，如果发现了矛盾会直接break（说明该孩子不可能是裁判），用pos变量记录当前是第几句话。而找到裁判需要排除其它所有的孩子，所以是pos的最大值。我们对其进行维护即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <queue>
using namespace std;

const int inf=0x3f3f3f3f;

typedef struct{
    
  int a,b;
  char cmp;
}round;

int N,M;
round rd[2005];
int rela[505]; //0平手 1克父结点 2被父结点克
int pre[505];

void init(){
    
  for(int i=0;i<=500;i++)
      pre[i]=i,rela[i]=0;
}

int root_find(int x){
    
  if(x==pre[x])  return x;
  int root=root_find(pre[x]);
  rela[x]+=rela[pre[x]],rela[x]%=3;
  return pre[x]=root;
}

void join(int x,int y,int r){
    
  int rx=root_find(x);
  int ry=root_find(y);
  if(rx!=ry){
    
     pre[rx]=ry;
     rela[rx]=(r+rela[y]-rela[x]+3)%3;
  }
}

int main()
{
    
    while(~scanf("%d%d",&N,&M)){
    
       for(int i=0;i<M;i++)
          scanf("%d %c %d",&rd[i].a,&rd[i].cmp,&rd[i].b);
       int num=0;
       int pl;
       int pos=0;

       for(int i=0;i<N;i++){
    
         init();
         int flag=1;
         for(int j=0;j<M;j++){
    
            if(rd[j].a==i||rd[j].b==i) continue;
            int ra=root_find(rd[j].a);
            int rb=root_find(rd[j].b);
            int temp;
            if(rd[j].cmp=='>') temp=1;
            else if(rd[j].cmp=='=') temp=0;
            else temp=2;
            if(ra!=rb)  join(rd[j].a,rd[j].b,temp);
            else if((rela[rd[j].a]-rela[rd[j].b]+3)%3!=temp){
    
               flag=0;
               pos=max(pos,j+1);
               break;
            }
         }
         if(flag) num++,pl=i;
       }


       if(N==1)  pos=0;
       if(num>1)  printf("Can not determine\n");
       else if(num==0)  printf("Impossible\n");
       else printf("Player %d can be determined to be the judge after %d lines\n",pl,pos);
    }
    return 0;
}

12.Connections in Galaxy War ZOJ - 3261

我们常说的带权并查集是边带权并查集，即用权值来记录子结点和父结点的关系，而这道题每个点都有权值（power）。

题目大意：
每个星球只能向其能联系到的星球中power最大（如果有多个就取序号最小的）且power比自己大的星球求助。

一开始给出M条信息，形如：a b；代表a、b星球间可以相互联系到

然后给出Q条指令，query指令代表询问星球x会向哪个星球求助（或者输出-1代表没有求援对象）；destroy指令代表破坏星球x和星球y之间的联系。

分析：
用并查集来维护能互相联系到的点，并让并查集的根节点(集合代表）是这个集合中权值最大且序号最小的元素。如何实现？只要在合并集合函数中进行判断即可，让权值大的点成为根节点。

问题出在拆边（destroy）上，并查集并无法实现这个功能。但是有一个很巧妙的做法，先记录Q条指令，对于不会被destroy的边，直接连起来。然后倒着处理这Q条指令，遇到destroy后将这条边在加上即可。

有几个要注意的地方：
①每个星球只能向比自己power大的星球，所以如果这个星球所在集合的代表和这个星球power一样大（只是序号更小所以成为了集合代表），那么这个星球也是没法求援的。
②两组输出的数据间需要加一个空行，最后一组数据不需要输出空行
③个人是用一个结构体来记录边的信息的，然后用map来判断哪些边会被destroy。然后就出现了问题，后来才知道map会对key值进行排序，所以要重载操作符（<和==都要重载）
④记得初始化时清空map（WA的教训 ）

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <string>
#include <map>
using namespace std;

const int inf=0x3f3f3f3f;

typedef struct{
    
 int a,b;
}tunnel;

typedef struct{
    
  bool type;
  int q;
  tunnel d;
}query;

int N;
int pre[10005];
long long pl[10005];
tunnel tnl[20005];
query qry[50005];
int ans[50005];
map<tunnel,int>mp;

//重载操作符，因为map需要对key值进行排序
bool operator <(tunnel x,tunnel y){
     
  if(x.a!=y.a) return x.a<y.a;
   return x.b<y.b;
}

bool operator ==(tunnel x,tunnel y){
    
 return x.a==y.a&&x.b==y.b;
}

void init(){
    
  for(int i=0;i<=10000;i++)
      pre[i]=i;
  mp.clear();
}

int root_find(int x){
    
   return pre[x]==x?x:pre[x]=root_find(pre[x]);
}

void join(int x,int y){
    
  int rx=root_find(x);
  int ry=root_find(y);
  if(rx==ry)  return;
  if(pl[rx]<pl[ry]) pre[rx]=ry;
  else if(pl[rx]>pl[ry]) pre[ry]=rx;
  else rx<ry?pre[ry]=rx:pre[rx]=ry;
}

int main()
{
    
    int Case=0;
    while(~scanf("%d",&N)){
    
      init();
      //所有信息都先读入后再进行操作
      for(int i=0;i<N;i++)
         scanf("%lld",&pl[i]);

      int M;
      scanf("%d",&M);
      for(int i=0;i<M;i++)
         scanf("%d%d",&tnl[i].a,&tnl[i].b);

      int Q;
      scanf("%d",&Q);
      for(int i=0;i<Q;i++){
    
         string temp;
         cin>>temp;
         if(temp=="destroy") {
    
             tunnel t_;
             scanf(" %d %d",&t_.a,&t_.b);
             qry[i].d=t_;
             qry[i].type=0;
             mp[t_]=1;
             mp[{
    t_.b,t_.a}]=1;
         }
         else{
    
            scanf(" %d",&qry[i].q);
            qry[i].type=1;
         }
      }
      //连接不会被拆的边
      for(int i=0;i<M;i++)
         if(mp[tnl[i]]==0&&mp[{
    tnl[i].b,tnl[i].a}]==0)
            join(tnl[i].a,tnl[i].b);


      //倒序处理并记录答案
      int cnt=0;
      for(int i=Q-1;i>=0;i--){
    
         if(qry[i].type==1){
    
             int rx=root_find(qry[i].q);
             if(rx!=qry[i].q&&pl[rx]>pl[qry[i].q])
                    ans[cnt++]=rx;
             else
                    ans[cnt++]=-1;
         }
         else join(qry[i].d.a,qry[i].d.b);
      }
     //数据间的空行
     if(Case) printf("\n");
     Case++;
     //倒着输出，因为之前是倒序处理的
     for(int i=cnt-1;i>=0;i--)
        printf("%d\n",ans[i]);
    }

    return 0;
}

测试数据：

3
20 20 20
3
1 2
0 1
0 2
4
query 1
query 2
destroy 1 2
query 2
-1
-1
-1
3
10 20 10
2
1 2
0 1
5
query 0
query 1
query 2
destroy 1 2
query 2

1
-1
1
-1

13.小希的迷宫 HDU - 1272

给定n个点判断是否为树：
①满足任意两个点只有一条通路
②点数=边数+1

并查集模板题：
坑数据点：0 0 为Yes

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

int pre[100005];
int buc[100005];

void init(){
    
  for(int i=1;i<=100000;i++)
      pre[i]=i,buc[i]=0;
}

int root_find(int x){
    
  return pre[x]==x?x:pre[x]=root_find(pre[x]);
}

void join(int x,int y){
    
  int rx=root_find(x);
  int ry=root_find(y);
  if(rx!=ry) pre[rx]=ry;
}

int main()
{
    
    int a,b;
    while(1){
    
       init();
       int flag=1;
       int point_num=0;
       int edge_num=0;
       while(~scanf("%d%d",&a,&b)){
    
          if(a==-1&&b==-1)  return 0;
          if(a==0&&b==0) break;
          if(!buc[a])  buc[a]++,point_num++;
          if(!buc[b])  buc[b]++,point_num++;
          int ra=root_find(a);
          int rb=root_find(b);
          if(ra==rb) flag=0;
          else {
    edge_num++;join(a,b);}
       }
       if(point_num==0&&edge_num==0) printf("Yes\n");
       else if(flag&&edge_num==point_num-1) printf("Yes\n");
       else printf("No\n");
    }

    return 0;
}

14.Is It A Tree? POJ - 1308

和上一题只有输出格式不同

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

int pre[100005];
int buc[100005];

void init(){
    
  for(int i=1;i<=100000;i++)
      pre[i]=i,buc[i]=0;
}

int root_find(int x){
    
  return pre[x]==x?x:pre[x]=root_find(pre[x]);
}

void join(int x,int y){
    
  int rx=root_find(x);
  int ry=root_find(y);
  if(rx!=ry) pre[rx]=ry;
}

int main()
{
    
    int a,b;
    int Case=1;
    while(1){
    
       init();
       int flag=1;
       int point_num=0;
       int edge_num=0;
       while(~scanf("%d%d",&a,&b)){
    
          if(a==-1&&b==-1)  return 0;
          if(a==0&&b==0) break;
          if(!buc[a])  buc[a]++,point_num++;
          if(!buc[b])  buc[b]++,point_num++;
          int ra=root_find(a);
          int rb=root_find(b);
          if(ra==rb) flag=0;
          else {
    edge_num++;join(a,b);}
       }

       if(point_num==0&&edge_num==0||(flag&&edge_num==point_num-1))
               printf("Case %d is a tree.\n",Case++);
       else    printf("Case %d is not a tree.\n",Case++);

    }

    return 0;
}