1021. Deepest Root DFS 求最长无环路径

第一次出现超时 ac不了的题

思路一:对于每个节点用一次dfs

dfs中 记录到当前的最长路径,若大于最长,则清除set,并加入当前节点

思路二:先查找只有一个相邻节点的节点进行dfs,由于可能存在闭环,对为访问的节点dfs

思路三:(TQL),大神思路,先以1节点为根用一次dfs(1),求出以1为根的最深点集合,并且完成深度搜索一次,可以知道是否还有不可达点,

    如果还有没访问,继续遍历,可以的到连通分量数。

    如果大于1,直接打印错误信息

    否则,对最深点集合的其中一个进行dfs 即为答案。

    //【精髓】第一次dfs 的求的点虽然不是全局深度最深的,但最深点集合必定包含这些点,

    思路二,只有在 单邻居的节点数 小于2的情况下和思路三性能相当

对于二维数组

int a[][]

vector<int> a[]

vector<vector<int>> a

三种方式,在存储图(顶点数较多的情况下)的时候

访问速度依次变慢,所占空间依次缩小

原文地址:https://www.cnblogs.com/mgfsos/p/10599455.html