一笔画问题

Description

Input

Output

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

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

Sample Input

Sample Output

1 2 3 1

1 2 3 4 5 1

分析：当图中奇度数的节点不为0或2个的时候，就不存在一笔画。反之，如果存在的话可以用深搜找到路径。

参考代码：

#include<cstdio>#include<cstdlib>#include<cmath>#include<cstring>#include<string>#include<algorithm>#include<stack>#include<queue>#include<map>#include<iostream> using namespace std;const int maxn = 100+10;int n,m;//n个顶点 m条边int g[maxn][maxn];int ans[maxn];int len; void Search( int x){    for( int i = 1; i <= n; i++)    {        //PRintf("%d*/n",g[x][i]);        if( g[x][i])        {            g[x][i] = 0;            g[i][x] = 0;            Search(i);        }    }    ans[len++] = x; } int main(){    while( ~scanf("%d%d",&n,&m))    {        memset(g,0,sizeof(g));        int u,v;        for( int i = 1; i <= m; i++)        {            scanf("%d%d",&u,&v);            g[u][v] = 1;            g[v][u] = 1;        }         /*for( int i = 1; i <= n; i++)        {            for( int j = 1; j <= n; j++)                printf("%d ",g[i][j]);            putchar(10);        }*/         int in;        int cnt = 0;        int start = 1;        for( int i = 1; i <= n; i++)        {            in = 0;            for( int j = 1; j <= n; j++)            {                if( g[i][j])                    in++;            }            if( in%2)//度为奇数            {                if( cnt == 0)                    start = i;                cnt++;            }        }         if( cnt == 0 || cnt == 2)//度为奇数的结点数大于2        {            len = 0;            Search( start);            for( int i = len-1; i > 0; i--)                printf("%d ",ans[i]);            printf("%d/n",ans[0]);        }        else            printf("No Solution!/n");    }     return 0;}