題目鏈接

這數(shù)據(jù)。。簡直了

有自環(huán)和重邊，有些點可能沒有連邊(并查集不好使 就DFS吧)
因為重邊+自環(huán)可能非常多，同一個點可能經(jīng)過n次，所以必須要重置表頭H[x](類似當(dāng)前弧優(yōu)化)
另外是找歐拉回路不是歐拉路徑，判斷不要錯
無向圖: 所有點度數(shù)都為偶數(shù)(這就不需要什么入度出度之分了)
有向圖: 所有點入度=出度(dgr = indgr-outdgr = 0)

#include <cstdio> #include <cctype> #include <cstdlib> #define gc() getchar() const int N=1e5+5,M=2e5+5;int n,m,dgr[N],Enum,H[N],nxt[M<<1],to[M<<1],ans[M],cnt; bool vis[M<<1];inline int read() {int now=0,f=1;register char c=gc();for(;!isdigit(c);c=gc()) if(c=='-') f=-1;for(;isdigit(c);now=now*10+c-'0',c=gc());return now*f; } inline void AddEdge(int u,int v){to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum; } void DFS_u(int x) {for(int i=H[x]; i; i=nxt[i])if(!vis[i]){H[x]=i/*對于重復(fù)多次的點 之前的邊直接跳過*/, vis[i]=vis[i^1]=1, DFS_u(to[i]),ans[++cnt]=i>>1, i&1?ans[cnt]*=-1:0;i=H[x];//i為后續(xù)點更新之后的表頭 } } void Undirect() {n=read(),m=read(), Enum=1;for(int u,v,i=1; i<=m; ++i){u=read(),v=read(),AddEdge(u,v),AddEdge(v,u);++dgr[u], ++dgr[v];}for(int i=1; i<=n; ++i)if(dgr[i]&1) {printf("NO"); return;}//所有點度數(shù)都為偶數(shù) for(int i=1; i<=n; ++i)if(dgr[i]) {DFS_u(i); break;}//任找一(與圖連通的)點 if(cnt<m) printf("NO");else{puts("YES");for(int i=cnt; i; --i) printf("%d ",ans[i]);} } void DFS_d(int x) {for(int i=H[x]; i; i=nxt[i])if(!vis[i])H[x]=i, vis[i]=1, DFS_d(to[i]), ans[++cnt]=i, i=H[x]; } void Direct() {n=read(),m=read();int u=0,v;for(int i=1; i<=m; ++i){u=read(),v=read(),AddEdge(u,v);--dgr[u], ++dgr[v];}int s=u;for(int i=1; i<=n; ++i)if(dgr[i]) {printf("NO"); return;}//所有點入度=出度 // if(dgr[i]&1 && ++t>2) {printf("NO"); return;}//WA: 這是歐拉路 // for(int i=1; i<=n; ++i)//WA: 所有點已經(jīng)度數(shù)都為0了。。 // if(dgr[i]) {DFS_d(i); break;}DFS_d(s);if(cnt<m) printf("NO");else{puts("YES");for(int i=cnt; i; --i) printf("%d ",ans[i]);} }int main() {int t=read();t==1 ? Undirect() : Direct();return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/SovietPower/p/8496077.html

總結(jié)

以上是生活随笔為你收集整理的UOJ.117.欧拉回路的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。