狗家店面，只问了一道题，但是有follow up。
第一个问题很简单，就是一个无向向无环图求最长路径
第二个问题是第一个问题的follow up，如果有多个无向无环图，并且每一个图的最长路径已知。现在把这些图连起来，求连接起来的这个图的最长路径。
第三个问题：如果改成有向无环图呢？
补充内容 (2018-10-24 12:01):
无向无环图，打错了
补充内容 (2018-10-24 21:11):
第二问是指对于两个图，各取一点，然后把这两点连接，就相当于把这两个图连接了起来。
1 Like
第三问在有向无环图（DAG）中求最长路径（又叫做关键路径，critical path）是一个经典问题，做法是拓扑排序+动态规划
首先对原图做一些处理：
(1) 每条边权值（weight）设为1
(2) 考虑到题目中起点和终点不固定，不妨设原图的源点集合（即入度为0的点）为S，汇点集合（即出度为0的点）为T；然后添加额外的两个点s和t，并从s连一条权值为0的边到S中每个点，从T中每个点连一条权值为0的边到t
现在求s到t的关键路径即可，可以参考下面一些链接里的介绍：
无向无环图中的最长路径也是比较经典的问题：
- 选择一点作为树根root，深搜找到离树根最远的点A
- 从点A开始深搜，搜到的最远的点就是图中最长路径
分情况讨论： - 如果root在最长路径上，肯定会搜到最长路径两端点中的一个，反证法很容易
- 如果root不在最长路径上，且假设最长路径为CD，那么可知distance(root, c) < distance(root, A) and distancd(root, d) < distance(root, A)
但是这样的话，distance(A, C) = distance(root, A) + distance(root, C) > distance(root, D) + distance(root, C) > distance(C, D)
所以AC之间路径比CD更长，和假设矛盾（其实上面的证明还需要加强，比如root到C与root到D的路径至少一条不会和root到A的重合等）
这里最关键的一点在于，在无向无环图中，或者一棵树中，两点之间的路径唯一。
1.无向无环图=树，任取一点味根，对树做dfs，递归地返回每个子树的根到叶子的最长路径值，并通过这个信息维护最长路径，如 L 为左子树的返回值， R为右子树返回值，则用L+R+1更新最长路，并返回max(L,R)+1。
2.连接是啥子意思哦····
3.每次找入度为0的点开始做dfs，直到没有入度为0的点为止，维护最长路值
请问第二第三问怎么答？
第一個問題是不是類似哩叩五四三
題目是要印出最長的路徑，還是找出最長路徑的值就好?
但這棵樹不一定是 binary tree 吧? 所以光是用 L 和 R 應該不夠
是的，那就维护Len1+Len2+1, 返回max(len)+1，len1 len2 是最长的两个子树的返回值。
第二问是指对于两个图，各取一点，然后把这两点连接，就相当于把这两个图连接了起来。
第二问，如果只有两个图的话，如图a和图b，可以先求出从连接的那个点在这个图a的最长路径，记为len_a, 同理找出len_b。找出图a和图b的最长路径，记为max_a, max_b。则最长路径为max(max_a, max_b, len_a+len_b). 但是k个图的没想出来，k>2.
补充内容 (2018-10-24 21:26):
应该是max(max_a, max_b, len_a+len_b+1)，因为这两个点用一根额外的线连接起来