| 题目名称 | 1642. 无根树转有根树 |
|---|---|
| 输入输出 | wgs.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 6 |
| 题目来源 |
 cqw
于2014-05-24加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：64， 提交：110， 通过率：58.18% | ||||
 Pine |
100 | 0.235 s | 15.54 MiB | C++ |
 Albert S. Chang |
100 | 0.262 s | 25.74 MiB | C++ |
 HeHe |
100 | 0.270 s | 9.94 MiB | C++ |
|
HeHe |
100 | 0.271 s | 9.40 MiB | C++ |
 rvalue |
100 | 0.275 s | 19.22 MiB | C++ |
 dxd |
100 | 0.282 s | 23.20 MiB | C++ |
 CSU_Turkey |
100 | 0.403 s | 13.17 MiB | C++ |
|
CSU_Turkey |
100 | 0.422 s | 15.57 MiB | C++ |
 Fisher. |
100 | 0.422 s | 19.39 MiB | C++ |
|
CSU_Turkey |
100 | 0.423 s | 15.57 MiB | C++ |
| 本题关联比赛 | |||
| 至少完成十道练习 | |||
| 图论练习和一些常规题 | |||
| 图论练习和一些常规题 | |||
| 关于 无根树转有根树 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
裸的BFS
也可以用DFS --------------------- 时隔很久重写一遍。。。。 第一次快速输出写炸了。。 第二次忘记删除调试输出了。。。 。。。。。。。 | ||||
|
简直瀑布
 YGOI_真神名曰驴蛋蛋
2016-09-11 16:35
2楼
| ||||
|
好水...
| ||||
raywzy【题目描述】
输入一个n个结点的无根树的各条边，并指定一个根结点，要求把该树转化为有根树，输出各个结点的父亲编号。n≤10^6，如图所示。
【输入格式】
第1行：两个空格隔开的整数n，u；n是树的节点数，u是根节点编号。
第2～n行：每行包含二个整数X,Y，表示节点X，节点Y之间有边。（节点编号从0开始）
第n+1行，一个整数m
第n+2行，m个用空格隔开的整数，表示需要输出父亲的结点编号。
【输出格式】
一行，m个用一个空格隔开的整数，为m个节点的父亲编号。
【样例输入】
8 1 0 1 0 2 0 3 1 4 1 5 5 6 5 7 8 0 1 2 3 4 5 6 7
【样例输出】
1 -1 0 0 1 1 5 5
【提示】
1号节点没有父亲，输出-1。
【来源】
《算法竞赛入门经典（第2版）》第11章例题