nyoj20_吝啬的国度_DFS
吝啬的国度
时间限制： 1000 ms | 内存限制：65535 KB
难度： 3
每组测试数据的第一行输入一个正整数N(1<=N<=100000)和一个正整数S(1<=S<=100000)，N表示城市的总个数，S表示参观者所在城市的编号
随后的N-1行，每行有两个正整数a,b(1<=a,b<=N)，表示第a号城市和第b号城市之间有一条路连通。 </dd> <dt> 输出 </dt> <dd> 每组测试数据输N个正整数，其中，第i个数表示从S走到i号城市，必须要经过的上一个城市的编号。（其中i=S时，请输出-1） </dd> <dt> 样例输入 </dt> <dd>
1 10 1 1 9 1 8 8 10 10 3 8 6 1 2 10 4 9 5 3 7</dd> <dt> 样例输出 </dt> <dd>
-1 1 10 10 9 8 3 1 1 8</dd> </dl>
解题思路：好像是做的第一个图论的题，但感觉dfs函数理解的还是不透彻，还得继续看！
#include <iostream> #include <cstdio> #include <cstring> #include <vector> using namespace std; vector<int> v[100005]; int pre[100005]; void dfs(int s){ for(int i=0;i<v[s].size();i++){ if(pre[v[s][i]]) continue; pre[v[s][i]]=s; dfs(v[s][i]); } } int main() { int m; int n,s; int a,b; scanf("%d",&m); while(m--){ memset(v,0,sizeof(v)); memset(pre,0,sizeof(pre)); scanf("%d %d",&n,&s); pre[s]=-1; for(int i=0;i<n-1;i++){ scanf("%d %d",&a,&b); v[a].push_back(b); v[b].push_back(a); } dfs(s); for(int i=1;i<=n;i++){ if(i<n){ printf("%d ",pre[i]); }else{ printf("%d\n",pre[i]); } } } return 0; }
