无弦环
wenge
2020-02-12 22:48:53
```cpp
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define clr(a,b) memset(a,b,sizeof(a))
#define PRINT(x) cout<<#x<<" = "<<x
#define br cout<<"\n"
ll n,m,ans;
vector<int> f[200005];
int t=0,dfn[200005],vis[200005],p[200005],l=0;
stack<int> st;
void dfs(int x,int fa){
dfn[x]=++t;
st.push(x);
for(int i=0;i<f[x].size();i++){
int y=f[x][i];
if(y==fa)continue;
if(!dfn[y])dfs(y,x);
else{
while(1){
int u=st.top();
st.pop();
p[++l]=u;
vis[u]=1;
if(u==y)break;
}
int minn=0x3f3f3f3f,u,v;
for(int j=1;j<=l;j++){
for(int k=0;k<f[p[j]].size();k++){
int q=f[p[j]][k];
if(j==1&&q==p[l])continue;
if(j==l&&q==p[1])continue;
if(q==p[j-1]||q==p[j+1])continue;
if(vis[q]){
if(abs(dfn[p[j]]-dfn[q])<minn){
minn=abs(dfn[p[j]]-dfn[q]);
u=p[j],v=q;
}
}
}
}
if(minn<0x3f3f3f3f){
if(dfn[u]>dfn[v])swap(u,v);
int l1=0;
for(int j=1;j<=l;j++){
if(dfn[p[j]]>=dfn[u]&&dfn[p[j]]<=dfn[v])l1++;
}
cout<<l1<<"\n";
for(int j=1;j<=l;j++){
if(dfn[p[j]]>=dfn[u]&&dfn[p[j]]<=dfn[v])cout<<p[j]<<" ";
}
exit(0);
}
else{
cout<<l<<"\n";
for(int j=1;j<=l;j++)cout<<p[j]<<" ";
exit(0);
}
}
}
st.pop();
}
int main(){
//freopen("test.in","r",stdin);
//freopen("test.out","w",stdout);
//ios::sync_with_stdio(false);
//cin.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
ll u,v;
cin>>u>>v;
f[u].pb(v);
f[v].pb(u);
}
for(int i=1;i<=n;i++){
if(!dfn[i])dfs(i,0);
}
return 0;
}
```