NYOJ20：吝啬的国度-图的DFS算法解析

### NYOJ20：吝啬的国度 #### 内存限制: 64MB #### 时间限制: 1000ms #### 特判: No #### 难度: 3 在一个吝啬的国度里有N个城市，这N个城市间只有N-1条路将这些城市连接起来。Tom位于第S号城市，他有一张该国的地图，想要知道从S号城市前往T号城市时，必须经过的前一个城市是哪个（假设不走重复的路）。 #### 输入描述: 第一行输入一个整数M，表示测试数据的组数（1 <= M <= 5）。每组测试数据的第一行包含两个正整数N和S（1 <= N, S <= 100000），分别表示城市的总数和Tom所在的城市的编号。接下来的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 ``` #### 分析: 由于有n个点且只有(n-1)条边将它们全部连通，因此不存在环。题目要求找到到达某个点的前一个点，即目的地的上一个必经点。不走重复的路意味着可以使用深度优先搜索（DFS）来解决这个问题。 #### 代码实现: ```cpp #include #include #include using namespace std; const int MAXN = 100005; int ans[MAXN]; vector vec[MAXN]; void dfs(int s) { int lens = vec[s].size(); for (int i = 0; i > t; while (t--) { memset(ans, 0, sizeof(ans)); for (int i = 1; i <= 100000; i++) { vec[i].clear(); } int n, s; cin >> n >> s; for (int i = 1; i > a >> b; vec[a].push_back(b); vec[b].push_back(a); } dfs(s); ans[s] = -1; for (int i = 1; i <= n; i++) { cout <