UC知道神秘国度的爱情故事 (c语言)
来源：百度知道 编辑：UC知道 时间：2024/06/08 08:26:13
题目：某个太空神秘国度中有很多美丽的小村，从太空中可以望见，小村间有路相连，更精确点说，任意两村之间有且仅有一条路径。
小村A中有位年轻人爱上了自己村里美丽姑娘。每天早晨，姑娘都要去小村B里的面包房工作，傍晚6点回家。年轻人终于决定要向姑娘表白，他打算在小村C等着姑娘路过的时候把爱慕说出来。问题是，他不能确定小村C是否在小村B到小村A之间的路径上。你可帮助他解决这个问题吗
Input
I
8 20 1
4 5 1
10 11 1
12 10 1
18 14 1
Q
8 10 5 15
8 20 10 14
I
7 6 1
10 3 2
7 2 1
2 3 2
10 3 1
Q
2 20 2 20
E
Output
1
3
12
数据给错了
input
3
0 1
1 2
3
0 2 1
1 2 0
1 2 1
0
output
Yes
No
Yes
用遍历的话时间太废了
所以我们要用深度优先搜索树
问题 该怎么建立这么一棵树呢？
PS：LCA不会求
小村A中有位年轻人爱上了自己村里美丽姑娘。每天早晨，姑娘都要去小村B里的面包房工作，傍晚6点回家。年轻人终于决定要向姑娘表白，他打算在小村C等着姑娘路过的时候把爱慕说出来。问题是，他不能确定小村C是否在小村B到小村A之间的路径上。你可帮助他解决这个问题吗
Input
I
8 20 1
4 5 1
10 11 1
12 10 1
18 14 1
Q
8 10 5 15
8 20 10 14
I
7 6 1
10 3 2
7 2 1
2 3 2
10 3 1
Q
2 20 2 20
E
Output
1
3
12
数据给错了
input
3
0 1
1 2
3
0 2 1
1 2 0
1 2 1
0
output
Yes
No
Yes
用遍历的话时间太废了
所以我们要用深度优先搜索树
问题 该怎么建立这么一棵树呢？
PS：LCA不会求
典型的最近公共祖先(lca)问题
对每个询问,假设A和B的lca是D,判断一下C是否在AD或BD上即可
ps
你去搜"lowest common ancestor"或者"nearest common ancestor"会出来很多东西的
这么经典的内容建议你还是自己找资料认真学学
用循环单链表，
设一个头指针，指向循环单链表的一个结点作为入口，
遍历链表，如找到表示C的值，就是能等到，
你给出的数据看不明白