题目：
给定一张无向图，要求输出两条欧拉路覆盖所有边；
分类讨论，首先判-1：有两个以上连通块 / 有四个以上奇度数点 / 只有一条边 / 有两个连通块而其中一个连通块里有四个奇度数点 (/ 有连通块里有奇数个奇度数点)；
然后分两个连通块和一个连通块的情况进行 dfs 找欧拉路(模板 dfs )；
注意可能没有奇度数的点，也就是有欧拉回路，所以不仅找奇度数点进行 dfs ，还要在那之后 dfs 仍然没有被走过的点；
明明是模仿题解写的竟然还调了两小时...码力++...
代码如下：
#include#include #include using namespace std;int const maxn=10005;int n,m,d[maxn],ans[maxn],tot,fa[maxn],cnt,c[maxn],hd[maxn],ct=1;bool vis[maxn],used[maxn];struct N{ int to,nxt; N(int t=0,int n=0):to(t),nxt(n) {}}ed[maxn<<1];void add(int x,int y){ed[++ct]=N(y,hd[x]); hd[x]=ct;}int find(int x){ return fa[x]==x?x:fa[x]=find(fa[x]);}void dfs(int x){ vis[x]=1; for(int i=hd[x];i;i=hd[x]) { hd[x]=ed[i].nxt; if(used[i>>1])continue; used[i>>1]=1; dfs(ed[i].to); ans[++tot]=(i>>1); }}int main(){ freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); n=10000; scanf("%d",&m);//不能是 n=10005 for(int i=1;i<=n;i++)fa[i]=i;//!! for(int i=1,x,y;i<=m;i++) { scanf("%d%d",&x,&y); add(x,y); add(y,x); d[x]++; d[y]++; if(find(x)!=find(y))fa[find(x)]=find(y); } for(int i=1;i<=n;i++) if(d[i]&1) c[find(i)]++; for(int i=1;i<=n;i++) if(c[i]&1){printf("-1\n"); return 0;} for(int i=1,sum=0;i<=n;i++) { if(d[i])cnt+=(i==find(i)); if(c[i])sum+=c[i]; if(sum>4){printf("-1\n"); return 0;} } if(cnt>2){printf("-1\n"); return 0;} if(cnt==2) { for(int i=1;i<=n;i++) if(c[i]==4){printf("-1\n"); return 0;} for(int i=1;i<=n;i++) if(!vis[i]&&(d[i]&1)) { tot=0; dfs(i); printf("%d\n",tot); for(int j=tot;j;j--)printf("%d ",ans[j]); printf("\n"); } for(int i=1;i<=n;i++)//欧拉回路 if(!vis[i]&&d[i]) { tot=0; dfs(i); printf("%d\n",tot); for(int j=tot;j;j--)printf("%d ",ans[j]); printf("\n"); } } else { bool fl=0; for(int i=1;i<=n;i++) if(c[i]==4)fl=1; if(fl) { for(int i=1;i<=n;i++) if(d[i]&1) { for(int j=i+1;j<=n;j++) if(d[j]&1){d[i]++; d[j]++; add(i,j); add(j,i); break;} break; } for(int i=1;i<=n;i++) if(!vis[i]&&(d[i]&1)){tot=0; dfs(i); break;} for(int i=1;i<=tot;i++) if(ans[i]==m+1) { printf("%d\n",i-1); for(int j=1;j