第一次出现超时 ac不了的题
思路一:对于每个节点用一次dfs
dfs中 记录到当前的最长路径,若大于最长,则清除set,并加入当前节点
思路二:先查找只有一个相邻节点的节点进行dfs,由于可能存在闭环,对为访问的节点dfs
思路三:(TQL),大神思路,先以1节点为根用一次dfs(1),求出以1为根的最深点集合,并且完成深度搜索一次,可以知道是否还有不可达点,
如果还有没访问,继续遍历,可以的到连通分量数。
如果大于1,直接打印错误信息
否则,对最深点集合的其中一个进行dfs 即为答案。
//【精髓】第一次dfs 的求的点虽然不是全局深度最深的,但最深点集合必定包含这些点,
思路二,只有在 单邻居的节点数 小于2的情况下和思路三性能相当
对于二维数组
int a[][]
vector<int> a[]
vector<vector<int>> a
三种方式,在存储图(顶点数较多的情况下)的时候
访问速度依次变慢,所占空间依次缩小