4021 - 邮递员
Time Limit : 1 秒
Memory Limit : 128 MB
邮递员在送信时，为了节省路途，自己规定：每次总是从n个村子中选择其中一个合适的村子出发，途中每个村子仅且经过一次，送完所有的信。已知各个村子的道路连通情况（如图所示）。请你帮邮递员选择一条合适的路线，假设每次选择村子（包括出发的村子）时优先选择序号最小的村子。
Input
第一行：整数n：村子的个数，n<=30。
接下来是一个n*n的0、1矩阵，表示n个村子的连同情况，如：a[i,j]=1 ，表示第i和第j个村子之间有路可走，如果a[i,j]=0，表示他们之间无路可走。
Output
一条可行的路线；如果不存在可行的线路，输出“no round”（引号不需输出）。
Examples
Input Format
7 0 1 0 1 1 0 0 1 0 1 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 1 0 0 1 0
Output Format
2 3 7 6 5 1 4
Solution C
#include<stdio.h> #include<stdlib.h> int a[101][101],v[101],d[101]; int n,f; void dfs(int i,int k){ int j; v[i]=1; d[k]=i; if (k==n) f=1; for (j=1;j<=n;j++) if (f==0&&v[j]==0 &&a[i][j]==1) dfs(j,k+1); v[i]=0; } int main(){ int i,j; scanf("%d",&n); for (i=1;i<=n;i++) for (j=1;j<=n;j++) scanf("%d",&a[i][j]); for (i=1;i<=n;i++) if (f==0&&v[i]==0) dfs(i,1); if (f) { for (i=1;i<=n;i++) if (i==1) printf("%d",d[i]); else printf(" %d",d[i]); printf("\n"); } else printf("no round\n"); return 0; }