欧拉路径问题 / 开普饭

P1127 词链

欧拉通路输出路径 O ( n m ) O(n m) O(n m)

注意输出路径要先 d f s dfs dfs，再把边入栈。

不能先入栈再dfs，因为 d f s ( v ) dfs(v) dfs(v)不能搜了，而 u u u的儿子可以继续搜。

比如 a c , c a , a b ac,ca,ab ac,ca,ab 边排序后是 a b , a c , c a ab,ac,ca ab,ac,ca，dfs会先搜 a b ab ab，但此时我们的答案的第一个不是 a b ab ab，而是 a c ac ac，也就是我们要把每个结点能搜的点都加入答案之后再加入它。

P1333 瑞瑞的木棍

欧拉通路裸题，注意没有输入的情况，连通块为0.

POJ1386 Play on Words

欧拉通路裸题,C AC,G 超时了。

牛客欧拉回路

https://www.nowcoder.com/questionTerminal/0ba5d8f525494a8787aaa9d53b5f9b9e

此题不考虑孤立点，然后直接判断度数即可。

HDU 1878

欧拉回路裸题，此题考虑连通能过。

LOJ#117. 欧拉回路

好题，数据够强。

注意几点：

无向图要求：度数都为偶数，经过所有边。

有向图要求：出入度相等，经过所有边。

另外：注意弧优化，即走过的边不用再走了，极端数据不然会T，比如全部是1的自环。

code

// Problem: #117. 欧拉回路// Contest: UOJ// URL: https://uoj.ac/problem/117// Memory Limit: 256 MB// Time Limit: 1000 ms// Date: 2021-03-19 20:15:51// --------by Herio--------#include<bits/stdc  .h>using namespace std;typedef long long ll;typedef unsigned long long ull; const int N=1e5 5,M=4e5 5,inf=0x3f3f3f3f,mod=1e9 7;#define mst(a,b) memset(a,b,sizeof a)#define PII pair<int,int>#define fi first#define se second#define pb emplace_back#define SZ(a) (int)a.size()#define IOS ios::sync_with_stdio(false),cin.tie(0) void Print(int *a,int n){for(int i=1;i<n;i  )printf("%d ",a[i]);printf("%d\n",a[n]); }int t,n,m;int c,d[N];int h[N],cnt;int in[N],ot[N];struct edge{int to,nt,w;}e[M];void add(int u,int v){e[  cnt]={v,h[u]},h[u]=cnt;}void add(int u,int v,int w){e[  cnt]={v,h[u],w},h[u]=cnt;e[  cnt]={u,h[v],-w},h[v]=cnt;}int vis[M];int ans[M],tot;void dfs(int u){//printf("u=%d\n",u);for(int &i=h[u];i;i=e[i].nt){if(vis[(i 1)>>1]) continue;vis[(i 1)>>1]=1;int ii=i;dfs(e[i].to);ans[  tot]=(ii 1)/2*e[ii].w;}}void dfs1(int u){//printf("u=%d\n",u);for(int &i=h[u];i;i=e[i].nt){//printf("u=%d v=%d\n",u,e[i].to);if(vis[i]) continue;vis[i]=1;int ii=i;dfs1(e[i].to);ans[  tot]=ii;}}int main(){scanf("%d%d%d",&t,&n,&m);if(t==1){int st=0;for(int i=1,u,v;i<=m;i  ){scanf("%d%d",&u,&v);add(u,v,1);st=u;d[u]  ,d[v]  ;}c=0;for(int i=1;i<=n;i  ) if(d[i]&1) {c=1;break;}//printf("c=%d\n",c);if(c) puts("NO");else {dfs(st);if(tot!=m) return puts("NO"),0;puts("YES");for(int i=tot;i;i--)printf("%d ",ans[i]);printf("\n");}}else {int st=0;for(int i=1,u,v;i<=m;i  ){scanf("%d%d",&u,&v);add(u,v);st=u;ot[u]  ,in[v]  ;}c=0;for(int i=1;i<=n;i  ) if(in[i]!=ot[i]) {c=1;break;}if(c) puts("NO");else {//printf("cnt=%d\n",cnt);dfs1(st);if(tot!=m) return puts("NO"),0;puts("YES");for(int i=tot;i;i--)printf("%d ",ans[i]);printf("\n");}}return 0;}

P1341 无序字母对

写错了一个变量，一直debug 靠靠靠

// Problem: P1341 无序字母对// Contest: Luogu// URL: https://www.luogu.com.cn/problem/P1341// Memory Limit: 125 MB// Time Limit: 1000 ms// Date: 2021-03-19 21:28:07// --------by Herio--------#include<bits/stdc  .h>using namespace std;typedef long long ll;typedef unsigned long long ull; const int N=3e3 5,M=100,inf=0x3f3f3f3f,mod=1e9 7;#define mst(a,b) memset(a,b,sizeof a)#define PII pair<int,int>#define fi first#define se second#define pb emplace_back#define SZ(a) (int)a.size()#define IOS ios::sync_with_stdio(false),cin.tie(0) void Print(int *a,int n){for(int i=1;i<n;i  )printf("%d ",a[i]);printf("%d\n",a[n]); }int n;string a[N];int d[M];int s[M];int find(int x){return x==s[x]?x:s[x]=find(s[x]);}void Init(int n){for(int i=0;i<n;i  ) s[i]=i;}bool ck(){for(int i=0;i<=n;i  ){int u=a[i][0]-'A',v=a[i][1]-'A';//printf("----%d-----\n",a[i][0]-'A',a[i][1]-'A');u=find(u),v=find(v);if(u!=v) s[u]=v;}int c=0;for(int i=0;i<M;i  ) if(d[i]&&s[i]==i)  c  ;//printf("---c=%d\n",c);return c<2;}struct node{string s;int id;}b[N<<1];bool cmp(node a,node b){return a.s<b.s;}int vis[N];int ans[N],tot;void dfs(int u){for(int i=1;i<=2*n;i  ){if(vis[b[i].id]) continue;if(u!=b[i].s[0]-'A') continue;vis[b[i].id]=1;int v=b[i].s[1]-'A';//printf("u=%d,v=%d\n",u,v);dfs(v); }ans[  tot]=u;}int main(){Init(M);scanf("%d",&n);for(int i=1;i<=n;i  ){cin>>a[i];string tmp=a[i];reverse(tmp.begin(),tmp.end());b[i].s=a[i],b[i].id=i,b[i n].s=tmp,b[i n].id=i;d[a[i][0]-'A']  ,d[a[i][1]-'A']  ;//printf("----%d-----\n",a[i][0]-'A',a[i][1]-'A');}//int iiii='l'-'A';//printf("--%d %d %d\n",d[0],iiii,d[iiii]);if(!ck()) puts("No Solution");else {int c=0;for(int i=0;i<M;i  )if(d[i]&1) {c  ;}//printf("c==%d\n",c);if(c!=0&&c!=2) puts("No Solution");else {//printf("c=%d\n",c);if(c==0){sort(b 1,b 2*n 1,cmp);dfs(b[1].s[0]-'A');//ans[  tot]=b[1].s[0]-'A';for(int i=tot;i;i--)putchar('A' ans[i]);printf("\n");}else {sort(b 1,b 2*n 1,cmp);int st=0;for(int i=1;i<=2*n;i  ){int x=b[i].s[0]-'A';if(d[x]&1){st=x;break;}}//printf("st=%d %d\n",st,d[st]);dfs(st);//ans[  tot]=st;for(int i=tot;i;i--)putchar('A' ans[i]);printf("\n");}}}return 0;}