题意
给定 \(n\) 个数,保证 \(n \mid 3\),要将这 \(n\) 个数分配到 \(\dfrac{n}{3}\) 个三元组,有 \(m\) 个要求 \(a,b\),每个要求表示 \(a,b\) 要在同一个三元组里,求最后的分组,若无解则输出 -1。
正文
♦准备知识:并查集
♦最坏时间复杂度:\(\mathcal{O}(n+m)\)
我们可以利用并查集来处理两个人要在同一组的情况,下面是并查集板子(在下文中,并查集中的每一个区块被称为一棵树):
//板子,不做解释
int ufs[20000];
void init(){
for(int i=1;i<=n;i++) ufs[i]=i;
}
int fd(int x){
if(ufs[x]==x) return x;
return ufs[x]=fd(ufs[x]);
}
void uoin(int x,int y){
ufs[fd(x)]=fd(y);
}
但这只是第一步,根据题意,当并查集中存在超过 3 个结点的树,那么这是绝对无解的。那么这要怎么弄呢?我们可以开一个 vector
\(S_{i,j}\) 来储存以 \(i\) 为根节点的树的节点数 \(j\),因此我们得到以下代码:
#define pb push_back
vector<vector<int>> s(20000);
for(int i=1;i<=n;i++) s[fd(i)].pb(i);//插入节点
for(auto &i: s)//判断是否有超过3个节点的树
if(i.size()>3) cout<<-1,exit(0);
我们还要考虑如何分组,这是蒟蒻的思路,仅供大佬借鉴。经过上面的无解判定,可以保证并查集中剩下的树只有 1 至 3 个节点。而三个节点的树正好是所需的三元组,无需再分。将有 1 个节点和有 2 个节点的树分别装入不同的 vector
\(sj,so\),可以很好地发现,我们只要将 \(sj\) 中的某一项和 \(so\) 的某一项合并,即可得到一个新的三元组(因为两棵树没有任何要求)。
于是有下面的代码:
vector<vector<int>> sj,so,ans;
for(auto &i: s)
if(i.size()==3) ans.pb(i);//3个节点的树
else if(i.size()==2) so.pb(i);//2个节点的树
else if(i.size()==1) sj.pb(i);//1个节点的树
while(!sj.empty()&&!so.empty())
sj.front().insert(sj.front().begin(),//将so首项插入sj首项末
so.front().begin(),so.front().end()),
so.erase(so.begin()),//删去so首项
ans.pb(sj.front()),//将合并后的sj插入ans末
sj.erase(sj.begin());//删去sj首项
但,这就完了吗?不!
可以看一下第一个样例:3 0
,没错,如果按照上面的代码,所有节点都会被放入 \(sj\) 中而无法合并,因此我们还要在 \(sj\) 和 \(so\) 合并完后,若 \(sj\) 还有残余且数量大于 3,我们可以每三项每三项合并,于是有:
while(!sj.empty()&&sj.size()>=3){
int a,b,c;
auto i=sj.begin();//得到sj首项
a=i->front(),i=sj.erase(i),//依次将sj的前三项赋值给a,b,c
b=i->front(),i=sj.erase(i),
c=i->front(),i=sj.erase(i);
ans.push_back({a,b,c});
}
当然,如果谨慎些的话,我们还要加上 \(sj\) 和 \(so\) 的判断,若仍有残余,则无解。(为什么不合并 \(so\)?因为它合并就超过 3 个节点了。)
if(so.size()>0) cout<<-1,exit(0);
if(sj.size()>0) cout<<-1,exit(0);
最后是输出。
for(auto &i: ans){
for(auto &j: i)
cout<<j<<' ';
cout<<'\n';
}
完整 CODE:
//不注解,前面已做讲解,不懂评论区问/私聊
#include<iostream>
#include<vector>
#define pb push_back
using namespace std;
int ufs[20000],n,m;
vector<vector<int>> s(20000),sj,so,ans;
void init(){
for(int i=1;i<=n;i++) ufs[i]=i;
}
int fd(int x){
if(ufs[x]==x) return x;
return ufs[x]=fd(ufs[x]);
}
void uoin(int x,int y){
ufs[fd(x)]=fd(y);
}
int main(){
cin>>n>>m,init();
int a,b;
for(int i=1;i<=m;i++) cin>>a>>b,uoin(a,b);
for(int i=1;i<=n;i++) s[fd(i)].pb(i);
for(auto &i: s)
if(i.size()>3) cout<<-1,exit(0);
else if(i.size()==3) ans.pb(i);
else if(i.size()==2) so.pb(i);
else if(i.size()==1) sj.pb(i);
while(!sj.empty()&&!so.empty())
sj.front().insert(sj.front().begin(),
so.front().begin(),so.front().end()),
so.erase(so.begin()),
ans.pb(sj.front()),
sj.erase(sj.begin());
if(so.size()>0) cout<<-1,exit(0);
while(!sj.empty()&&sj.size()>=3){
int a,b,c;
auto i=sj.begin();
a=i->front(),i=sj.erase(i),
b=i->front(),i=sj.erase(i),
c=i->front(),i=sj.erase(i);
ans.push_back({a,b,c});
}
if(sj.size()>0) cout<<-1,exit(0);
for(auto &i: ans){
for(auto &j: i)
cout<<j<<' ';
cout<<'\n';
}
}
提交记录,完美结束。
后附
日志
v1.0 on 2022.12.16: 发布
标签:300,题解,CodeForces,sj,int,erase,so,front,节点 From: https://www.cnblogs.com/wanguan/p/16988472.html