CF1817B 题解
honglan0301
·
·
题解
题目分析
发现题意就是说让你找一个环，满足环上存在一个点 $u$，向环外连了至少两条边。于是贪心地考虑，我们只需要试图让这个点向环内的连边尽量少。容易发现至少要有两条，而只要找出一个极小环就能取到两条，于是边双缩点之后判断是否有在环上且度数 $\geq 4$ 的点即可，从该点开始找一个极小环再任意找两条边便满足题目要求。
## 代码
赛时代码很丑。
```cpp
/*
author: PEKKA_l
Sexy_goodier _ xiaoqing
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define int long long
int t,n,m,u,v,dfn[2005],low[2005],vis[2005],stk[2005],cntd,top,flag[2005],cnts,sz[2005];
vector <int> e[2005];
void dfs(int x,int fat)
{
dfn[x]=low[x]=++cntd; stk[++top]=x; vis[x]=1;
for(auto i:e[x])
{
if(i==fat) continue;
if(!dfn[i]) {dfs(i,x); low[x]=min(low[x],low[i]);}
else if(vis[i]) {low[x]=min(low[x],dfn[i]);}
}
if(dfn[x]==low[x])
{
cnts++;
while(1)
{
int nw=stk[top--]; flag[nw]=cnts; sz[cnts]++; vis[nw]=0; if(nw==x) break;
}
}
}
void tarjan()
{
for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i,i);
}
int zt[2005],hn[2005],cnth,us[2005],ss[2005];
bool dfs2(int x,int bf,int to)
{
if(x==to&&zt[x]==1) return 1;
if(zt[x]) return 0; zt[x]=1;
for(auto i:e[x])
{
if(i==bf) continue;
if(dfs2(i,x,to))
{
hn[++cnth]=i; return 1;
}
}
return 0;
}
void solve(int x)
{
for(int i=1;i<=n;i++) zt[i]=hn[i]=us[i]=ss[i]=0; cnth=0;
dfs2(x,x,x); for(auto i:e[x]) ss[i]=1;
int num=0;
for(int i=3;i<=cnth;i++)
{
if(ss[hn[i]]) {num=i; break;}
}
for(int i=2;i<=num;i++) us[hn[i]]=1;
cout<<num+2<<endl; hn[num+1]=x;
for(int i=2;i<=num+1;i++) cout<<hn[i-1]<<" "<<hn[i]<<endl;
int cntt=0;
for(auto i:e[x])
{
if(!us[i]) {cntt++; cout<<x<<" "<<i<<endl;}
if(cntt==2) break;
}
}
signed main()
{
cin>>t;
while(t--)
{
cin>>n>>m; for(int i=1;i<=n;i++) e[i].clear(); cntd=cnts=top=0;
for(int i=1;i<=n;i++) dfn[i]=low[i]=vis[i]=stk[i]=flag[i]=sz[i]=0;
for(int i=1;i<=m;i++) {cin>>u>>v; e[u].pb(v); e[v].pb(u);}
tarjan(); bool ok=0;
for(int i=1;i<=n;i++)
{
if(e[i].size()>=4&&sz[flag[i]]>=3)
{
cout<<"YES"<<endl; ok=1; solve(i);
break;
}
}
if(!ok) cout<<"NO"<<endl;
}
}
```