首页 > 其他分享 >【寻迹#4】并查集

【寻迹#4】并查集

时间：2024-10-28 15:31:44浏览次数：1  
标签：int 寻迹 查集 fa init inline 节点

并查集

一、并查集

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。

顾名思义，并查集支持两种操作：

  • 合并（Union）：合并两个元素所属集合（合并对应的树）
  • 查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合

1.初始化

所有的元素在初始时默认在单独的集合内，表示为只有一颗根节点的树， 方便起见，我们将根节点的父亲设为自己。

2.查询

我们需要沿着树向上移动，直到找到根节点。

这个过程中可以采用路径压缩，即并查集维护的是很多个集合，对树的形状并没有要求，可以直接将所有节点连接到树的根节点。

3.合并

要合并两棵树，我们只需要将一棵树的根节点连到另一棵树的根节点。

3.1启发式合并

合并时，选择哪棵树的根节点作为新树的根节点会影响未来操作的复杂度。我们可以将节点较少或深度较小的树连到另一棵，以免发生退化。

即每次合并前比较一下树的节点数。

4.删除

要删除一个叶子节点，我们可以将其父亲设为自己。为了保证要删除的元素都是叶子，我们可以预先为每个节点制作副本，并将其副本作为父亲。

void erase(int x) 
{
	int xx=Find(x);
    --size[xx];
    fa[x] = x;
 }

5.移动

与删除类似，通过以副本作为父亲，保证要移动的元素都是叶子。

void move(int x,int y) 
{
	int fx=Find(x);int fy=Find(y);
	if(fx==fy) return;
	fa[x]=fy;
	--size[fx];++size[fy];
}

6.带权并查集

我们还可以在并查集的边上定义某种权值、以及这种权值在路径压缩时产生的运算，从而解决更多的问题。

7.其他应用

最小生成树算法中的 Kruskal 和 最近公共祖先中的 Tarjan 算法是基于并查集的算法。

二、题单

1.修复公路

传送门

思路：最小生成树模板题，主要体现一下并查集的应用

代码：

#include<bits/stdc++.h>
using namespace std;
#define N 1050
#define M 100050
struct E{ int x,y,z; }edge[M];
int n,m;
int fa[N];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') { if(ch=='-')f=-1;ch=getchar(); }
	while(ch>='0'&&ch<='9') { x=x*10+ch-48;ch=getchar(); }
	return x*f;
}
inline void init(int n) { for(int i=1;i<=n;i++) fa[i]=i; }
inline bool cmp(E a, E b) { return a.z<b.z; }
int Find(int x)
{
	if(x==fa[x]) return x;
	return fa[x]=Find(fa[x]);
}
inline int kruskal()
{
	int num=0,maxx=0;
	for(int i=1;i<=m;i++)
	{
		int x=edge[i].x;int y=edge[i].y;int z=edge[i].z;
		x=Find(x);y=Find(y);
		if(x==y) continue;
		fa[x]=y;num++;
		maxx=max(maxx,z);
		if(num==n-1) break;
	}
	if(num==n-1) return maxx;
	return -1;
}
int main()
{
	n=read();m=read();
	init(n);
	for(int i=1;i<=m;i++) { edge[i].x=read();edge[i].y=read();edge[i].z=read(); }
	sort(edge+1,edge+1+m,cmp);
	cout<<kruskal()<<endl;
	return 0;
}

2.奶酪

传送门

思路：

用并查集维护。

对于每一个点，先判断是否与上表面或下表面联通，

再遍历之前的点，把所有相交的点（球）扔到一个集合里，

