P2731 骑马修栅栏

2019-11-06 08:05:56

字体：大中小

来源：转载

供稿：网友

洛谷

课本Page 466

定理1：存在欧拉路的条件，图是连通的，有且只有 2 个奇点；定理2：存在欧拉回路的条件，图是连通的，有 0 个奇点；

#include<iostream>#include<cstring>#include<string>#include<algorithm>#include<cmath>#include<queue>#include<vector>#include<cstdio> using namespace std;int F,q[501][501],n=0,ans[1300],du[501],cnt=0;//500*500 邻接矩阵 du[]用来记录每个点的度（相连的边的个数） void dfs(int x){ for(int i=1;i<=n;i++) { if(q[x][i])//从任意一个与它相连的点出发 { q[x][i]--;//删去便利完的边 q[i][x]--; dfs(i); } } ans[++cnt]=x;//记路径，不过是倒着记的（递归） }int main(){ scanf("%d",&F); for(int i=1;i<=F;i++) { int x,y; scanf("%d%d",&x,&y); q[x][y]++; q[y][x]++; du[x]++; du[y]++; n=max(n,max(x,y)); } int start=1; for(int i=1;i<=n;i++) if(du[i]%2==1){start=i;break;}//如果有奇点，就从奇点开始寻找，没有就从 1 开始 //如果无奇点，就是一个欧拉回路（因为每一个点都是偶点） dfs(start); for(int i=cnt;i>=1;i--) PRintf("%d/n",ans[i]); return 0;}

上一篇：算分作业3

下一篇：IntelliJ Idea 常用快捷键列表