本文共 1374 字，大约阅读时间需要 4 分钟。

Description

有一个地下迷宫，它的通道都是直的，而通道所有交叉点(包括通道的端点)上都有一盏灯和一个开关；请问如何从某个起点开始在迷宫中点亮所有的灯并回到起点？

Input

连续T组数据输入，每组数据第一行给出三个正整数，分别表示地下迷宫的结点数N(1 < N <= 1000)、边数M(M <= 3000)和起始结点编号S，随后M行对应M条边，每行给出一对正整数，表示一条边相关联的两个顶点的编号。

Output

若可以点亮所有结点的灯，则输出从S开始并以S结束的序列，序列中相邻的顶点一定有边，否则只输出部分点亮的灯的结点序列，最后输出0，表示此迷宫不是连通图。

Sample

Input

16 8 11 22 33 44 55 66 43 61 5

Output

1 2 3 4 5 6 5 4 3 2 1

答案：

#include 
   
    #include
    
     #define PI 3.1415926#define ll long long#define pb push_backconst int inf=0x3f3f3f3f;const int N =  1e5 + 10;using namespace std;int mp[1111][1111];int dp[1111];int vis[1111];int n;int cnt;void dfs(int k){       if(cnt!=1)        printf(" ");    printf("%d",k);    for(int i=1; i<=n; i++)    {           if(vis[i]!=1&&mp[k][i])        {               vis[i] = 1;            cnt++;            dfs(i);            printf(" %d",k);        }    }}int main(){       ios::sync_with_stdio(false);    int t;    cin>>t;    while(t--)    {           memset(vis,0,sizeof(vis));        memset(mp,0,sizeof(mp));        memset(dp,0,sizeof(dp));        int m,k;        cin>>n>>m>>k;        while(m--)        {               int x,y;            cin>>x>>y;            mp[x][y]=mp[y][x]=1;        }        cnt=1;        vis[k]=1;        dfs(k);        if(cnt==n)            printf("\n");        else            printf(" 0\n");    }    return 0;}