最后遍历上表面和下表面的点，看看能否找到一条通道。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 10500
int T,n,cnt1,cnt2;
ll h,r;
int fa[N],f1[N],f2[N];
struct node{ ll x,y,z; }a[N];
inline void init(int n) 
{
	memset(f1,0,sizeof(f1));memset(f2,0,sizeof(f2));
	cnt1=cnt2=0;
	for(int i=1;i<=n;i++) fa[i]=i; 
}
inline ll dist(ll x1,ll y1,ll z1,ll x2,ll y2,ll z2) { return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2); } 
int Find(int x) 
{
	if(fa[x]==x) return x;
	return fa[x]=Find(fa[x]); 
}
int main()
{
	cin>>T;
	while(T--)
	{
		cin>>n;
		cin>>h>>r;
		init(n);
		for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y>>a[i].z;
		for(int i=1;i<=n;i++)
		{
			ll x1=a[i].x;ll y1=a[i].y;ll z1=a[i].z;
			if(z1+r>=h) f1[++cnt1]=i;
			if(z1-r<=0) f2[++cnt2]=i;
			for(int j=1;j<=i;j++)
			{
				ll x2=a[j].x;ll y2=a[j].y;ll z2=a[j].z;
				if((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)>4*r*r) continue;
				if(dist(x1,y1,z1,x2,y2,z2)<=4*r*r)
				{
					int fax=Find(i);int fay=Find(j);
					if(fax!=fay) fa[fax]=fay;
				}
			}
		}
		int book=0;
		for(int i=1;i<=cnt1;i++)
			for(int j=1;j<=cnt2;j++) if(Find(f1[i])==Find(f2[j])) book=1;
		if(book) puts("Yes");
		else puts("No");
	}
	return 0;
}

3.程序自动分析

传送门

思路：

其实是一道比较好想的并查集的问题，

考虑先把所有约束条件按照 \(e\) 排序，

如果 \(e=1\) 就把两个点连起来，

如果 \(e=0\) 时发现这两个点已经连起来了，那就可以直接认为无法满足，

但本题的关键在于，数据过大，直接开数组可能会越界，所以需要离散化。

代码：

#include<bits/stdc++.h>
using namespace std;
#define N 200050
int T;
struct P{ int x,y,z; }a[N];
int temp[N],fa[N];
int n,m;
inline void init(int n) { for(int i=1;i<=n;i++) fa[i]=i; }
int Find(int x)
{
	if(fa[x]==x) { return x; }
	return fa[x]=Find(fa[x]);
}
inline void Link(int x,int y) { fa[Find(x)]=Find(y); }
inline int check(int x,int y) { return Find(x)==Find(y); }
inline bool cmp(P a,P b) { return a.z>b.z; }
int main()
{
	cin>>T;
	while(T--)
	{
		int tot=0;
		cin>>m;
		for(int i=1;i<=m;i++)
		{
			cin>>a[i].x>>a[i].y>>a[i].z;
			temp[++tot]=a[i].x;temp[++tot]=a[i].y;
		}
		sort(temp+1,temp+1+tot);
		n=unique(temp+1,temp+1+tot)-(temp+1);
		for(int i=1;i<=m;i++)
		{
			a[i].x=lower_bound(temp+1,temp+1+n,a[i].x)-temp;
			a[i].y=lower_bound(temp+1,temp+1+n,a[i].y)-temp;
		}
		init(n);
		sort(a+1,a+1+m,cmp);
		int book=0;
		for(int i=1;i<=m;i++)
		{
			if(a[i].z) Link(a[i].x,a[i].y);
			else if(check(a[i].x,a[i].y)) { book=1;break; }
		}
		if(book) puts("NO");
		else puts("YES");
	}
	return 0;
}

4.关押罪犯

传送门

思路：

首先想到将事件的影响力排序，这样发生的第一件冲突即为最后的答案，

那么从上到下考虑没一起事件，肯定是优先不让它发生，即把两个罪犯分到两个监狱中去，

重复此操作，直到有两个罪犯被迫相遇产生冲突。

将并查集开为两倍大小，设两个罪犯为 \(x\) 和 \(y\) ，

如果当前 \(x\) 与 \(y\) 已经处于一个集合中，则无法避免冲突，直接输出答案即可，

否则的话将 \(x\) 与 \(y+n\) 放在一个集合中， \(y\) 与 \(x+n\) 放在一个集合中。

代码：

#include<bits/stdc++.h>
using namespace std;
#define M 100050
#define N 20050
struct I{ int a,b,c; }inc[M];
int fa[N*2];
int n,m,book;
inline bool cmp(I x,I y) { return x.c>y.c; }
inline void init(int n) { for(int i=1;i<=2*n;i++) fa[i]=i; }
int Find(int x)
{
	if(fa[x]==x) return x;
	return fa[x]=Find(fa[x]);
}
inline int check(int x,int y) { return Find(x)==Find(y); }
inline void Link(int x,int y) { fa[Find(x)]=Find(y); }
int main()
{
	cin>>n>>m;
	init(n);
	for(int i=1;i<=m;i++) cin>>inc[i].a>>inc[i].b>>inc[i].c;
	sort(inc+1,inc+1+m,cmp);
	for(int i=1;i<=m;i++)
	{
		int x=inc[i].a;int y=inc[i].b;int z=inc[i].c;
		if(check(x,y)) { book=1;cout<<z<<endl;break; }
		Link(x,y+n);
		Link(y,x+n);
	}
	if(!book) puts("0");
	return 0;
}

