1680 - One Day Tour In ZJU
Xiao Ming's parents visit ZJU and Xiao Ming want to take them to look around the campus.They will start from the stone with two famous questions raised by President Zhu Kezhen and end at largest dining room in Asia.They want to visit every place exactly once in ZJU's campus,including the stone and dining room.
题目输入
The input consists of multiple test cases.
The first line contains an integer n(n<=20),which means the number of place in ZJU's campus.We give numbers(from 1 to n) to the places,especailly,1 means the stone with two famous question and n means the largest dining room.
The second line contains an integer m,which means the number of roads between two place.
Then follows m lines,each line contain two integer,which means there is a road between these two place.The road will not repeat more than one time.
题目输出
For each test case, you should output one line.If the path exists,you should output 1.Otherwise,you should output 0.
输入/输出样例
题目输入
5 4 1 2 1 3 1 4 2 5 6 6 1 3 3 2 1 2 3 4 4 5 5 6
题目输出
0 1
C语言解答
#include <stdio.h> #include <stdlib.h> #include <string.h> int G[25][25]; int vis[25]; int n, m; int flag; int isok(){ for(int i = 1;i < n; i++){ if(vis[i]==0)return 0; } return 1; } void dfs(int u){ if(u == n){ if(isok())flag = 1; return; } if(vis[u]==1)return; vis[u] = 1; for(int v = 1;v <= n; v++){ if(vis[v]==0 && G[u][v] == 1){ dfs(v); } if(flag)return; } vis[u] = 0; } int main() { while(scanf("%d",&n) != EOF){ scanf("%d",&m); memset(G,0,sizeof(G)); memset(vis,0,sizeof(vis)); while(m--){ int a, b; scanf("%d%d",&a,&b); G[a][b] = G[b][a] = 1; } flag = 0; dfs(1); printf("%d\n",flag); } return 0; }
C++解答
#include <stdio.h> int n,m,ok,b[22],a[22][22];//a代表各地之间的连接情况，b代表某点是否去过 void find(int last,int t)//搜索，已经走过t个地方，最后处于last { int i; if(t==n) { if(last==n)//只有去过n个地方并且最后处于n才是ok的 ok=1; return; } for(i=1;i<=n;i++)//搜索下一个要去的地方 if(a[i][last]==1&&b[i]==0)//下一个去i { b[i]=1;//标记i已经去过 find(i,t+1);//递归 if(ok==1) return; b[i]=0;//取消标记 } } void run() { int i,j,k; for(i=1;i<=n;i++)//重置地图 for(j=1;j<=n;j++) a[i][j]=0; for(i=0;i<m;i++)//读取路的信息，写入地图 { scanf("%d%d",&j,&k); a[j][k]=1; a[k][j]=1; } for(i=1;i<=n;i++)//所有地方都没去过 b[i]=0; ok=0; b[1]=1;//在1出发 find(1,1);//已经去过1，最后处于1，开始搜索 printf("%d\n",ok); } int main() { while(scanf("%d%d",&n,&m)!=EOF) run(); return 0; }