USACO Riding the Fences

本题考察的是无向图上的欧拉路问题，这题也是前面那个text中的例题，因此，思路并不复杂。
不过需要注意一些细节问题：
首先，是起点的选择。可以找到欧拉路的图有两种，其一是每个顶点度数都是偶数，另一个是仅有两个度数为奇数的顶点。要针对这两种情况分别考虑。
其次，是无向图转换有向图，要保证删边时两条都要删掉。
还有，重边的问题，本人使用一个cnt变量记录每条边的数量。
最后，数组可以开大一点，本人开到510在第八个数据会出错，扩大到600就不会了。不知是什么原因。

代码如下，本人没有写检查是否是欧拉图的代码。

C语言: 高亮代码由发芽网提供

001 #include <stdio.h>
002 #include <stdlib.h>
003 #define MXN 600
004
005 typedef struct node
006 {
007     int v;
008     struct node *next;
009     int cnt;    //whether the route exists and its count
010 }node;
011
012 node *first[MXN];
013 int deg[MXN] = {};
014 int route[MXN] = {};
015 int cnt;
016 int max = 0;
017 int min = MXN;
018
019 void add_edge(int b,int e,long cnt)
020 {
021     node *p;
022     p = malloc(sizeof(node));
023     p->cnt = cnt;
024     p->v = e;
025     p->next = first[b];
026     first[b] = p;
027 }
028
029
030 long adj[MXN][MXN] = {};
031 void init()
032 {
033     int F;
034     int b,e;
035     scanf("%d\n",&F);
036     while(F --)
037     {
038         scanf("%d%d",&b,&e);
039         adj[b][e] ++;
040         adj[e][b] ++;
041         deg[b] ++;
042         deg[e] ++;
043         if(b > e)
044         {
045             if(b > max)    max = b;
046             if(e < min)    min = e;
047         }
048         else
049         {
050             if(b < min)    min = b;
051             if(e > max)    max = e;
052         }
053     }
054     //convert adjcency matrix to adjcency list thus node->v is in increasing order
055     int i,j;
056     for(i = min;i <= max;i ++)
057         for(j = max;j >= min;j --)
058             if(adj[i][j] > 0)
059                 add_edge(i,j,adj[i][j]);
060 }
061
062 int findstart()
063 {
064     int i;
065     int odd_cnt = 0;
066     for(i = 1;i <= max;i ++)
067         if(deg[i] % 2)
068             odd_cnt ++;
069     if(odd_cnt == 2)
070         for(i = min;i <= max;i ++)
071             if(deg[i] % 2)    return i;   //use the min odd node as start node
072
073     return min;     //no odd nodes, use the minimum node as start node
074 }
075
076 void disable(int b,int e)    //delete one edge from b to e
077 {
078     node *p;
079     for(p = first[b];p != NULL;p = p->next)
080         if(p->v == e)
081         {
082             p->cnt --;
083             return;
084         }
085 }
086
087 void solve(int s)
088 {
089     node * p;
090     for(p = first[s];p != NULL;p = p->next)
091     {
092         if(p->cnt > 0)
093         {
094             p->cnt --;
095             disable(p->v,s);
096             solve(p->v);
097         }
098     }
099     route[cnt ++] = s;
100 }
101
102 void pt()
103 {
104     int i;
105     for(i = cnt - 1;i >= 0;i --)    //output in reverse order
106         printf("%d\n",route[i]);
107 }
108
109 void debug()
110 {
111     int i;
112     node * p;
113     for(i = min;i <= max;i ++)
114     {
115         printf("%d ->",i);
116         for(p = first[i]; p != NULL;p = p->next)
117             printf(" %d",p->v);
118         printf("\n");
119     }
120 }
121
122 int main()
123 {
124     freopen("fence.in","r",stdin);
125     freopen("fence.out","w",stdout);
126     init();
127     //debug();
128     cnt = 0;
129     solve(findstart());
130     pt();
131     fclose(stdin);
132     fclose(stdout);
133     return 0;
134 }