5.食物链

传送门

思路：

与上一道关押罪犯类似，

考虑开三个集合 \(A,B,C\) ，每个集合中都有 \(1\sim n\) 的点，不妨假设 \(A\) 吃 \(B\) ， \(B\) 吃 \(C\) ， \(C\) 吃 \(A\) ，

先考虑并查集的维护，判断假话我们后面再说，

当读取到是 \(x\) 和 \(y\) 同类的指令时，要将 \(A,B,C\) 集合中的 \(x\) 和 \(y\) 点都连接起来，因为我们并不知道 \(x\) 和 \(y\) 具体属于哪一个集合，

当读取到 \(x\) 吃 \(y\) 的指令时，我们要连接 \(A\) 中的 \(x\) 和 \(B\) 中的 \(y\) ， \(B\) 中的 \(x\) 和 \(C\) 中的 \(y\) ，依此类推…

再来说如何判断真假，

当读取到 \(x\) 和 \(y\) 是同类的指令时，我们只需要判断 \(x\) 和 \(y\) 是否有吃或者被吃的关系，如果有那么就是假话

当读取到 \(x\) 吃 \(y\) 的指令时，要先判断如果 \(x=y\) ，那么这句话是假话；如果\(x\) 和 \(y\) 是同类，那么这句话也是假话；如果 \(y\) 吃 \(x\) ，那么这句话也是假话

最后要特判如果有大于 \(n\) 的点也要算假话。

代码：

#include<bits/stdc++.h>
using namespace std;
#define N 50050
int n,k;
int cnt;
int fa[N*3];
inline void init(int n) { for(int i=1;i<=n;i++) fa[i]=i; }
int Find(int x)
{
	if(fa[x]==x) return x;
	return fa[x]=Find(fa[x]);
}
inline void Link(int x,int y) { fa[Find(x)]=Find(y); }
inline int check(int x,int y) { return Find(x)==Find(y); }
int main()
{
	cin>>n>>k;
	init(3*n);
	int Type,x,y;
	for(int i=1;i<=k;i++)
	{
		cin>>Type>>x>>y;
		if(x>n||y>n){ cnt++;continue; }
		if(Type==1)
		{
			if(check(x,y+n)||check(x,y+2*n)) { cnt++;continue; }
//第一个括号：(x,y+n) or (x+n,y+2*n) or (x+2*n,y)三个都可以 第二个括号：(x+n,y) or (x+2*n,y+n) or (x,y+2*n) 三个都可以
			Link(x,y);
			Link(x+n,y+n);
			Link(x+2*n,y+2*n);
		}
		else
		{
			if(x==y) { cnt++;continue; } 
			if(check(x,y)||check(y,x+n)) { cnt++;continue; } //check(y,x+n) or check(y+n,x+2*n) or check(y+2*n,x) 三个都可以 
			Link(x,y+n);
			Link(x+n,y+2*n);
			Link(x+2*n,y);
		}
	}
	cout<<cnt<<endl;
	return 0;
}

6.星球大战

传送门

思路：

考虑我们不好模拟点被炸毁的过程，

