spark 网站开发,域名备案信息查询官网,软件开发流程是哪几个,免费的云服务器有哪些活动 - AcWing
本题需要你实现prufer序列与无根树之间的相互转化。
假设本题涉及的无根树共有 n 个节点#xff0c;编号 1∼n。
为了更加简单明了的描述无根树的结构#xff0c;我们不妨在输入和输出时将该无根树描述为一个以 n 号节点为根的有根树。
这样就可以设这棵无…活动 - AcWing
本题需要你实现prufer序列与无根树之间的相互转化。
假设本题涉及的无根树共有 n 个节点编号 1∼n。
为了更加简单明了的描述无根树的结构我们不妨在输入和输出时将该无根树描述为一个以 n 号节点为根的有根树。
这样就可以设这棵无根树的父亲序列为 f1,f2,…,fn−1其中 fi 表示将该树看作以 n 号节点为根的有根树时i 号节点的父节点编号。
同时设这棵无根树的prufer序列为 p1,p2,…,pn−2。
现在给定一棵由 n 个节点构成的无根树以及该无根树的一个序列父亲序列或prufer序列请你求出另一个序列。
输入格式
输入共两行。
第一行包含两个整数 n,m表示无根树的节点数以及给定序列类型。
如果 m1则第二行包含 n−1 个整数表示给定序列为父亲序列。
如果 m2则第二行包含 n−2 个整数表示给定序列为prufer序列。
输出格式
共一行输出另一个序列整数之间用单个空格隔开。
数据范围
2≤n≤10^5
输入样例1
6 1
3 5 4 5 6输出样例1
3 5 4 5输入样例2
6 2
3 5 4 5输出样例2
3 5 4 5 6 解析
prufer编码主要作用即将一棵无根树转化为一个序列即prufer序列另外prufer序列也可以反过来转化为一棵树即prufer序列和树之间是一一对应的常用来解决一些证明问题如凯莱定理等 证明凯莱定理一个无向完全图有 n^(n−2 棵生成树由于prufer序列和树之间是一一对应的关系证明有多少棵不同的生成树即证明有多少种prufer序列显然prufer序列共有 n−2 项其范围为 1∼n故其种类数为 n^(n−2) prufer编码的流程假定 n 号节点为根找到除根外度数最小的节点在删除该节点之前将其父节点输出重复该流程直到最后只剩下两个节点即prufer序列只有 n−2 个元素因为prufer序列最多 n−1 个元素而最后一个元素一定为 n所以这个元素可以省略输出的元素即为prufer序列 如何将一棵树线性时间内转化为prufer序列
假定当前出度为 0 且编号最小的节点为 j则输出 f[j]删除 j 之后出度为 0 的节点至多只会增加一个即 f[j]判断删除 j 之后 f[j] 的出度是否为 0如果 f[j] 的出度为 0 且 f[j]j 说明 f[j] 是当前出度为 0 且编号最小的节点递归输出这样的父节点即可否则说明这样的 j 只会更大即 j 只会增加这样即可线性时间内将一颗树转化为prufer序列
如何将一个prufer序列转化为一棵树
先将 n 这个节点加入到prufer序列中不难发现prufer序列中某个数出现的次数即为该数在树中的儿子节点的数量从 1 开始找到儿子数量为 0 且编号最小的节点 j其父节点即为当前遍历的prufer序列的元素将该元素从prufer序列中删去因为删除该元素后儿子数量为 0 的节点数量至多直接增加一个如果该元素的儿子数量为 0 且编号小于 j说明当前节点即为儿子数量为 0 且编号最小的节点递归处理即可这样的 j 同样也是递增的故可以在线性时间内将一个prufer序列转化为一棵树
时间复杂度O(n)
#includeiostream
#includestring
#includecstring
#includecmath
#includectime
#includealgorithm
#includeutility
#includestack
#includequeue
#includevector
#includeset
#includemath.h
#includemap
#includesstream
#includedeque
#includeunordered_map
#includeunordered_set
#includebitset
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pairint, int PII;
typedef pairdouble, double PDD;
const int N 1e5 10, M 1e4 10;
const double INF 1e8;
int n, m;
int f[N], d[N], p[N];void tree2prufer() {for (int i 1; i n; i) {scanf(%d, f[i]);d[f[i]];}for (int i 1, j 1; i n - 1; j) {while (d[j])j;p[i] f[j];while (i n - 1 --d [p[i-1]] 0 p[i - 1] j)p[i] f[p[i - 1]];}for (int i 1; i n-1; i) {printf(%d , p[i]);}
}void prufer2tree() {for (int i 1; i n-2; i) {scanf(%d, p[i]);d[p[i]];}p[n - 1] n;for (int i 1, j 1; i n; j, i) {while (d[j])j;f[j] p[i];while (i n --d[p[i]] 0 p[i] j)f[p[i]] p[i 1], i;}for (int i 1; i n; i) {printf(%d , f[i]);}
}int main() {cin n m;if (m 1)tree2prufer();else prufer2tree();return 0;
}
