题解：P10648 [NordicOI 2023] Island Alliances
Cypher_404 · · 题解
题解：P10648 [NordicOI 2023] Island Alliances
题意分析
- 有
n 个数字，代表n 座岛屿。 - 有
m 个点对x_i,y_i 代表两个互相敌对的岛屿。 - 有
q 个点对x_i,y_i 代表询问两个岛屿是否能够联盟，联盟的条件是：它们互相不敌对且它们互相联盟的岛屿也互相不敌对。 - 如果决定联盟，那么就联盟并且输出 APPROVE，不联盟则输出 REFUSE 并且不联盟。
思路分析
看到点对之间的合并，想到并查集。
直接开码。
后来发现：无法判断两个敌对的点对是否在一个并查集内，于是添加了链式前向星用于存储敌对关系，合并时直接将信息加入到最上面的祖宗。且将并查集合并。
再后来发现：如果直接合并会 TLE 很多，想到启发式合并。每次将并查集内数字数量更小的合并给数量更多的。
还是 TLE 了
想办法卡卡常数？
加入了快读，输出使用了 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;
}整体思路还是很好理解的，可以多看看。