所以想到反过来，模拟把所有点连接起来的过程，比较难想，但是比较好实现。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
#define M 400050
#define N 400050
int ver[M],Next[M],head[N],tot=-1;
int brok[N],vis[N],ans[N],fa[N];
int cnt;
inline void init(int n) { for(int i=1;i<=n;i++) fa[i]=i; }
inline void ADD(int x,int y)
{
	ver[++tot]=y;
	Next[tot]=head[x];
	head[x]=tot;
}
int Find(int x)
{
	if(fa[x]==x) return x;
	return fa[x]=Find(fa[x]);
}
inline void Link(int x,int y) { fa[Find(x)]=Find(y); }
int main()
{
	cin>>n>>m;
	init(n);
	memset(head,-1,sizeof(head));
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		ADD(x,y);ADD(y,x);
	}
	cin>>k;
	for(int i=1;i<=k;i++)
	{
		int x;
		cin>>x;
		brok[i]=x;
		vis[x]=1;
	}
	cnt=n-k;
	for(int x=0;x<n;x++)
	{
		for(int i=head[x];~i;i=Next[i])
		{
			int y=ver[i];
			if(!vis[x]&&!vis[y]) 
			{
				int xx=Find(x);int yy=Find(y);
				if(xx!=yy) {Link(xx,yy);cnt--;}
			}
		}
	}
	ans[k+1]=cnt;
	for(int j=k;j>=1;j--)
	{
		int x;
		x=brok[j];
		cnt++;
		vis[x]=0;
		for(int i=head[x];~i;i=Next[i])
		{
			int y=ver[i];
			if(!vis[y])
			{
				int xx=Find(x);int yy=Find(y);
				if(xx!=yy) { Link(xx,yy);cnt--; }
			}
		}
		ans[j]=cnt;
	}
	for(int i=1;i<=k+1;i++) cout<<ans[i]<<endl;
	return 0; 
}

7.银河英雄传说

传送门

思路：

带权并查集的应用，除了正常的并查集之外，

我们需要维护每一个节点下的战舰数，以及一棵树下任何一个节点到它的最高父节点的距离（战舰数），

然后最后减一减答案就出来了。

代码：

#include<bits/stdc++.h>
using namespace std;
#define N 30050
int fa[N],size[N],dist[N];//size[i] 维护的是编号为 i 的战舰后面有多少战舰;
						  //dist[i]表示的是 i 到 fa[i] or Find(i) 的战舰数
int T;
char ch;
int x,y,ans;
inline void init()
{
	for(int i=1;i<=N;i++) fa[i]=i;
	for(int i=1;i<=N;i++) size[i]=1;
}
int Find(int x)
{
	if(fa[x]==x) return x; 
	int root=Find(fa[x]);
	dist[x]+=dist[fa[x]];
	return fa[x]=root;
}
inline void Link(int x,int y)
{
	x=Find(x);y=Find(y);
	fa[x]=y;
	dist[x]=size[y];
	size[y]+=size[x];
}
inline int check(int x,int y) { return Find(x)==Find(y); }
int main()
{
	init();
	cin>>T;
	while(T--)
	{
		cin>>ch>>x>>y;
		if(ch=='M') Link(x,y);
		else if(!(check(x,y))) puts("-1");
		else
		{
			ans=abs(dist[x]-dist[y])-1;
			cout<<ans<<endl; 
		}
	}
	return 0;
}

8.MooTube

传送门

思路：

发现题目没有强制在线，所以可以离线操作，

于是想到可以对边的信息和查询的信息进行从大到小的排序，

对于每一次询问，只考虑建立边权比 \(k_i\) 大的边（因为小的没用，不会贡献此次询问的答案），

并且，每一次询问只需要在已有的图上继续连边即可，复杂度虽然是 \(O(nT)\) ，但是显然跑不满，

每次连边用一个数组维护连通块中节点的数量，最后减去自己即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define N 100050
struct edge{ int x,y,z; }a[N];
struct query{ int k,v,num; }q[N];
int n,T;
int fa[N],cnt[N],ans[N];
inline bool cmp1(edge a,edge b) { return a.z>b.z; }
inline bool cmp2(query a,query b) { return a.k>b.k; }
inline void init()
{
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=n;i++) cnt[i]=1;
}
int Find(int x)
{
	if(fa[x]==x) return x;
	return fa[x]=Find(fa[x]);
}
inline void Link(int x,int y)
{
	int xx=Find(x);int yy=Find(y);
	if(xx!=yy)
	{
		fa[xx]=yy;
		cnt[yy]+=cnt[xx];
	} 
}
int main()
{
	cin>>n>>T;
	init();
	for(int i=1;i<n;i++) cin>>a[i].x>>a[i].y>>a[i].z;
	for(int i=1;i<=T;i++) 
	{
		cin>>q[i].k>>q[i].v;
		q[i].num=i;
	}
	sort(a+1,a+1+(n-1),cmp1);
	sort(q+1,q+1+T,cmp2);
	int pos=1;
	for(int i=1;i<=T;i++)
	{
		for(int j=pos;j<n;j++)
		{
			if(a[j].z<q[i].k) break;
			Link(a[j].x,a[j].y);
			pos++;
		}
		ans[q[i].num]=cnt[Find(q[i].v)]-1;
	}
	for(int i=1;i<=T;i++) cout<<ans[i]<<endl;
	return 0;
}

