题目链接

P2731 骑马修栅栏 Riding the Fences

解题思路

存图+简单\(DFS\)。

坑点在于两种不同的输出方式。

#include<stdio.h>
#define N 1030
int n,g[N][N],deg[N],m=1024,M=-1;
void dfs(int p){
    int i;
    printf("%d\n",p);
    for(i=m;i<=M;i++){
        if(g[p][i]){
            g[p][i]--;
            g[i][p]--;
            dfs(i);
        }
    }
}
int main(){
    int i,a,b;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d%d",&a,&b);
        if(a<m)m=a;
        if(b<m)m=b;
        if(a>M)M=a;
        if(b>M)M=b;
        g[a][b]++;g[b][a]++;
        deg[a]++;deg[b]++;
    }
    int st=m;
    for(i=m;i<=M;i++)
        if(deg[i]&1){st=i;break;}
    dfs(st);
    return 0;
}

刚开始图方便直接在\(DFS\)内输出了，结果莫名其妙\(WA\)。想了半天才想出这样一个数据：

4
1 2
1 3
3 4
4 1

所以不能直接输出，应该存栈输出。

AC代码

#include<stdio.h>
#define N 1030
int n,g[N][N],deg[N],m=1024,M=-1,sta[N<<1],cnt;
void dfs(int p){
    int i;
    for(i=m;i<=M;i++){
        if(g[p][i]){
            g[p][i]--;
            g[i][p]--;
            dfs(i);
        }
    }
    sta[++cnt]=p;
}
int main(){
    int i,a,b;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d%d",&a,&b);
        if(a<m)m=a;
        if(b<m)m=b;
        if(a>M)M=a;
        if(b>M)M=b;
        g[a][b]++;g[b][a]++;
        deg[a]++;deg[b]++;
    }
    int st=m;
    for(i=m;i<=M;i++)
        if(deg[i]&1){st=i;break;}
    dfs(st);
    for(i=cnt;i;i--)printf("%d\n",sta[i]);
    return 0;
}