本文主要是介绍nyoj20 吝啬的国度 (无根树转换为实根树),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
吝啬的国度
- 描述
- 在一个吝啬的国度里有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
来源 - 经典题目 上传者
张云聪
#include <stdio.h> #include <string.h> #include <vector> using namespace std; #define N 100005 int tree[N]; vector<int>map[N]; void ChangeTree(int root,int flag) {for(int i=0;i<map[root].size();i++){if(map[root][i]!=flag){tree[map[root][i]]=root;//保存根节点ChangeTree(map[root][i],root);//从树根一搜到底。}} } int main() {int test,n,root,x,y;scanf("%d",&test);while(test--){memset(map,0,sizeof(map));scanf("%d %d",&n,&root);for(int i=0;i<n-1;i++){scanf("%d %d",&x,&y);map[x].push_back(y);map[y].push_back(x);}tree[root]=-1;ChangeTree(root,-1);for(int i=1;i<n;i++)printf("%d ",tree[i]);printf("%d\n",tree[n]);}return 0; }
我也是今天刚刚理解的,给大家说一下我理解过程中遇到的问题。其实在做图论题之前学长让我看书,我不是那种爱看书的。。我喜欢在题目中发现问题,然后上网看书,解决。这就是我的学习方式。
vector容器,第一次用到。理解vector数组好理解,可是不知道为什么变成二维数组了。其中map[i][j]可能比较难懂。
例子:map[1]=2,map[1]=3,map[1]=4;那么map[1][0]就等于1,map[1][1]=3,map[1][2]=4.而且map[1].size()=3;(因为map[1]只有2,3,4三个值);
第二个不懂的地方就是无根树转换为实根树了,我自己写了个例子,然后根据程序慢慢推,就懂了。。希望你也能自己动手试试、、
对了,算法只要理解了思想,那么程序就很容易写出来了。
- 第一行输入一个整数M表示测试数据共有M(1<=M<=5)组
这篇关于nyoj20 吝啬的国度 (无根树转换为实根树)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!