Last Corollary CodeForces – 1364D（dfs树找最小环）starletkiss的博客-

思路：对于所给的图形来说，可以分为树图和非树图。
两种图的做法不一样，因为树图是没有环的，只有第二种选择。
对于树图来说，我们找出树的每一层有哪几个点，并且保存起来。然后分别查看（0,2,4…）层的总数和(1,3,5…)层的总数，哪一个符合就输出哪一个就行。
对于非树图来讲，就比较麻烦了。
首先我们先找出非树图中最小的环来，假如这个环的长度为len. 如果len<=k的话，那么我们把这个环的点输出就可以了。如果len>k的话，我们可以发现，对于一个长度为len的环，不相邻的点一共有len/2(下取整)个。也就是说，我们找出非树图中最小的环，就一定可以得到符合题意的答案。
那么接下来就是怎么去找非树图的最小环了。具体的我就不赘述了，简而言之就是将一个图先当做树去遍历，记录每一个点出现的次序，如果发现了这个点之前出现的话，就可以直接计算出这个环的长度，然后我们不断的更新最小值，记录一下这个环上面的一个点就行。在dfs的时候记录一下每一个点的先驱节点是什么，方便后面输出。
代码如下：

#include<bits/stdc++.h> #define ll long long #define inf 0x3f3f3f3f using namespace std; const int maxx=1e5+100; const int maxm=2e5+100; struct node{ int to,next; }e[maxm<<1]; int head[maxm<<1]; int vis[maxx],dis[maxx],f[maxx]; vector<int> q[maxx]; int n,m,k,tot,ans=inf,pos; inline void init() {  tot=0; memset(head,-1,sizeof(head)); memset(dis,0,sizeof(dis)); memset(vis,0,sizeof(vis)); } inline void add(int u,int v) {  e[tot].next=head[u],e[tot].to=v,head[u]=tot++; } inline int dfs(int u,int fa,int id) {  dis[u]=id;  vis[u]=1;  f[u]=fa; for(int i=head[u];i!=-1;i=e[i].next) { int to=e[i].to; if(to==fa) continue; if(vis[to]) //这个点之前遍历过，就说明出现了环 { if(ans>abs(dis[to]-dis[u])+1) {     ans=abs(dis[to]-dis[u])+1;     pos=u; } } else dfs(to,u,id+1); } } inline void Dfs(int u,int f,int h) {  q[h].push_back(u); for(int i=head[u];i!=-1;i=e[i].next) { int to=e[i].to; if(to==f) continue; Dfs(to,u,h+1); } } int main() { scanf("%d%d%d",&n,&m,&k); init(); int x,y; for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); add(x,y); add(y,x); } if(m==n-1) {   cout<<1<<endl; Dfs(1,0,0); int sumj=0,sumo=0; int i=0; while(q[i].size()) { if(i%2==0) sumj+=q[i].size(); else sumo+=q[i].size();    i++; } int num=(k+1)/2; if(sumj>=num) { for(int i=0;;i+=2) { for(int j=0;j<q[i].size();j++) {      cout<<q[i][j]<<" ";      num--; if(!num) break; } if(!num) break; } } else { for(int i=1;;i+=2) { for(int j=0;j<q[i].size();j++) {      cout<<q[i][j]<<" ";      num--; if(!num) break; } if(!num) break; } } return 0; }  vector<int> p; dfs(1,0,0); if(ans<=k) {   cout<<2<<endl<<ans<<endl; for(int i=1;i<=ans;i++)     cout<<pos<<" ",pos=f[pos];   cout<<endl; } else { int num=k/2+(k%2==1);   cout<<1<<endl; int cnt=0; for(;num;num--) {    cout<<pos<<" ";    pos=f[pos];    pos=f[pos]; }   cout<<endl; } return 0; } 

努力加油a啊，(^o)/~