CodeForces-300#B 题解

题意

给定 \(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: 发布