刚开始学欧拉回路，因为不太理解导致\(WA\)了两次。
错点：\(1.\)
度数为奇数个的点数大于2时不存在欧拉路径（是偶数个也不行）。
\(2.\)
如果存在欧拉路径而不是欧拉回路时，不能随便选一个点当做起点，必须选度数为奇数的两个点中的一个。
#include#include #include using namespace std;const int N = 100005;int n,dis[200][200],fa[N],st[N],top;int cnt,ans[N],t,s=200,du[N],sum;char x[N],y[N];int find(int x){ if(x==fa[x]) return x; fa[x]=find(fa[x]); return fa[x];}int main(){ scanf("%d",&n); for(int i=1;i<=150;i++) fa[i]=i; for(int i=1;i<=n;i++) { cin>>x[i]>>y[i]; s=min(s,min((int)x[i],(int)y[i])); dis[(int)x[i]][(int)y[i]]=1; dis[(int)y[i]][(int)x[i]]=1; du[(int)x[i]]++; du[(int)y[i]]++;// if(du[x[i]]==1) ++sum if(find((int)x[i])!=find((int)y[i])) fa[find((int)x[i])]=find((int)y[i]); } int zx=find(s); for(int i=1;i<=n;i++) { if(find((int)x[i])!=zx||find((int)y[i])!=zx) { printf("No Solution\n"); return 0; } } for(int i=1;i<=150;i++) if(du[i]&1) ++cnt; if(cnt==1||cnt>2) { printf("No Solution\n"); return 0; } for(int i=1;i<=150;i++) if(du[i]&1) { s=i; break; } st[++top]=s; while(top>0) { int u=st[top],v=0; for(int i=1;i<=150;i++) if(dis[u][i]) { v=i; break; } if(v>0) { st[++top]=v; dis[u][v]=dis[v][u]=0; } else { --top; ans[++t]=u; } } if(t>n+1) { printf("No Solution\n"); return 0;} for(int i=t;i;i--) cout<<(char)ans[i]; return 0;}
在一本通上看见一道很巧妙的题。
有\(N\)个盘子，每个盘子上写着一个仅由小写字母组成的英文单词。你需要给这些盘子安排一个合适的顺序，使得相邻两个盘子中，前一个盘子的单词的末字母等于后一个盘子上单词的首字母。
\(N<=100000\)思路分析（当然是书上的）：
以26个字母作为顶点，对于每一个盘子，如果它的首字母为\(c1\)，末字母为\(c2\)，那么从\(c1\)向\(c2\)连一条有向边。这样问题转化为在图中寻找一条不重复的经过每一条边的路径，即欧拉路径。(一定有回路，如果不保证先判断一下)
欧拉回路板子：#include#include #include #include using namespace std;const int N = 1000010;int head[N],tot,stack[N],ans[N];bool vis[N];int n,m,top,t;struct edge{ int node,next;}e[N<<1];void add(int x,int y){ e[++tot].node=y; e[tot].next=head[x]; head[x]=tot;}void euler(){ stack[++top]=1; while(top>0) { int x=stack[top],i=head[x]; while(i&&vis[i]) i=e[i].next;//while写成了 if if(i) { stack[++top]=e[i].node; head[x]=e[i].next; vis[i]=vis[i^1]=true; } else { --top; ans[++t]=x; } }}int main(){ scanf("%d%d",&n,&m); tot=1; int x,y; for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); add(x,y); add(y,x); } euler(); for(int i=t;i;i--) printf("%d\n",ans[i]); return 0;}