【一笔画】问题 详解

这道题，初看觉得只是一般的图论问题，不过深究起来，还真是有点意思啊~（经过N次WA试验后得出的结论）
话不多说，先看看题目：

1001: 一笔画

Time Limit: 1 Sec Memory Limit: 128 MB 64bit IO Format: %lld
Description
对给定的一个无向图，判断能否一笔画出。若能，输出一笔画的先后顺序，否则输出“No Solution!”
所谓一笔画出，即每条边仅走一次，每个顶点可以多次经过。
输出字典序最小的一笔画顺序。
Input
包含多组测试数据。
第一行n，m，有n个点，m条边，以下m行描述每条边连接的两点。(n<=100)
Output
每组测试数据占一行。一笔画的先后顺序，每个顶点之间用一个空格分开。

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

Sample Input
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

---

这道题其实是由一道最普通的一笔画图论问题延伸而来的。特别之处在于：
1.需要你在无解情况下输出“No Solution!”。
2.要求你在有多种解的情况下输出字典序最小的一组。

先撇开这道题，看看没有这两点要求下的代码：

#include<bits/stdc++.h>
using namespace std;
#define maxn 101
int g[maxn][maxn];//二维数组进行链式储存
int du[maxn];//记录每个点的度，以便于最终判断奇点数目
int circuit[maxn];//记录欧拉路的路径
int n,e,circuitpos,i,j,x,y,start;
void find_circuit(int i)
{
    int j;
    for(j=1;j<=n;j++)
    if(g[i][j]==1){g[i][j]=g[j][i]=0;find_circuit(j);}//这个点搜寻完毕，标记搜寻后继续寻找以j为起点的剩下边
    circuit[++circuitpos]=i;//记录路径
}
int main()
{
    while(cin>>n>>e)
    {
        memset(g,0,sizeof g);memset(circuit,0,sizeof circuit);
        for(i=1;i<=e;i++){cin>>x>>y;g[x][y]=g[y][x]=1;du[x]++;du[y]++;}//无向，标记为1；代表可以连通即可;
        start=1;int tot=0;
        for(i=1;i<=n;i++)
            if(du[i]%2==1){
            start=i;//要么欧拉回路，从任一点开始；要么为奇点的时候就是起点或者终点，从其开始；
            tot++;
        }
        if(!(tot==2||tot==0)){cout<<"No Solution!"<<endl;continue;}
        circuitpos=0;
        find_circuit(start);//从起点开始遍历
        for(i=1;i<=circuitpos;i++)cout<<circuit[i]<<' ';
        cout<<endl;
    }
    return 0;
}

---

那么如何来解决这两个问题呢？

第一个问题其实好解决。
学过图论应该都知道（或者没学，现在跟你们来讲一下）：
对于能够一笔画的图，应该满足：
1.图连通，有且只有两个奇点（度为奇数的点），则存在欧拉路（不一定回到原点）。
2.图连通，且没有奇点，则存在欧拉回路（回原点）。
P:啥玩意是度？就是这一个点所连接的边的数目。
则我们在这里做出开始搜索的条件即可：

        tot=0;circuitpos=0;//tot计算奇点的数目，如果为0或者2，则进行搜索，否则直接输出无解
        for(i=1;i<=n;i++)
            if(du[i]%2)
            {
                if(tot==0)
                    start=i;//要么欧拉回路，从任一点开始；要么为奇点的时候就是起点或者终点，从其开始；
                tot++;
            }
        if(tot==2||tot==0)
        {
            find_circuit(start);//从起点开始遍历
            for(i=circuitpos-1;i>=1;i--)
                cout<<circuit[i]<<' ';
            cout<<circuit[i]<<endl;
        }
        else cout<<"No Solution!"<<endl;

---

再看看如何解决第二个问题？其实不难发现，我们进行搜索时，总是从满足条件，且序号最小的情况开始讨论。并且对于起点，若不是欧拉回路，则选取最先出现的点作为起点；若为欧拉回路（无论从那个点出发都能回）则从最小的1开始搜寻即可。

重点在于：

由于上图第一段代码中，是搜寻结束后进行的储存，故存放序列为反的，输出时需要逆序输出！！。AC代码如下：

#include<iostream>
#include<cstring>
using namespace std;
#define maxn 111
int g[maxn][maxn];//二维数组进行链式储存
int du[maxn];//记录每个点的度，以便于最终判断奇点数目
int circuit[maxn];//记录欧拉路的路径
int n,e,circuitpos;
void find_circuit(int i)
{
    int j;
    for(j=1;j<=n;j++)
        if(g[i][j])
        {
            g[i][j]=0;
            g[j][i]=0;
            find_circuit(j);
        }//这个点搜寻完毕，标记搜寻后继续寻找以j为起点的剩下边
    circuit[circuitpos]=i;//记录路径
    circuitpos++;
}
int main()
{
    while(cin>>n>>e)
    {
        int i,j,x,y,tot,start;
        start=1;
        memset(g,0,sizeof g);
        memset(du,0,sizeof du);
        memset(circuit,0,sizeof circuit);
        for(i=0;i<e;i++)
        {
            cin>>x>>y;
            g[x][y]=1;
            g[y][x]=1;
            du[x]++;du[y]++;
        }//无向，标记为1；代表可以连通即可;
        tot=0;circuitpos=0;
        for(i=1;i<=n;i++)
            if(du[i]%2)
            {
                if(tot==0)
                    start=i;//要么欧拉回路，从任一点开始；要么为奇点的时候就是起点或者终点，从其开始；
                tot++;
            }
        if(tot==2||tot==0)
        {
            find_circuit(start);//从起点开始遍历
            for(i=circuitpos-1;i>=1;i--)
                cout<<circuit[i]<<' ';
            cout<<circuit[i]<<endl;
        }
        else cout<<"No Solution!"<<endl;
    }
    return 0;
}

其实这里还有一个问题，就是搜索过程中，如果遇到死胡同了，搜索过的路径又已经标记为0，之后，不会再搜索，如何找出一条完整的路径？

![（这里点名表扬本校的某黄dalao指出这个问题，我才发现了这个题目的有趣之处，黄X牛逼！！！！！手动@黄X！）
举个例子来说明吧，如下：
如图，左侧是题目原图，右侧为我人工DEBUG得到的搜索边的顺序，我们发现，其实每次搜索完一个点后，不会立刻储存这个点，而是继续搜索，直到搜索完所有点，所有边后才会开始逆序储存。
然后我们看看图1，2：可得：最开始的搜索情况应该是点1->2->3->4->1；所以其实简化后发现，其余三个框框，全是1234延伸出来的路径（转一圈又回来了，点可以重复经过）故相当可以理解搜索路径为:于2延伸出8,9，10，然后返回，继续搜索3，同理3延伸出11,12，13，返回继续搜索4……(这是原定状况，事实上最先搜索4->1后最先存的是4的路径,所以倒过来存，如4之后存765，由于存放顺序是反的，故输出应该为从最后开始输出，为567)同理继续递推…

其实！！（这里我又要吹一波我们的某黄dalao了）

我们的黄大佬指出，这里其实可以看做是一个二叉树问题，该路段搜索完毕后返回节点继续搜索！！有兴趣可以自己debug看看！！黄X牛掰！

我也不知道我讲的清不清楚，如果还有问题可以留言评论~这里点名支持下黄X的博客，大家没关注的点个关注！！->https://blog.csdn.net/weixin_43890662