标签：int,寻迹,查集,fa,init,inline,节点
From： https://www.cnblogs.com/Cybersites/p/18510754

相关文章

  • 并查集
    并查集并查集是一种数据结构，它主要处理一些不相交集合的合并问题。一些常见的用途有求连通子图、最小生成树Kruskal算法和求公共祖先等。并查集的主要操作有：初始化Init查询Find合并Union初始化Init()voidInit(intn){vector<int>father(n+1);//创......
  • 经典算法思想--并查集
    前言 （最近在学习Java，所有函数都是用Java语言来书写的）前言部分是一些前提储备知识在并查集（Union-Find）数据结构中，rank（中文称为“秩”）是用来表示树的高度或深度的一种辅助信息。它的主要作用是优化合并操作，以保持并查集的结构尽可能扁平，从而提高查询效率。秩的具体定义......
  • CF771A. Bear and Friendship Condition 题解 并查集
    题目链接：https://codeforces.com/problemset/problem/771/A视频讲解：https://www.bilibili.com/video/BV1tZ1FYPELp/?p=6题目大意：判断一个无向图中的每个连通块是否都是一个完全图。首先我们可以用并查集维护每个连通块的大小。其次，我们可以开一个\(cnt_i\)表示以节点\(i\)......
  • CF1139C. Edgy Trees 题解 并查集
    题目链接：https://codeforces.com/problemset/problem/1139/C视频讲解：https://www.bilibili.com/video/BV1tZ1FYPELp?p=3我们可以求总方案数-不满足条件的方案数。设一个不包含黑色边的极大连通块的大小为\(sz_i\)。则答案为\[n^k-\sum\{sz_i^k\}\]示例程序：#include......
  • CF1800E2. Unforgivable Curse (hard version) 题解 并查集
    题目链接：https://codeforces.com/contest/1800/problem/E2视频讲解：https://www.bilibili.com/video/BV1tZ1FYPELp?p=2把下标\(i\)对应到图中编号为\(i\)的节点。节点\(i\)和\(i+k\)之间连一条边，节点\(i\)和\(i+k+1\)之间也连一条边。同一个连通块里的节点对应的字......
  • 新高一暑假第一期集训恢复性训练【数据结构-晚测】（并查集）（补）
    新高一暑假第一期集训恢复性训练【数据结构-晚测】（并查集）（补）[CF1290C]PrefixEnlightment带权扩展域并查集。任意三个子集的交集为空集，显然，一个点最多只能在两个集合中出现，这样所有集合的大小之和是\(\Theta(n)\)的。一个在两个集合中出现的点ii相当于连接了\(2\)个集合......
  • 带权并查集 学习笔记
    顾名思义，就是并查集带权值。在路径压缩的时候，我们还要维护权值应该怎么办呢？关联题目：P1196[NOI2002]银河英雄传说。我们对于一个舰队维护一个\(fr\)表示到头部的距离，\(cnt\)表示该舰队的战舰数量。那么每一次合并时，先进行路径压缩，找到父亲，在将父亲的权值传下来即可。因为每......
  • 新高一暑假第一期集训恢复性训练【数据结构-并查集】（补）
    新高一暑假第一期集训恢复性训练【数据结构-并查集】（补）C.[POJ1417]TrueLiars先将题目中的好人和坏人转换一下，也即是如果\(x\)说\(y\)是好人，则他们两属于同一组，反之则不属于同一组。然后我们可以想到带权的并查集，用\(val_x\)代表\(x\)与其父节点的关系，当\(val_x\)......
  • 学习笔记 - 并查集
    本人实力不济，如有错误或建议及补充，请指出1.定义并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。顾名思义，并查集支持两种操作：合并（Union）：合并两个元素所属集合（合并对应的树）查询（Find）：查询某个元素所属集合（查询......
  • Soso 的并查集写挂了
    题面似乎有原题,但是很偏挂个pdf题面下载算法暴力很显然,只需要在并查集维护时稍微加上一点细节#include<cstdio>usingnamespacestd;intn,m,fa[500010],a[500010];longlongans=0;intfind(intx){ ans+=a[x]; ans%=998244353; if(fa[x]==x)returnx; r......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99