Graph类题目求解答

这道题大家会考虑怎么做呢，有没有什么类似的Leetcode题目推荐。。我感觉是bfs+backtracking,但是具体没想清楚！回答加米加米

AndreaYl 发表于 2022-8-11 18:23
感谢🙏！（今天加米到上限了，明天跟你补上）但我还有一个问题题目说可能会有多个长度相同的List， ...

不用，在更新的时候自定义比较就行，如果长度不一样选长的，长度一样选字典序小的

我想用dfs加memo。memo里记录的是这首歌后头最多可以跟多少首。

补充内容 (2022-08-12 05:58 +08:00):
抱歉没有想太明白。如果是要list的话，可能需要一个queue把所有的path的存起来，然后不断地增长这里头每一个path的两端，用memo的话可以减少重复搜索。我自己先写写看。

coolwenwen 发表于 2022-08-11 14:49:50
我想用dfs加memo。memo里记录的是这首歌后头最多可以跟多少首。

这个题目最后需要返回最长的list不是长度，那在我们找到最长的长度之后怎么得到最长的list呢，小白求教

这是个NP困难问题所以只能暴力。用回溯遍历整张图，开一个list记录当前的歌单，再搞一个全局变量记录最长的，如果当前歌单比已经记录的长则更新。

lyyc 发表于 2022-08-11 15:00:22
这是个NP困难问题所以只能暴力。用回溯遍历整张图，开一个list记录当前的歌单，再搞一个全局变量记录最长的，如果当前歌单比已经记录的长则更新。

感谢🙏！（今天加米到上限了，明天跟你补上）但我还有一个问题题目说可能会有多个长度相同的List，按照题目给的判断规则选择某个，那这样的话是只能先记下所有的最长，然后再筛选一遍吗？

请问这道题在哪能做，我有兴趣做一下这道题