博客

//摘取题目

题目描述

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

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

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

输入

第1行：1个整数n，表示图的顶点数(n<=100)

接下来n行，每行n个数，表示图的邻接矩阵

输出

第1行：一笔画的先后顺序，每个顶点之间用一个空格分开

样例输入 Copy

样例一

3

0 1 1

1 0 1

1 1 0

样例二：

7

0 1 0 1 1 0 1

1 0 1 0 0 0 0

0 1 0 1 0 0 0

1 0 1 0 0 0 0

1 0 0 0 0 1 0

0 0 0 0 1 0 1

1 0 0 0 0 1 0

样例输出 Copy

样例一：

1 2 3 1

样例二：

1 2 3 4 1 5 6 7 1

//

首先要知道，图中点的度都为偶数或有两个点为奇数时肯定可以一笔画完，否则不行；

然后找路径:

先是找最小的起点，之后用递归找到一个后，就去找它的边，有符合的边就把它从图中删去，然后递归该边的第二个点，只要有最优解，就会返回，在返回时将点序号存入数组，最后需倒序输出即可。

接下来，我奉上拙作；

没有考虑很特殊的请况，大家可以自己去想想(⊙o⊙)哦

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,k,sum,s[100001];
bool map[201][201];
void fid(int x)
{
    for(int i=1;i<=n;i++)
    {
        if(map[x][i])
        {
            map[i][x]=map[x][i]=false;
            fid(i);
        }
    }
    s[k++]=x;
}
int main()
{
    //freopen("1.txt","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&map[i][j]);
            s[i]+=map[i][j];
        }//cout<<s[i]%2<<" "<<i<<endl;//cout<<s[i]<<" ";
        if(s[i]%2==1)
        {
            if(sum==0) sum=i;//只在第一次更换，这样才是最小字典序 
            k++;
        }
    }
    if(!sum) sum++;
    if(k!=0&&k!=2) printf("No Solution!");
    else
    {
        memset(s,0,sizeof(s));
        k=0;
        fid(sum);
        for(int i=k-1;i>0;i--)
        {
            printf("%d ",s[i]);
        }
        printf("%d",s[0]);
    }
    return 0;
}