并查集提高篇

概述

主要记录各种并查集的例题

例1.格子游戏

题目链接

题目描述

Alice和Bob玩了一个古老的游戏：首先画一个 n×n 的点阵（下图 n=3 ）。

接着，他们两个轮流在相邻的点之间画上红边和蓝边：

直到围成一个封闭的圈（面积不必为 1）为止，“封圈”的那个人就是赢家。因为棋盘实在是太大了，他们的游戏实在是太长了！

他们甚至在游戏中都不知道谁赢得了游戏。

于是请你写一个程序，帮助他们计算他们是否结束了游戏？

输入格式

输入数据第一行为两个整数 n 和 m。n表示点阵的大小，m 表示一共画了 m 条线。

以后 m 行，每行首先有两个数字 (x,y)，代表了画线的起点坐标，接着用空格隔开一个字符，假如字符是 D，则是向下连一条边，如果是 R 就是向右连一条边。

输入数据不会有重复的边且保证正确。

输出格式

输出一行：在第几步的时候结束。

假如 m 步之后也没有结束，则输出一行“draw”。

数据范围

\(1≤n≤200，\)

\(1≤m≤24000\)

输入样例

5
1 D
1 R
2 D
1 R
2 D

输出样例

题解

将二维的点映射成一维，若两点连线，则有相同的根节点，每次判断即可

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 40005;
int n,m;
int a,b;
char op;
int pre[N];
int find(int x)
{
    return pre[x]==x?x:pre[x]=find(pre[x]);
}
void init(int n)
{
    for(int i=1;i<=n;i++) pre[i]=i;
}
int get(int x,int y)
{
    return (x-1)*n+y;
}
int main()
{
    cin>>n>>m;
    init(n*n);
    int cnt=0;
    bool flag=false;
    while(m--)
    {
        cnt++;
        cin>>a>>b>>op;
        int cur=get(a,b);
        int tmp;
        if(op=='D') tmp=get(a+1,b);
        else tmp=get(a,b+1);
        if(find(cur)==find(tmp))
        {
            cout<<cnt<<endl;
            flag=true;
            break;
        }
        else 
        {
            int fx=find(cur);
            int fy=find(tmp);
            pre[fx]=fy;
        }
    }
    if(!flag) cout<<"draw"<<endl;
    return 0;
}

例2.搭配购买

题目链接

题目描述

Joe觉得云朵很美，决定去山上的商店买一些云朵。

商店里有 n 朵云，云朵被编号为 1,2,…,n，并且每朵云都有一个价值。

但是商店老板跟他说，一些云朵要搭配来买才好，所以买一朵云则与这朵云有搭配的云都要买。

但是Joe的钱有限，所以他希望买的价值越多越好。

输入格式

第 1 行包含三个整数 n，m，w，表示有 n 朵云，m 个搭配，Joe有 w 的钱。

第 2∼n+1行，每行两个整数 ci，di 表示 i 朵云的价钱和价值。

第 n+2∼n+1+m 行，每行两个整数 ui，vi，表示买 ui 就必须买 vi，同理，如果买 vi 就必须买 ui。

输出格式

一行，表示可以获得的最大价值。

数据范围

\(1≤n≤10000,\)

\(0≤m≤5000,\)

\(1≤w≤10000,\)

\(1≤ci≤5000,\)

\(1≤di≤100,\)

\(1≤ui,vi≤n\)

输入样例

输出样例

题解

将必须买的物品用并查集维护，必须买的物品相当于一个联通块，对所有的联通块进行01背包即可

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10005;
int dp[N];
int n,m,w;
int pre[N],sumc[N],sumd[N];
int c[N],d[N];
int u,v;
void init(int n)
{
    for(int i=1;i<=n;i++)
    {
        pre[i]=i;
        sumc[i]=c[i];
        sumd[i]=d[i];
    }
}
int find(int x)
{
    return pre[x]==x?x:pre[x]=find(pre[x]);
}
int main()
{
    cin>>n>>m>>w;
    for(int i=1;i<=n;i++) cin>>c[i]>>d[i];
    init(n);
    while (m -- )
    {
        cin>>u>>v;
        if(find(u)!=find(v)) 
        {
            int fx=find(u);
            int fy=find(v);
            pre[fx]=fy;
            sumc[fy]+=sumc[fx];
            sumd[fy]+=sumd[fx];
        }
    }
    memset(c,0,sizeof(c));
    memset(d,0,sizeof(d));
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(pre[i]==i)
        {
            c[++cnt]=sumc[i];
            d[cnt]=sumd[i];
        }
    }
    for(int i=1;i<=cnt;i++)
    {
        for(int j=w;j>=c[i];j--)
        {
            dp[j]=max(dp[j],dp[j-c[i]]+d[i]);
        }
    }
    cout<<dp[w]<<endl;
    return 0;
}

