CF300B Coach 题解

闲话

调了好一会，甚至还重构了一次代码才对，但是还是很喜欢并查集，并查集可爱捏。

题意省流

$n$ 个学生分成 $3$ 人一组，要满足 $m$ 个条件，每个条件给出两个数 $x,y$，要求 $x$ 和 $y$ 必须在一个组里。

正文

要使学生三人一组，一眼使用并查集。

首先考虑无解（输出 $-1$ ）的情况：

• 给出的限制条件中有大于 $3$ 个人组队的情况。
• 有一人或两人落单。

第二种情况的数据：

6 4
1 2
3 4
5 6

此时没有能够凑出 $3$ 人一队的方案，输出 $-1$。

对于合法的情况可以分三种情况：

1. 组中已经有三人，可以直接成组。
2. 组中有两人，需要找落单一人。
3. 仅有一人，可以与两人组成组或另找两个单人成组。

贴码

没有优化，人傻常数大，但是在 $3\leq n\leq 48$ 的情况下其实不是很要紧。

其实是因为没有精神再去打更好的解法了。

#include<bits/stdc++.h>
#define MAXN 10010
using namespace std;
int n,m,fa[MAXN],ans,ton[MAXN];
int akali[MAXN],num[MAXN],cnt;
bool vis[MAXN],Vis[MAXN];
queue<int> q[MAXN];
int find(int x){
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1,u,v;i<=m;i++){
		cin>>u>>v;
		int fau=find(u),fav=find(v);
		fa[fau]=fav;
	}
	for(int i=1;i<=n;i++) ton[find(i)]++;
	for(int i=1;i<=n;i++){
		if(ton[fa[i]]>=4){
			cout<<-1;
			return 0;
		}
		q[fa[i]].push(i);
		if(!Vis[fa[i]]){
			Vis[fa[i]]=1;
			num[++cnt]=fa[i];
		}
		akali[fa[i]]++;
	}
	for(int i=1;i<=cnt;i++){/*处理 2+1 的情况*/
		if(akali[num[i]]==2){
			for(int j=1;j<=cnt;j++){
				if(i==j) continue;
				if(akali[num[j]]==1){
					akali[num[j]]=0;
					q[num[i]].push(num[j]);
					fa[num[j]]=num[i];
					break;
				}
			}
		}
	}
	for(int i=1;i<=cnt;i++){/*处理 1+1+1 的情况*/
		if(akali[num[i]]==1){
			for(int j=i+1;j<=cnt;j++){
				if(akali[num[j]]==1){
					akali[num[j]]=0;
					q[num[i]].push(num[j]);
					fa[num[j]]=num[i];
					for(int k=1+j;k<=cnt;k++){
						if(akali[num[k]]==1){
							akali[num[k]]=0;
							q[num[i]].push(num[k]);
							fa[num[k]]=num[i];
							break;
						}
					}
					break;
				}
			}
			akali[num[i]]=3;
		}
	}
	for(int i=1;i<=n;i++){
		if(q[fa[i]].size()!=3){/*若有不能成组的则无解*/
			cout<<-1;
			return 0;
		}
	}
	for(int i=1;i<=n;i++){
		if(!vis[fa[i]]){
			vis[fa[i]]=1;
			while(!q[fa[i]].empty()){
				cout<<q[fa[i]].front()<<" "; q[fa[i]].pop();
			}
			cout<<"\n";
		}
	}
	return 0;
}