并查集

发表于2021-08-26更新于2021-10-10阅读次数

说！你跟他到底有没有关系？

好题题单

并查集

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

普通并查集

初始化

1
2
3
void init(){
    for(ll i=1;i<maxn;i++)  fa[i]=i;
}

路径压缩+查找

1
2
3
ll found(ll x){
    return fa[x]==x? x:fa[x]=found(fa[x]);
}

合并

1
2
ll fu=found(u),fv=found(v);
fa[fu]=fv;

基础题：
小希的迷宫
Wireless Network

带权并查集

做这类带权并查集的题目，解决并查集中两两的关系时，可以用向量的思想来做。只要保证路径压缩时，a+b=c，那么这道题就可以放心大胆的用向量加减法来处理权值了。

关于权值di[i]的初始化
对于权值di[i]，是需要初始化的，不过一般都是初始化为0，在定义其为全局变量时，就默认为0了，然后有时候就没写在代码里，但是要初始化的。

经典题型1

食物链
题意 a吃b，b吃c，c吃a，求假话数量
思路：带权并查集，比如一句话包含a和b，判断a，b是否在同一并查集内，不在则合并，在则判断这句话是否正确即可。关键在于权值的设置，
这个权值的设置十分巧妙，有向量那味，但我还是不知道为什么能这样
感觉这个权值的设置是个巧合，刚好能这么做。
踩坑：并查集合并一定是fa[fy]=fx，不能fa[y]=x;

1
2
3
4
5
6
7
8
9
10
ll found(ll x){
    if(fa[x]==x){
        return x;
    }
    else{
        ll fx=found(fa[x]);
        di[x]=(di[x]+di[fa[x]])%3;
        return fa[x]=fx;
    }
}

经典题型2

How Many Answers Are Wrong
TT 写一串数字，对 FF 不可见
FF 选择一个区间（会重复操作）， TT 把这个区间的和告诉 FF，然额，一些和是不正确的（好狠心的女生），所以，有一些答案是矛盾的，根据这些矛盾求出答案错误的个数。
注意两点：1。TT 给的一个 和 是正确的，如果它与之前给的 和 不矛盾。
2。FF 发现一个与之前矛盾的 和 之后，该 和 不再参与之后的分析，直接被抛弃了
思路 带权并查集，注意区间端点的设置，为了衔接,将[3,4]和[5,6]变为(2,4]。和(4,6]，这样子两边端点才能衔接上，才会在一个并查集里。

基础题：
Navigation Nightmare

灵活运用（带权并查集+hash）

本题解决：
1.hash后对并查集是否有影响
2.并查集中子父结点的大小关系对结果的影响

Parity game
题意：A有一段最大长度为1e9只含0和1的序列，B询问m次，m<5e3
每次询问[l,r]之间1的个数，A会告诉他是奇数个还是偶数个
但是A的回答可能是错误的，请判断A的回答从哪次开始矛盾

