首页 > 代码库 > USACO 3.3 fence 欧拉回路
USACO 3.3 fence 欧拉回路
题意：求给定图的欧拉回路（每条边只走一次）
若欧拉回路存在，图中只可能有0个or2个奇数度的点。
求解时，若有奇数度的点，则必须从该点开始。否则可以从任一点开始
求解过程：dfs
1 //主程序部分 2 # circuit is a global array 3 find_euler_circuit 4 circuitpos = 0 5 find_circuit(node 1) 6 --------------------------------------------- 7 # nextnode and visited is a local array 8 # the path will be found in reverse order 9 //递归函数10 find_circuit(node i)11 if node i has no neighbors then12 circuit(circuitpos) = node i13 circuitpos = circuitpos + 114 else15 while (node i has neighbors)16 pick a random neighbor node j of node i17 delete_edges (node j, node i)18 find_circuit (node j)19 circuit(circuitpos) = node i20 circuitpos = circuitpos + 121 -------------------------------------------22 最终结果：将circuit()数组倒序输出即可
1 /* 2 PROB:fence 3 LANG:C++ 4 */ 5 #include <iostream> 6 #include <cstring> 7 #include <cstdio> 8 using namespace std; 9 #define INF 99999910 11 int dx=INF,dy=0,n,f,x,y,p;12 int e[1100][1100];13 int t[1100],seq[1100];14 15 void dfs(int x)16 {17 for (int i=dx;i<=dy;i++)18 if (e[x][i]>0)19 {20 e[x][i]--;21 e[i][x]--;22 dfs(i);23 }24 p++;25 seq[p]=x;26 }27 28 int start()29 {30 for (int i=dx;i<=dy;i++)31 if (t[i]%2!=0)32 return i;33 return 1;34 }35 36 int main()37 {38 freopen("fence.in","r",stdin);39 freopen("fence.out","w",stdout);40 41 memset(e,0,sizeof(e));42 memset(t,0,sizeof(t));43 cin>>f;44 for (int i=1;i<=f;i++)45 {46 cin>>x>>y;47 e[x][y]++;48 e[y][x]++;49 t[x]++;50 t[y]++;51 if (x<dx) dx=x;52 if (y<dx) dx=y;53 if (x>dy) dy=x;54 if (y>dy) dy=y;55 56 }57 58 x=start();59 //cout<<dx<<" "<<dy<<"--"<<x<<endl;60 p=0;61 dfs(x);62 63 //cout<<p<<endl;64 for (int i=p;i>=1;i--)65 cout<<seq[i]<<endl;66 67 return 0;68 }
USACO 3.3 fence 欧拉回路
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。