CF1817B Fish Graph 题解

· · 题解

本题可以使用深度优先搜索算法。

首先可以尝试寻找那个度数不小于 4 的特殊结点，确定该结点后，用深度优先搜索找该点所在的环。

具体地，开始时选择“特殊结点”的邻接点中随便一个结点开始找环，搜索中对于每一个点，遍历除了它的前驱的所有临接点。若再次搜到起始点（即“特殊结点”），就把环上所有边记下来返回。

最后输出这些记下来的边，然后从连接特殊结点的其他边中随便选 2 条出来输出即可完成要求。

如果所有的度数不小于 4 的结点都不满足条件，就报告无解。

放代码：

#include<bits/stdc++.h>
using namespace std;
vector<int> g[2001],c,f;
bool b[2001];
int d[2001];
void dfs(int s,int e,int x){
  c.emplace_back(x),b[x]=true; // 搜索到该点，打上标记
  if(x==e){f=c; return;} // 记下环上的所有结点
  for(int i:g[x])
    if(!b[i]&&(s!=x||i!=e)){
      dfs(s,e,i); // 尝试搜索邻接点
      if(!f.empty())return;
    }
  c.pop_back(); // 该结点不可行
}
int main(){
  ios::sync_with_stdio(false);
  int t; cin>>t;
  while(t--){
    int n,m; cin>>n>>m; bool w=false;
    for(int i=1;i<=n;i++)g[i].clear(),b[i]=d[i]=0;
    for(int i=1;i<=m;i++){
      int u,v; cin>>u>>v;
      g[u].emplace_back(v);
      g[v].emplace_back(u);
      d[u]++,d[v]++; // 记录度数
    }
  for(int i=1;i<=n;i++)
    if(d[i]>=4&&!w)
      for(int j:g[i]){ // 随便选择它的一个邻接点并开始找环
        c.clear(),f.clear();
        memset(b,0,sizeof(b)); // 记得清空标记数组
        if(dfs(i,j,i);!f.empty()){
          vector<pair<int,int> > r;
          for(int i=0;i<f.size();i++)
            r.emplace_back(f[i],f[(i+1)%f.size()]);
          int c=0;
          for(int j:g[i]){
            if(c>1)break;
            if(find(f.begin(),f.end(),j)==f.end())
              c++,r.emplace_back(i,j);
          } // 从其他结点中选取 2 个
          if(c<2)continue;
          cout<<"Yes\n"<<r.size()<<'\n';
          for(auto [u,v]:r)cout<<u<<' '<<v<<'\n';
          w=true; break;
        }
      }
    if(!w)cout<<"No\n"; // 无解情况
  }
  return 0;
}