吝啬的国度 时间限制：1000 ms | 内存限制：65535 KB 难度：3描述在一个吝啬的国度里有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） 样例输入110 11 91 88 1010 38 61 210 49 53 7样例输出-1 1 10 10 9 8 3 1 1 8
第一次刷图论，对存储什么的还不熟悉，这题用邻接矩阵太大，邻接表不知道怎么弄，还好vector来存可以节省很多空间。
n-1条边可以认为它是一个连通无环图，一棵树。
无根树转有根树。
深搜，用一个p数组存数每一步的父结点，visit存储该结点是否访问。
不过最后我vector没有清空，wrong answer了。
#include <iostream> #include <cstring> #include <vector>using namespace std;const int Max = 100001; int p[Max]; int visit[Max]; vector<int> a[Max];void dfs(int s) {//cout << s<< '[';visit[s] = 1;for(int i = 0 ; i < a[s].size(); i++)if(a[s][i]&&!visit[a[s][i]]){//cout << '!'; p[a[s][i]] = s; dfs(a[s][i]);}} int main() {int num,n,s;int x,y;cin >> num ;while(num--){memset(p,-1,sizeof(p));memset(visit,0,sizeof(visit));cin >> n >> s;for(int i = 0; i < n-1; i++){cin >> x >> y;a[x].push_back(y);a[y].push_back(x);} dfs(s); for(int i = 1; i <= n; i++){cout <<p[i] << ' ' ;a[i].clear();}cout << endl;}system("pause");return 0; }
