Riding the Fences
Farmer John owns a large number of fences that must be repairedannually. He traverses the fences by riding a horse along each andevery one of them (and nowhere else) and fixing the broken parts.
Farmer John is as lazy as the next farmer and hates to ride the samefence twice. Your program must read in a description of a network offences and tell Farmer John a path to traverse each fence length exactlyonce, if possible. Farmer J can, if he wishes, start and finish at anyfence intersection.
Every fence connects two fence intersections, which are numberedinclusively from 1 through 500 (though some farms have far fewer than500 intersections). Any number of fences (>=1) can meet at a fenceintersection. It is always possible to ride from any fence to any otherfence (i.e., all fences are "connected").
Your program must output the path of intersections that, if interpretedas a base 500 number, would have the smallest magnitude.
There will always be at least one solution for each set of inputdata supplied to your program for testing.
PROGRAM NAME: fenceINPUT FORMAT
Line 1:The number of fences, F (1 <= F <= 1024)
Line 2..F+1:A pair of integers (1 <= i,j <=500) that tell which pair of intersections this fence connects.
SAMPLE INPUT (file fence.in) 91 22 33 44 24 52 55 65 74 6OUTPUT FORMAT
The output consists of F+1 lines, each containing a single integer.Print the number of the starting intersection on the first line, thenext intersection’s number on the next line, and so on, until the finalintersection on the last line. There might be many possible answers toany given input set, but only one is ordered correctly.
SAMPLE OUTPUT (file fence.out)1234254657解决方案
找出起始点，然后用从起始点开始用深搜寻找欧拉路径，，唯一需要注意的是两个点之间可能有多条边连接。
运行结果Executing… Test 1: TEST OK [0.003 secs, 4480 KB] Test 2: TEST OK [0.003 secs, 4480 KB] Test 3: TEST OK [0.005 secs, 4480 KB] Test 4: TEST OK [0.003 secs, 4480 KB] Test 5: TEST OK [0.005 secs, 4480 KB] Test 6: TEST OK [0.008 secs, 4480 KB] Test 7: TEST OK [0.011 secs, 4480 KB] Test 8: TEST OK [0.014 secs, 4480 KB]All tests OK.通过代码
/*ID: c1033311LANG: C++TASK: fence*/#include<stdio.h>#include<string.h>#define MAX 501#define MAXP 1030int point[MAXP],deg[MAX],G[MAX][MAX];int n=0;void euler(int u){int v;for(v=1;v<MAX;++v){if(G[u][v]){G[u][v]–;G[v][u]–;euler(v);point[n++]=v;}}}int main(){FILE *fin=fopen("fence.in","r");FILE *fout=fopen("fence.out","w");int F,i,a,b;int start;fscanf(fin,"%d",&F); //输入for(i=0;i<F;++i){fscanf(fin,"%d%d",&a,&b);G[a][b]++; //两个点之间可能有多条边G[b][a]++;deg[a]++;deg[b]++;}start=1;for(i=1;i<MAX;++i)//寻找起点if(deg[i]%2){start=i;break;}euler(start); //寻找欧拉路径point[F]=start;for(i=F;i>=0;–i) //输出fprintf(fout,"%d\n",point[i]);return 0;}
感受最美的风景。你曾经说，
