本文共 1653 字,大约阅读时间需要 5 分钟。
110 11 91 88 1010 38 61 210 49 53 7
-1 1 10 10 9 8 3 1 1 8
/********************************** 日期:2013-3-26* 作者:SJF0115* 题号: 题目20: 吝啬的国度* 来源:http://acm.nyist.net/JudgeOnline/problem.php?pid=20* 结果:AC* 来源:南阳理工OJ* 总结:**********************************/#include#include #include #include using namespace std;vector G[100001];int preCity[100001];int vis[100001];//深搜void DFS(int location){ vis[location] = 1; //访问与location相连的城市 for(int i = 0;i < G[location].size();i++){ int v = G[location][i]; if(!vis[v]){ //存储访问城市的上一站 preCity[v] = location; //printf("%d %d\n",location,v); DFS(v); } }} int main (){ int N,M,City,Location,a,b,i,first; //freopen("C:\\Users\\SJF\\Desktop\\acm.txt","r",stdin); scanf("%d",&N); while (N--){ scanf("%d %d",&City,&Location); //初始化 for(i = 1;i <= City;i++){ G[i].clear(); } //输入路径 for(i = 1;i < City;i++){ scanf("%d %d",&a,&b); G[a].push_back(b); G[b].push_back(a); } //访问城市 memset(vis,0,sizeof(vis)); vis[Location] = 1; preCity[Location] = -1; DFS(Location); //输出访问城市的上一站 first = 1; for(i = 1;i <= City;i++){ if(first){ first = 0; } else{ printf(" "); } printf("%d",preCity[i]); } printf("\n"); } return 0;}
转载地址:http://mucsi.baihongyu.com/