Refact.ai Match 1 (Codeforces Round 985)—D. Cool Graph · znzryb
## 思路讲解
主要思路与洛谷题解类似
[](https://www.luogu.com.cn/problem/solution/CF2029D)
主要思路就是先把所有点给打散，再连起来
打散比较简单，发现这个点入度≥2就持续删边
```cpp
for(int i=1;i<=n;++i) {
if(g[i].size()>=2) { // 入度>=2
vector<int> temp;
for(set<int> :: iterator it=g[i].begin();it!=g[i].end();++it) {
temp.push_back(*it);
}
while (temp.size()>1) {
int a=temp.back();
temp.pop_back();
int b=temp.back();
del(i,a,b);
}
}
}
```
重新连起来需要root1和root2，否则连不起来
```cpp
// root,root2就是根，所有的操作都是他衍生出来的
if(!isCool) {
for(int i=1;i<=n;++i) {
if(vis[i])
continue;
vis[i]=true;
add(root,root2,i);
root2=i;
if(g[i].size()==0) {
continue;
}
vis[*g[i].begin()]=true;
}
}
```
## AC代码
[https://codeforces.com/contest/2029/submission/292760535](https://codeforces.com/contest/2029/submission/292760535)
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=static_cast<int>(1e5)+10;
int n,T,m;
set<int> g[N];
bitset<N> vis;
struct op {
int a,b,c;
};
vector<op> ans;
inline void del(int a,int b, int c) {
op temp;
temp.a=a,temp.b=b,temp.c=c;
ans.push_back(temp);
// 删除
g[a].erase(b);g[a].erase(c);
g[b].erase(a);g[c].erase(a);
// a与b，c关系明晰，但是b，c关系不明，故需要检验判断
if(g[b].count(c)==1)
g[b].erase(c),g[c].erase(b);
else
g[b].insert(c),g[c].insert(b);
}
inline void add(int a,int b,int c) {
op temp;
temp.a=a,temp.b=b,temp.c=c;
ans.push_back(temp);
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
cin>>T;
while (T--) {
cin>>n>>m;
vis.reset(); // 初始化
for(int i=1;i<=n;++i) {
g[i].clear();
}
ans.clear();
if(m==0) {
cout<<0<<endl;
continue;
}
for(int _=1;_<=m;++_) {
int a,b;
cin>>a>>b;
g[a].insert(b); // g里面其实是个set
g[b].insert(a);
}
for(int i=1;i<=n;++i) {
if(g[i].size()>=2) { // 入度>=2
vector<int> temp;
for(set<int> :: iterator it=g[i].begin();it!=g[i].end();++it) {
temp.push_back(*it);
}
while (temp.size()>1) {
int a=temp.back();
temp.pop_back();
int b=temp.back();
temp.pop_back();
del(i,a,b);
}
}
}
bool isCool=true;
int root,root2;
for(int i=1;i<=n;++i) { // 检验是否删完以后成为空图了
if(g[i].size()==1) {
isCool=false;
root=i;
root2=*g[i].begin();
vis[i]=true,vis[*g[i].begin()]=true;
break;
}
}
// root,root2就是根，所有的操作都是他衍生出来的
if(!isCool) {
for(int i=1;i<=n;++i) {
if(vis[i])
continue;
vis[i]=true;
add(root,root2,i);
root2=i;
if(g[i].size()==0) {
continue;
}
vis[*g[i].begin()]=true;
}
}
cout<<ans.size()<<"\n";
for(int i=0;i<ans.size();++i) {
cout<<ans[i].a<<" "<<ans[i].b<<" "<<ans[i].c<<"\n";
}
}
return 0;
}
// AC https://codeforces.com/contest/2029/submission/292760535
```
## 心路历程（WA，TLE，MLE……）
原来的思路是找环，删点，但发现无向图找环很麻烦，也无法满足我的需求，于是还是决定变树。
无向图找环，用dfs加dsu（并查集）
如果不太会的话建议左转去做leetcode684冗余连接
[](https://leetcode.cn/problems/redundant-connection/)
[](https://www.notion.so/1454539447bd80949fb6d5b2057602f6)
**初始化要彻底**
```cpp
vis.reset(); // 初始化
for(int i=1;i<=n;++i) {
g[i].clear();
}
ans.clear();
```