例3.银河英雄传说

题目链接

题目描述

有一个划分为 N 列的星际战场，各列依次编号为 1,2,…,N。

有 N 艘战舰，也依次编号为 1,2,…,N，其中第 i 号战舰处于第 i 列。

有 T 条指令，每条指令格式为以下两种之一：

M i j，表示让第 i 号战舰所在列的全部战舰保持原有顺序，接在第 j 号战舰所在列的尾部。
C i j，表示询问第 i 号战舰与第 j 号战舰当前是否处于同一列中，如果在同一列中，它们之间间隔了多少艘战舰。现在需要你编写一个程序，处理一系列的指令。

输入格式

第一行包含整数 T，表示共有 T 条指令。

接下来 T 行，每行一个指令，指令有两种形式：M i j 或 C i j。

其中 M 和 C 为大写字母表示指令类型，i 和 j 为整数，表示指令涉及的战舰编号。

输出格式

你的程序应当依次对输入的每一条指令进行分析和处理：

如果是 M i j 形式，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息；

如果是 C i j 形式，你的程序要输出一行，仅包含一个整数，表示在同一列上，第 i 号战舰与第 j 号战舰之间布置的战舰数目，如果第 i 号战舰与第 j 号战舰当前不在同一列上，则输出 −1。

数据范围

\(N≤30000,T≤500000\)

输入样例

输出样例

-1
1

题解

并查集可以用于维护具有传递性关系的作用，每个集合的大小，绑定到根结点上，每个点到根结点的距离，绑定到每个元素的结点上

可以在find的过程中更新当前点到根节点的距离(d[x])与集合大小(sz[x])，具体更新见代码

题目问的是两条船之间的距离，因此有两种情况

a==b:0
a!=b:abs(d[a] - d[b]) - 1;

代码

#include<iostream>
using namespace std;
const int N=30005;
int pre[N];
int d[N],sz[N];
void init(int n)
{
  for(int i=1;i<=n;i++)
  {
    pre[i]=i;
    sz[i]=1;
  }
}
int find(int x)
{
  if(pre[x]==x) return x; 
  int root=find(pre[x]);
  d[x]+=d[pre[x]];          // d表示到根节点的距离，需要加上父节点到根节点的距离
  return pre[x]=root;
}
void solve()
{
  int t;
  char op;
  int x,y;
  cin>>t;
  init(N-5);
  while(t--)
  {
    cin>>op>>x>>y;
    int fx=find(x),fy=find(y);
    if(op=='M') 
    {
      pre[fx]=fy;             // 更新根节点
      d[fx]=sz[fy];           // 由于是接在末尾，x的根节点到y根节点的距离为原y集合的大小
      sz[fy]+=sz[fx];         // y集合大小增加x集合的大小
    }
    else 
    {
      if(fx!=fy) cout<<"-1"<<endl;
      else
      {
        cout<<max(0,abs(d[x]-d[y])-1)<<endl;
      }
    }
  }
}
int main()
{
  solve();
  return 0;
}

例4.程序自动分析

题目链接

题目描述

在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。

考虑一个约束满足问题的简化版本：假设 x1,x2,x3,… 代表程序中出现的变量，给定 n 个形如 xi=xj 或 xi≠xj 的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。

例如，一个问题中的约束条件为：x1=x2，x2=x3，x3=x4，x1≠x4，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。

现在给出一些约束满足问题，请分别对它们进行判定。

输入格式