思路：
令a为子节点，b为父节点
用权值1表示a到b含奇数个1，用权值0表示a到b含偶数个1
虽然A的长度很长，有1e9，但B只询问m次,m<5e3，每次询问最多出现两个数字，所以最多1e4种数字
所以我们可以将数字长度离散化，我这里是采用hash的方式，这里不用担心hash后会对程序有影响
因为这里hash只是将原数字映射到另一个数字罢了，hash(x)与x就为同一个数字,完全不会有影响**，
这里进一步说明，hash(x)对程序是没影响的。
本来输入是x和y，是x到y，x是小于y的，路径压缩时默认子节点是小于父结点的，
**但存在一个问题,hash(x)可能会大于hash(y)，这样子会不会有影响呢？
经检验，这里x,y两者大小关系，对运算无影响。因为如果是x>y,那么我们将其反过来，就相当于-w了。
那么我们的运算结果还是一样的，即0+1=0-1 0+0=0-0 1+0=1-0 1+1=1-1(每次运算记得模2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<stdio.h>
#include<string.h>
#pragma comment(linker, "/STACK:102400000,102400000")//解决递归函数多次调用栈溢出问题
#define Debug(x) cout<<#x<<':'<<x<<endl
typedef long long ll;
#define INF 0x7fffffff//10^9级别，不到2^32
const ll maxn=1e5+11;


#define jump 10007//大概比mod小十倍
#define mod 100003//
ll lib[mod + 2];//lib[x]记得初始化为数据中不会出现的数，比如这里为-1
inline ll hash1(ll x){//返回x在哈希表中位置
    ll num = x;
    x = (x % mod + mod) % mod;//包含处理x为负数情况
    while (lib[x] != -1 && lib[x] != num) x = (x + jump) % mod;
    if (lib[x] == -1) {
        lib[x] = num;
    }
    return x; 
}


ll fa[maxn],di[maxn];
ll found(ll x){
    if(fa[x]==x){
        return x;
    }
    else{
        ll fx=found(fa[x]);
        di[x]=(di[x]+di[fa[x]])%2;
        return fa[x]=fx;
    }
}
void init(){
    memset(lib,-1,sizeof(lib));
    for(ll i=0;i<maxn;i++)  fa[i]=i;//---------------------------为0！！！
}
int main(){
    init();
    ll n,q;
    scanf("%lld%lld",&n,&q);
    ll ans=q,flag=0;
    for(ll i=1;i<=q;i++){
        ll u,v,w;
        char ar[11];
        scanf("%lld %lld %s",&u,&v,ar);
        if(flag==1)  continue;
        if(ar[0]=='e')  w=0;
        else  w=1;
        u-=1;
        u=hash1(u),v=hash1(v);
        ll fu=found(u),fv=found(v);
        if(fu==fv){
            if((w+di[v])%2==di[u])  ;
            else{
                flag=1;
                ans=i-1;
            }
        }
        else{
                fa[fv]=fu;
                di[fv]=(w+di[u]-di[v]+2)%2;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

灵活运用（贪心+并查集）

Supermarket
这里其实用贪心做，并查集只是用来作为工具，使得速度更加快。
这道题解决： 用并查集以O(1)找到最近的非空点
题意是买卖N件东西，每件东西都有个截止时间，在截止时间之前买都可以，而每个单位时间只能买一件。问最大获利。

思路如果购买不冲突，那么全部买下来就可以了。存在冲突，就需要取舍。显然在冲突的时候我们选择价格高的更优，如此就可以用贪心的算法。先将物品按照价格从高到底的顺序排列，购买一个就在时间点上做一个标记，只要不冲突就可以购买。 如何快速找到第一个不冲突的时间点呢，个人感觉使用并查集很好得解决了这个问题。用并查集维护当前节点最近的空闲点即可。每当一个位置i被选中就将当前节点的父节点更新为i-1，查询时只要父节点非零就证明有空闲位置，选中更新输出答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/*

*/
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN=10010;
int F[MAXN];
struct Node
{
    int p,d;
}node[MAXN];
bool cmp(Node a,Node b)//按p从大到小排序。d没有关系
{
    return a.p>b.p;
}
int find(int x)
{
    if(F[x]==-1)return x;
    return F[x]=find(F[x]);
}
int main()
{
    int n;
    while(scanf("%d",&n)==1)
    {
        memset(F,-1,sizeof(F));
        for(int i=0;i<n;i++)
          scanf("%d%d",&node[i].p,&node[i].d);
        sort(node,node+n,cmp);
        int ans=0;
        for(int i=0;i<n;i++)
        {
            int t=find(node[i].d);
            if(t>0)
            {
                ans+=node[i].p;
                F[t]=t-1;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

灵活运用（连通块，并查集）

path queries
题意 有m次询问，每次询问一个数字q，问以u,v为端点的路径的最大值不超过q的u，v对有多少个
思路：考试时想了很久，由于没有考虑过连通块，之前也没碰到过。。
导致一直做不出来，就是感觉能做，但一直没做出来
首先我们要知道，对于两个不相连的连通块，如果将他俩连起来，
是需要一条边将这两者连起来的，如果这条边是这两个连通块的所有边的最大值,那么以这条边为最大值的u,v就有size[a]*size[b]个。
那么我们将所有边按从小到大排序，这样子保证新加入的边是目前边的最大值，即两个连通块的最大值,连通块则用并查集处理。

贴一个极简风格的大佬代码，真的是绝绝子
原大佬代码链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,m,res[N],ans,f[N],sz[N];
vector<pair<int,int> > v[N];
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
signed main(){
	cin>>n>>m;
	for(int i=1,a,b,c;i<n;i++)	scanf("%lld %lld %lld",&a,&b,&c),v[c].push_back({a,b});
//在for里面就把a,b,c给定义了
//这里用vector存边不得不说很巧妙，v[c]代表以c为权值的边集合,
//再用pair存边的两个端点，不得不说这数据结构设计得十分牛掰
	for(int i=1;i<=n;i++)	f[i]=i,sz[i]=1;
	for(int i=1;i<=2e5;i++){
		for(auto j:v[i]){//这个我也表示学到了学到了
			int x=find(j.first),y=find(j.second);
			ans+=sz[x]*sz[y];	f[x]=y,sz[y]+=sz[x];
		}
		res[i]=ans;
	}
	for(int i=1,x;i<=m;i++)	scanf("%lld",&x),printf("%lld ",res[x]);
	//在for里面定义变量x，这样子就不用在scanf前面加一行x的定义了
	//学到了学到了
	return 0;
}

带权并查集好题

Jumping Monkey HDU - 7136

题意：一个n<1e5的树，每个点有个权值w，从u点能走到v点当且仅当v是uv这条路径上的最大权值，求每个点可以到达的点的个数。

点击查看思路 
  




也可以用带权并查集维护这个过程，当按点权从小到大枚举结点u,并将u作为所有与u相连的（已经枚举过的）连通块的根时，
我们让fa[ fv ]=fu,d[ fv ]=1;并查集合并时则使d[ x ]=d[ x ]+d[ fa[ x ] ],和树的深度是一个意思。


  

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/*
* @Author: Marhoosh
* @Date:   2021-07-22 10:27:29
* @Last Modified by:   Marhoosh
* @Last Modified time: 2021-10-10 19:04:19
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
typedef pair<ll,ll> P;
const ll maxn=2e5+11;
ll head[maxn],to[maxn],nex[maxn],var[maxn],d[maxn],fa[maxn];
ll tmp,n;
P po[maxn];
void add(ll u,ll v){
    to[tmp]=v;nex[tmp]=head[u];head[u]=tmp++;
}
ll found(ll x){
    if(fa[x]==x){
        return x;
    }
    ll t=found(fa[x]);
    d[x]=d[x]+d[fa[x]];
    return fa[x]=t;
}
int main(){
    ll ca;scanf("%lld",&ca);
    while(ca--){
        tmp=1;
        scanf("%lld",&n);
        for(ll i=1;i<=n;i++){
            head[i]=0;fa[i]=i;d[i]=0;
        }
        for(ll i=1;i<=n-1;i++){
            ll u,v;scanf("%lld%lld",&u,&v);
            add(u,v);add(v,u);
        }
        for(ll i=1;i<=n;i++){
            scanf("%lld",&var[i]);
            po[i]={var[i],i};
        }
        sort(po+1,po+1+n);
        for(ll i=1;i<=n;i++){
            ll u=po[i].second,w=po[i].first;
            for(ll j=head[u];j;j=nex[j]){
                ll v=to[j];
                if(var[v]>w)  continue;
                ll fu=found(u),fv=found(v);
                fa[fv]=fu;d[fv]=1;
            }
        }
        for(ll i=1;i<=n;i++){
            found(i);
            printf("%lld\n",d[i]+1);
        }
    }
    return 0;
}