• 欢迎光临~

# CodeForces-300#B 题解

## 正文

``````//板子，不做解释
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);
}
``````

``````#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);
``````

``````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首项
``````

``````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});
}
``````

``````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';
}
``````

``````//不注解，前面已做讲解，不懂评论区问/私聊
#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: 发布