图论问题集合

寻找特殊有向图（一个节点最多有一个出边）中最大环路问题

我们以力扣2360. 图中的最长环为例解决这个问题

特殊有向图解析

任意一个图，都是由若干连通块组成，连通块之间并不相连。
对于连通块上的每一个节点：

1、最多只能有一个出边；
2、其中任意一个节点N，他只有这一个出边，他要么和前面的节点连上构成一个整体的连通体；要么和身后连接他的其中一个节点连上构成环路。
3、所以说不存在一个连通体中存在两个环：即任意一个连通体中，最多只有一个环
4、对于图中任意一个大小为 m 的连通块，有 m 个点，每个点至多出去一条边，所以连通块至多有 m 条边。
5、m 个点 m−1 条边的连通图是一棵树，在树上增加一条有向边，至多会形成一个环。（这样的图叫做内向基环树）

算法解析

通过上面分析，这种特殊的有向图，每一个连通块中至多有一个环，题目最终让我们找一个最大的环：
所以我们只需要挨个遍历图中每一个连通块，找到各个连通块当中环的大小，并动态维护最大值即可。

步骤 1 ：举例分析如何在一个连通块中找到环并使用时间戳计算大小

1、我们类比生活场景，观察下图，我们从0点开始走，只要不走到死胡同（题中会指向点-1）或者遇到之前走过的点，我们就继续前进，当我们发现我又走回了曾经到过的点，就说明一定存在环；如果我们直到最终走到死胡同的时候都没走回头路，说明没有环，可以继续看下一个连通体。
2、假设我们是time=2的时候，第一次到节点3，time=3到达节点2，time=4到达节点4，time=5的时候我们发现，节点3我们在time=2的时候来过一次，说明存在环，环的大小恰好等于时间差，即：5-2=3，共三个节点。

步骤 2 ：抽象成算法

1、对于一个新的连通体而言，我们第一次来，只要没走到头或者走回头路，我们就持续前进，并记录走到该处的时间；
2、当走到死胡同，说明没有环，继续下一个连通体；当走到之前访问过的点时，利用时间差计算这个连通体中环的大小
3、遍历完所有连通体，动态维护最大的环大小。
4、实现的时候，我们从头到尾遍历所有点，从任意入口进入连通体；当这个连通体环路被处理完，但是程序又从别的入口进入该连通体（上面图中，0、2、3、4都已经处理完，程序又从1进入），这种情况我们直接跳过就行。

注意

本题保证每个连通块至多有一个环，所以可以根据时间差算出环长。如果没有这个保证，时间差算出的可能不是最长环。一般图的最长环是 NP-hard 问题。

实现

class Solution {
public:int longestCycle(vector<int>& edges) {int n = edges.size();int ans = -1;vector<int> visit(n);//记录第一次访问时间int cur_time = 1;//记录当前时间//遍历每个节点，其实这里是遍历每个连通体，从连通体上任意一个点进入，然后处理完一个连通体之后，已经走过的点不走，一直到新的点//如果新的点依旧是属于已访问过的连通体，则直接跳过，反之说明到了新的连通体，继续处理for (int i = 0; i < n; i++) {int x = i;//记录当前节点//将初始时间进行记录，如果该环被处理过，则任意一个处理过的点第一次访问时间要小于这次的开始时间int start_time = cur_time;while (x != -1 && visit[x] == 0) {//只要没走到死胡同（值==-1）并且是没经过的点，就一直走visit[x] = cur_time++;//因为保证了走的是没经过的点，所以保证这里的值是第一次访问时间x = edges[x];}if (x != -1 && visit[x] >= start_time) {//退出循环之后，确认不是走到死胡同&&这个环路没被处理过（这轮循环的开始时间大于该点第一次访问时间，说明该点之前被处理过）//此时cur_time 表示第二次到达x时间-visit[x]第一次到x时间ans = max(ans, cur_time - visit[x]);//在所有的环中，也就是所有的连通体中可能存在的所有环，找最大的。}}return ans;}
};