Nyoj-20 吝啬的國度

吝啬的國度

描述

在一個吝啬的國度裡有N個城市，這N個城市間只有N-1條路把這個N個城市連接起來。現在，Tom在第S號城市，他有張該國地圖，他想知道如果自己要去參觀第T號城市，必須經過的前一個城市是幾號城市（假設你不走重復的路）。

輸入

第一行輸入一個整數M表示測試數據共有M(1<=M<=5)組
每組測試數據的第一行輸入一個正整數N(1<=N<=100000)和一個正整數S(1<=S<=100000)，N表示城市的總個數，S表示參觀者所在城市的編號
隨後的N-1行，每行有兩個正整數a,b(1<=a,b<=N)，表示第a號城市和第b號城市之間有一條路連通。

輸出

每組測試數據輸N個正整數，其中，第i個數表示從S走到i號城市，必須要經過的上一個城市的編號。（其中i=S時，請輸出-1）

樣例輸入

1
10 1
1 9
1 8
8 10
10 3
8 6
1 2
10 4
9 5
3 7

樣例輸出

-1 1 10 10 9 8 3 1 1 8

主要就是用到dfs搜索，圖的建立要用鄰接表，矩陣貌似建不了那麼大的

圖建立好了之後，將輸入的起始點作為根節點，即可得到一棵生成樹，從根節點開始搜索，

建立一個int ans[100005]數組來存儲答案

比如當前在節點3，3的下面有三個字節點6、8、9，那麼就可以把ans[6]=ans[8]=ans[9]=3

就這樣遍歷，如果當前節點沒有子節就返回，最後循環結束返回，答案也就出來了

需要注意的是不要忘了標記一下已經訪問過的節點，因為是無向圖，不標記的話會死循環

還有一點，用vector來建立圖，不論是建立、訪問、操作還是程序清晰度都會有極大改善，

而且可以大大降低出錯的可能性

以後有時間的話打算總結一下stl的使用技巧；

最後是本題的代碼：

#include
#include
#include
#include
#include
#include

using namespace std;

vector map[100005];	//建立100005個頭節點
int ans[100005];
bool vis[100005];
int n;

int f(int beg)
{
	if(map[beg].size()==0)	return 0;	//如果當前節點沒有子節點
	vis[beg]=true;
	for(int i=0;i!=map[beg].size();++i)//遍歷當前節點的所有子節點並處理
	{
		if(vis[map[beg][i]])	continue;//如果該子節點已經處理過（重要！不加會死循環
		ans[map[beg][i]]=beg;
		f(map[beg][i]);
	}
	return 0;
}

int main()
{
	int num,root;
	scanf("%d",&num);
	while(num--!=0)
	{
		scanf("%d%d",&n,&root);
		for(int i=1;i<=n;++i)//將容器初始化
		{
			map[i].clear();
		}
		for(int i=1;i!=n;++i)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			map[a].push_back(b);//添加關系
			map[b].push_back(a);
		}
		memset(ans,0,sizeof(ans));//初始化記錄數組
		memset(vis,0,sizeof(vis));
		ans[root]=-1;
		f(root);
		printf("%d",ans[1]);//輸出結果
		for(int i=2;i<=n;++i)
		{
			printf(" %d",ans[i]);
		}
		printf("\n");
	}
	return 0;
}