闲话
调了好一会，甚至还重构了一次代码才对，但是还是很喜欢并查集，并查集可爱捏。
题意省流
$n$ 个学生分成 $3$ 人一组，要满足 $m$ 个条件，每个条件给出两个数 $x,y$，要求 $x$ 和 $y$ 必须在一个组里。
正文
要使学生三人一组，一眼使用并查集。
首先考虑无解（输出 $-1$ ）的情况：
- 给出的限制条件中有大于 $3$ 个人组队的情况。
- 有一人或两人落单。
第二种情况的数据：
6 4
1 2
3 4
5 6
此时没有能够凑出 $3$ 人一队的方案，输出 $-1$。
对于合法的情况可以分三种情况：
- 组中已经有三人，可以直接成组。
- 组中有两人，需要找落单一人。
- 仅有一人，可以与两人组成组或另找两个单人成组。
贴码
没有优化，人傻常数大，但是在 $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;
}