题目1531: 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 question 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.
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
*** 提示已隐藏,点击上方 [+] 可显示 ***
2013年浙江大学复试机试模拟题
/********************************** 日期:2013-3-23* 作者:SJF0115* 题号: 题目1531: One Day Tour In ZJU* 来源:http://acmclub.com/problem.php?id=1531* 结果:AC* 来源:2013年浙江大学复试机试模拟题* 总结:**********************************/#include<stdio.h>#include<string.h>int n,m,ok;int vis[22],Map[22][22];//搜索,已经访问count个地方现在处于location点void DFS(int location,int count){int i;//已经全部访问完if(count == n){//到达目的地nif(location == n){ok = 1;}return;}//没有访问完,访问下一处for(i = 1;i <= n;i++){//i点没访问过且能访问则去i点if(Map[location][i] == 1&& vis[i] == 0){//标记i已经访问过vis[i]=1;//递归下一处DFS(i,count+1);if(ok == 1){return;}//取消标记vis[i] = 0;}}}//初始化void Init(){int i,j,start,end;//初始化地图for(i = 1;i <= n;i++){for(j = 1;j <= n;j++){Map[i][j]=0;}}//添加路况for(i = 0;i < m;i++){scanf("%d %d",&start,&end);//end和start之间联通Map[start][end]=1;Map[end][start]=1;}memset(vis,0,sizeof(vis));ok = 0;//1为出发点vis[1]=1;}int main(){while(scanf("%d %d",&n,&m)!=EOF){Init();DFS(1,1); printf("%d\n",ok);}return 0;}