输入文件的第 1 行包含 1 个正整数 t，表示需要判定的问题个数，注意这些问题之间是相互独立的。

对于每个问题，包含若干行：

第 1 行包含 1 个正整数 n，表示该问题中需要被满足的约束条件个数。

接下来 n 行，每行包括 3 个整数 i,j,e，描述 1 个相等/不等的约束条件，相邻整数之间用单个空格隔开。若 e=1，则该约束条件为 xi=xj；若 e=0，则该约束条件为 xi≠xj。

输出格式

输出文件包括 t 行。

输出文件的第 k 行输出一个字符串 YES 或者 NO，YES 表示输入中的第 k 个问题判定为可以被满足，NO 表示不可被满足。

数据范围

\(1≤n≤105\)

\(1≤i,j≤109\)

输入样例

输出样例

NO
YES

题解

首先发现数据范围过大，离散化，合并操作在判断操作之前进行，离线操作后利用并查集维护和判断即可

代码

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e5+5;

int ini[N],inj[N];
int pre[2*N];
int e[N];
int a[2*N+5];
int n;
void init(int n)
{
    for(int i=1;i<=n;i++) pre[i]=i;
}
int find(int x)
{
    return pre[x]==x?x:pre[x]=find(pre[x]);
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
            cin>>ini[i]>>inj[i]>>e[i];
            a[++cnt]=ini[i];
            a[++cnt]=inj[i];
        }
        sort(a+1,a+cnt+1);
        int len=unique(a+1,a+cnt+1)-a-1;
        init(len);
        //cout<<len<<endl;
        bool flag=true;
        for(int i=1;i<=n;i++)
        {
            ini[i]=lower_bound(a+1,a+len+1,ini[i])-a;
            inj[i]=lower_bound(a+1,a+len+1,inj[i])-a;
            int fx=find(ini[i]),fy=find(inj[i]);
            if(e[i]) 
            {
                if(fx!=fy)
                {
                    pre[fx]=fy;
                }
            }
        }
        //for(int i=1;i<=n;i++) cout<<ini[i]<<" "<<inj[i]<<endl;
        for(int i=1;i<=n;i++)
        {
            if(!e[i])
            {
                int fx=find(ini[i]),fy=find(inj[i]);
                if(fx==fy)
                {
                    flag=false;
                    break;
                }
            }
        }
        if(flag) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

例5.Graph Destruction

题目链接

题解

题目大意：给出一个无向图，无向图有n个点，m条边，依次删除1-n节点，输出每次删除后有多少个连通分量。我们知道并查集能很容易合并两个集合，但对于分裂操作很难，因此我们可以倒着考虑，从编号最大的点开始依次加点合并，离线倒着处理所有的答案然后输出就行了，我们每次加点实际判断的是编号比自己大的点的联通情况，而题目保证了\(a_i \lt b_i\)，因此建单向边即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int e[N], ne[N], head[N], idx = 0;
void add(int a, int b) {
    e[idx] = b;
    ne[idx] = head[a];
    head[a] = idx ++ ;
}
int n, m;
int res[N];
int pre[N];
void init(int n) {
    for(int i = 1; i <= n; i ++ ) pre[i] = i;
}

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

bool vis[N];
int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cin >> n >> m;
    init(n);
    memset(head, -1, sizeof(head));
    int tmp = 0;
    for(int i = 1; i <= m; i ++ ){
        int a, b;
        cin >> a >> b;
        add(a, b);
    }

    for(int i = n; i >= 1; i -- ) {
        tmp ++ ;
        for(int j = head[i]; j != -1; j = ne[j]) {
            int k = e[j];
            int fx = find(i);
            int fy = find(k);
            if(fx != fy)
                pre[fy] = fx, tmp -- ;
        }
        res[i - 1] = tmp;
    }

    for(int i = 1; i <= n; i ++ ) cout << res[i] << endl;
    return 0;
}

并查集 提高篇

概述

例1.格子游戏

题解

代码

例2.搭配购买

题解

代码

例3.银河英雄传说

题解

代码

例4.程序自动分析

题解

代码

例5.Graph Destruction

题解

代码

并查集提高篇