一级a做爰片免费网站冫,免费网站源码博客,城阳 网站建设,wordpress教程 好看题目链接 这数据。。简直了 有自环和重边#xff0c;有些点可能没有连边(并查集不好使 就DFS吧) 因为重边自环可能非常多#xff0c;同一个点可能经过n次#xff0c;所以必须要重置表头H[x](类似当前弧优化) 另外是找欧拉回路不是欧拉路径#xff0c;判断不要错 无向图: 所…题目链接 这数据。。简直了 有自环和重边有些点可能没有连边(并查集不好使 就DFS吧) 因为重边自环可能非常多同一个点可能经过n次所以必须要重置表头H[x](类似当前弧优化) 另外是找欧拉回路不是欧拉路径判断不要错 无向图: 所有点度数都为偶数(这就不需要什么入度出度之分了) 有向图: 所有点入度出度(dgr indgr-outdgr 0) #include cstdio
#include cctype
#include cstdlib
#define gc() getchar()
const int N1e55,M2e55;int n,m,dgr[N],Enum,H[N],nxt[M1],to[M1],ans[M],cnt;
bool vis[M1];inline int read()
{int now0,f1;register char cgc();for(;!isdigit(c);cgc()) if(c-) f-1;for(;isdigit(c);nownow*10c-0,cgc());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 iH[x]; i; inxt[i])if(!vis[i]){H[x]i/*对于重复多次的点 之前的边直接跳过*/, vis[i]vis[i^1]1, DFS_u(to[i]),ans[cnt]i1, i1?ans[cnt]*-1:0;iH[x];//i为后续点更新之后的表头 }
}
void Undirect()
{nread(),mread(), Enum1;for(int u,v,i1; im; i){uread(),vread(),AddEdge(u,v),AddEdge(v,u);dgr[u], dgr[v];}for(int i1; in; i)if(dgr[i]1) {printf(NO); return;}//所有点度数都为偶数 for(int i1; in; i)if(dgr[i]) {DFS_u(i); break;}//任找一(与图连通的)点 if(cntm) printf(NO);else{puts(YES);for(int icnt; i; --i) printf(%d ,ans[i]);}
}
void DFS_d(int x)
{for(int iH[x]; i; inxt[i])if(!vis[i])H[x]i, vis[i]1, DFS_d(to[i]), ans[cnt]i, iH[x];
}
void Direct()
{nread(),mread();int u0,v;for(int i1; im; i){uread(),vread(),AddEdge(u,v);--dgr[u], dgr[v];}int su;for(int i1; in; i)if(dgr[i]) {printf(NO); return;}//所有点入度出度
// if(dgr[i]1 t2) {printf(NO); return;}//WA: 这是欧拉路
// for(int i1; in; i)//WA: 所有点已经度数都为0了。。
// if(dgr[i]) {DFS_d(i); break;}DFS_d(s);if(cntm) printf(NO);else{puts(YES);for(int icnt; i; --i) printf(%d ,ans[i]);}
}int main()
{int tread();t1 ? Undirect() : Direct();return 0;
} 转载于:https://www.cnblogs.com/SovietPower/p/8496077.html
