自动搬运

查看原文

来自洛谷，原作者为

	Cypher_404 答应你们，1k 粉女装

搬运于2025-08-24 22:59:56，当前版本为作者最后更新于2024-07-02 19:57:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解：P10648 [NordicOI 2023] Island Alliances

题意分析

• 有 $n$ 个数字，代表 $n$ 座岛屿。
• 有 $m$ 个点对 $x_i,y_i$ 代表两个互相敌对的岛屿。
• 有 $q$ 个点对 $x_i,y_i$ 代表询问两个岛屿是否能够联盟，联盟的条件是：它们互相不敌对且它们互相联盟的岛屿也互相不敌对。
• 如果决定联盟，那么就联盟并且输出 APPROVE，不联盟则输出 REFUSE 并且不联盟。

思路分析

看到点对之间的合并，想到并查集。

直接开码。

后来发现：无法判断两个敌对的点对是否在一个并查集内，于是添加了链式前向星用于存储敌对关系，合并时直接将信息加入到最上面的祖宗。且将并查集合并。

再后来发现：如果直接合并会 TLE 很多，想到启发式合并。每次将并查集内数字数量更小的合并给数量更多的。

还是 TLE 了 $2$ 个测试点。

想办法卡卡常数？

加入了快读，输出使用了 puts。

还是 TLE。

再想想办法，似乎可以直接使用 set 进行存储，保证了敌对的单一性，并且在 set 中只放入最上面的祖宗，减少放入的元素，减少时间复杂度。

终于，在尝试了很多次以后 AC 了。

Code

第一版使用链式前向星存的，T 了 $2$ 个点。

#include<bits/stdc++.h>
using namespace std;
int fa[100010];
int findfa(int x)//并查集模板
{
	return (fa[x]==x)?x:(x=fa[x]=findfa(fa[x]));
}
template< typename T > inline void read(T &x)//快读
{
    char c=getchar();x=0;int f=0;
    for(;!isdigit(c);c=getchar()) f|=(c=='-');
    for(;isdigit(c);c=getchar()) x=((x<<3)+(x<<1)+(c^48));
    x=f?-x:x;
}
int head[100010],tot;
struct edge
{
	int v,net;
}e[20000010];
int size[100010];
void addedge(int u,int v)
{
	tot++;
	e[tot].v=v;
	e[tot].net=head[u];
	head[u]=tot;
}//链式前向星板子，不多赘述
unordered_map<int,int>vis;//用于防止多次加入敌对关系
int n,m,q;
int main()
{
	
	read(n);
	for(int i=1;i<=n;i++)
	{
		fa[i]=i;
		size[i]=1;
	}//初始化并查集
	read(m);
	read(q);
	while(m--)
	{
		int x,y;
		read(x);
		read(y);
		addedge(x,y);
		addedge(y,x);
	}//输入敌对关系
	while(q--)
	{
		int x,y;
		read(x);
		read(y);
		int mlf=findfa(x);//找到要合并的点对的两个祖先
		int hcy=findfa(y);
		if(size[mlf]>=size[hcy])//启发式合并
		{
			for(int i=head[mlf];i;i=e[i].net)//判断是否是敌对关系
			{
				if(findfa(e[i].v)==hcy)
				{
					puts("REFUSE");//直接拒绝
					goto fuck;
				}
			}
			vis.clear();//清空合并的标记
			for(int i=head[hcy];i;i=e[i].net)
			{
				if(vis[findfa(e[i].v)]==1)//已经合并过了，用于节省空间
				{
					continue;
				}
				vis[findfa(e[i].v)]=1;
				addedge(e[i].v,mlf);//合并
				addedge(mlf,e[i].v);
			}
			fa[hcy]=mlf;
			size[mlf]+=size[hcy];//累加size
		}
		else//同上，不多赘述
		{
			for(int i=head[hcy];i;i=e[i].net)
			{
				if(findfa(e[i].v)==mlf)
				{
					puts("REFUSE");
					goto fuck;
				}
			}
			vis.clear();
			for(int i=head[mlf];i;i=e[i].net)
			{
				if(vis[findfa(e[i].v)]==1)
				{
					continue;
				}
				vis[findfa(e[i].v)]=1;
				addedge(e[i].v,hcy);
				addedge(hcy,e[i].v);
			}
			fa[mlf]=hcy;
			size[hcy]+=size[mlf];
		}
		puts("APPROVE");
		fuck:;
	}
	return 0;
}

第二版，AC 了的。

#include<bits/stdc++.h>
using namespace std;
int fa[100010];
int findfa(int x)
{
	return (fa[x]==x)?x:(x=fa[x]=findfa(fa[x]));
}//并查集模板
template< typename T > inline void read(T &x)//快读
{
    char c=getchar();x=0;int f=0;
    for(;!isdigit(c);c=getchar()) f|=(c=='-');
    for(;isdigit(c);c=getchar()) x=((x<<3)+(x<<1)+(c^48));
    x=f?-x:x;
}
int size[100010];
set<int>vis[100010];//用于存储敌对关系
int n,m,q;
int main()
{
	read(n);
	for(int i=0;i<=n;i++)
	{
		fa[i]=i;
		size[i]=1;
	}//初始化并查集
	read(m);
	read(q);
	while(m--)
	{
		int x,y;
		read(x);
		read(y);//存入敌对的点对
		vis[x].insert(y);
		vis[y].insert(x);
	}
	while(q--)
	{
		int x,y;
		read(x);
		read(y);
		int mlf=findfa(x);//找到点对的祖先
		int hcy=findfa(y);
		if(size[mlf]<size[hcy])//启发式合并
		{
			if(vis[mlf].find(hcy)!=vis[mlf].end())//如果在敌对的点对中找到了对方，说明不会联盟
			{
				puts("REFUSE");
				goto fuck;
			}
			for (auto i : vis[mlf])//遍历set
			{
				vis[hcy].insert(i);//联盟
				vis[i].erase(mlf);//节省空间
				vis[i].insert(hcy);//联盟
			}
			fa[mlf]=hcy;//合并并查集
			size[hcy]+=size[mlf];//累加size
		}
		else//同上
		{
			if(vis[hcy].find(mlf)!=vis[hcy].end())
			{
				puts("REFUSE");
				goto fuck;
			}
			for (auto i : vis[hcy])
			{
				vis[mlf].insert(i);
				vis[i].erase(hcy);
				vis[i].insert(mlf);
			}
			fa[hcy]=mlf;
			size[mlf]+=size[hcy];
		}
		puts("APPROVE");
		fuck:;
	}
	return 0;
}

整体思路还是很好理解的，可以多看看。