最大环最长链
https://www.cnblogs.com/lfri/p/15758120.html
最大环是针对的是出度为1的图，否则会多环重合。 等价于n个点上有n条边。也叫基环树，它的标准定义是：具有N个点N条边的连通图。
最长链是无环的图，求一个最长路径的长度。
最大环
有向图
题目： 2127. 参加会议的最多员工数
限制： 每个节点出度为1，n个节点n条边。
有多种方法：
- 一种是先用拓扑排序将外链去掉，再dfs每一个环
- DFS: 另一种是从某一点出发，记录途径的点，如果遇到已经访问过的点，说明找到了环的入口。减去起始点到入口的距离，就是环的长度。
- 还有一种有并查集，对于
x->y，如果x和y同属于一个集合，说明形成了一个环。
dfs代码
class Solution:
def longestCycle(self, edges: List[int]) -> int:
n = len(edges)
vis = collections.defaultdict(bool)
ans = -1
for i in range(n):
if vis[i]: continue
path = []
cur = i
while not vis[cur]:
vis[cur] = True
path.append(cur)
cur = edges[cur]
if cur == -1: break
if cur == -1: continue
for j in range(len(path)):
if path[j] == cur:
t = len(path) - j
ans = max(ans, t)
break
return ans
有向图的所有环
class Solution:
def longestCycle(self, edges: List[int]) -> int:
n = len(edges)
vis = collections.defaultdict(bool)
ans = -1
for i in range(n):
if vis[i]: continue
path = []
cur = i
while not vis[cur]:
vis[cur] = True
path.append(cur)
cur = edges[cur]
if cur == -1: break
if cur == -1: continue
for j in range(len(path)):
if path[j] == cur:
t = len(path) - j
ans = max(ans, t)
# print(path) self.start就是所有的环。
self.start.append(path[j:])
break
return ans
无向图
和有向图类似，略
最长链
等价问题： 310. 最小高度树
有向无环图
这里有一个很重要的问题，有环怎么办？ 有环的情况下，求最长链是没有意义的。要么保证无环，要么是求连接到环上的链的长度。 例如求连接到环上的链的长度，需要从入度为0的节点开始，递推计算，于是采用拓扑序。
int TopologicalSort(vector<int>& favorite) {
int n = favorite.size();
vector<bool> vis(n, false);
vector<int>in(n, 0);
vector<int>dp(n, 1);
queue<int> q;
for(int i = 0;i < n;i++) in[favorite[i]]++;
for(int i = 0;i < n;i++) {
if(in[i] == 0) q.push(i);
}
while(!q.empty()) {
int cur = q.front();
q.pop();
// cout << cur << " ";
dp[favorite[cur]] = max(dp[favorite[cur]], dp[cur] + 1);
if(--in[favorite[cur]] == 0) q.push(favorite[cur]);
}
// dp[i] 表示到达i的最长链的长度
int two_point_sum = 0; // 题目相关部分
for(int i = 0;i < n;i++) {
if(i == favorite[favorite[i]]) two_point_sum += dp[i];
}
return two_point_sum;
}
无向无环图
- 也可以和有向图一样，拓扑序+dp
- 还有一种有趣的方法，两次dfs。可以证明，从任一点出发，dfs能走到的最远点一定是”直径”的一个端点，然后从这个端点出发，dfs得到另一个端点。 参考下面【路径最长的两个叶子节点】
例如Leetcode310最小树高度，等价于求树的直径 第一次dfs找到一个端点，再从这个端点出发dfs找到另一个端点，最后在写个dfs得到路径
DFS/BFS 求最长链
可以利用以下算法找到图中距离最远的两个节点与它们之间的路径：
以任意节点 pp 出现，利用广度优先搜索或者深度优先搜索找到以 pp 为起点的最长路径的终点 xx；
以节点 xx 出发，找到以 xx 为起点的最长路径的终点 yy；
xx 到 yy 之间的路径即为图中的最长路径，找到路径的中间节点即为根节点。
上述算法的证明可以参考「算法导论习题解答 9-1」。