WUST 一笔画（图论知识之欧拉路）

灰太狼 2022-06-12 02:16 191阅读 0赞

## 一笔画 ##

Time Limit: 1 Sec Memory Limit: 128 MB 64bit IO Format: %lld  
Submitted: 67 Accepted: 13  
\[ [Submit][]\]\[ [Status][]\]\[ [Web Board][]\]

## Description ##

对给定的一个无向图，判断能否一笔画出。若能，输出一笔画的先后顺序，否则输出“No Solution!”

所谓一笔画出，即每条边仅走一次，每个顶点可以多次经过。

输出字典序最小的一笔画顺序。

## Input ##

包含多组测试数据。

第一行n，m，有n个点，m条边，以下m行描述每条边连接的两点。(n<=100)

## Output ##

每组测试数据占一行。一笔画的先后顺序，每个顶点之间用一个空格分开。

如果不能完成一笔画，则输出“No Sulotion!”

## Sample Input ![copy.gif][]      ##

3 3
    1 2
    1 3
    2 3
    5 5
    1 2
    2 3
    3 4
    4 5
    5 1

## Sample Output ##

1 2 3 1
    1 2 3 4 5 1

\[ [Submit][]\]\[ [Status][]\]\[ [Web Board][]\]

题解：

不得吐槽一下这一题。。仔细观察可以发现“No Sulotion!”是什么鬼。。如果只是复制到输出那的话你将永远wa还一脸懵逼得去Debug（wa了20多次的惨痛经历，一直在找哪里wa）。。这题思路就是离散数学里的欧拉路，首先要知道度数，说明白了就是每个点有多少条路通往其他点，如果整个图奇数个度数的节点数目为2个或者0个的时候存在欧拉路，即能够一笔画，如果为2个的时候，那两个奇数个度数节点将为开始的点和结束的点，然后这题就好做了，就是判断是否存在欧拉路，然后存在处理一下开始点，就开始dfs了

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    using namespace std;
    int n,m;
    int p[110][110];//保存图
    int b[105];//保存路径
    int d[105];//保存每个点的度数
    int tot;
    void dfs(int x)
    {
        int i;
        for(i=1;i<=n;i++)
        {
            if(p[x][i])
            {
                p[x][i]=0;
                p[i][x]=0;
                dfs(i);
            }
        }
        b[tot]=x;//是反着放进去的要反着输出
        tot++;
    }
    int main()
    {
        int i,j,x,y,num,d1;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            d1=1;
            memset(p,0,sizeof(p));
            memset(d,0,sizeof(d));
            for(i=0;i<m;i++)
            {
                scanf("%d%d",&x,&y);
                p[x][y]=1;
                p[y][x]=1;
                d[x]++;
                d[y]++;
            }
            num=0;
            tot=0;
            for(i=1;i<=n;i++)
            {
                if(d[i]%2)
                {
                    if(num==0)//2个奇数度数情况保存最先那个节点
                        d1=i;
                    num++;
                }
            }
            if(num==2||num==0)//满足欧拉通路的情况，奇数个节点有0个或者2和，有2个情况下那两个为起始点和结束点，选小的为起始点
            {
                dfs(d1);
                for(i=tot-1;i>=1;i--)
                    printf("%d ",b[i]);
                printf("%d\n",b[0]);
            }
            else
            {
                printf("No Solution!\n");//神坑
            }
        }
        return 0;
    }

[Submit]: http://acm.wust.edu.cn/submitpage.php?id=1923&soj=0
[Status]: http://acm.wust.edu.cn/problemstatus.php?id=1923&soj=0
[Web Board]: http://acm.wust.edu.cn/bbs.php?pid=1923&soj=0
[copy.gif]: http://acm.wust.edu.cn/image/copy.gif