欧拉回路,我知道怎么做,但是我不知到为什么可以这么做!,囧囧;就当是背课文把,反正这就是欧拉回路。
如果有节点的度为奇数就从它开始,否则就从最小的开始,然后就是看下面的代码把:
#include <stdio.h>
#define MAXV 500
#define MAXE 1024
char map[MAXV][MAXV];
int path[MAXE];
int degree[MAXV];
int len;
int max;
void add(int a, int b)
{
map[a][b]++, degree[a]++;
}
void delete(int a, int b)
{
map[a][b]--, degree[b]--;
}
int getneighbor(int a)
{
int i;
for(i = 0; degree[a] != 0; i++){
if(map[i][a]){
return i;
}
}
}
void fence(int now)
{
int i;
while(degree[now]){
i = getneighbor(now);
delete(i, now);
delete(now, i);
fence(i);
}
path[len++] = now;
}
int main(void)
{
int i;
int n, k = 501;
int a, b;
freopen(fence.in, r, stdin);
freopen(fence.out, w, stdout);
scanf(%d, &n);
for(i = 0; i < n; i++){
scanf(%d%d, &a, &b);
a--, b--;
add(a, b);
add(b, a);
if(max < a){
max = a;
}
if(max < b){
max = b;
}
if(k > a){
k = a;
}
if(k > b){
k = b;
}
}
for(i = 0; i <= max; i++){
if(degree[i] & 1){
k = i;
break;
}
}
fence(k);
for(i = len - 1; i >= 0; i--){
printf(%d\\n, path[i] + 1);
}
return 0;
}