2360. Longest Cycle

Longest Cycle in a Graph

经典的环识别题 想当然耳开DFS最直观啰

这道题好处是 图上$n$个点标签是$0$到$n - 1$非负整数

直接拿vector<int>来做访问顺序的追踪表即可

用unordered_map<int, int>会慢很多......🐢

环何时成形？先把这个想清楚

当我们在递归有向图的过程中 来到某个点$u$

若$u$无出边 自然就是个死胡同了 点$u$不会在环内

那么假如$u$有条指向点$v$的出边呢？目前点$v$有三种可能性：

I. 仍未被访问过🔴

II. 正在递归栈上还没闪人🟡

III. 进过且登出递归栈了🟢

大家想想看 哪个状态会是环成形的那瞬间呢？

答案是中间的状态II. 正在递归栈上还没闪人🟡

这就是恭喜环成形的那瞬间🎊

$(u, v)$是这个新生的环$C$ 最后的那块拼图🧩

点$v$是环的起点 终点是点$u$🏁 环$C$的长度便是 $d[u] + 1 - d[v]$

其中$d[u]$和$d[v]$分别是 点$u$和点$v$的访问顺序

由于题目要求我们计算最长的环长度 每当有个环刚成形了

我们就要拿 $d[u] + 1 - d[v]$和已知的历史最高值 来比较

青出于蓝的话便更新历史新高值

方便管理的小技巧

当然有个小细节可注意下 就是为了快速区分前面说的II.和III.俩状态

我习惯在visitedOrders这个整数阵列上 采取几种不同标记：

1. -1：点未被访问过🔴
2. 正整数：点正在递归栈上还没闪人🟡这正是点的访问顺序
3. -2：点已经进过且登出递归栈了🟢

每个点和每条边都只会刚好经过一遍 时间复杂度$O(V + E)$

空间复杂度也和点与边数量呈线性关系 有$O(V + E)$

C++

#include <vector>
using namespace std;

class LongestCycle // LeetCode Q.2360.
{
private:
    vector<int> graph, visitedOrders;
    int currentOrder = 1, maxCycle = -1;

    void dfsCycle(int node)
    {
        visitedOrders[node] = currentOrder;
        currentOrder++; // Increment for the next node.

        int tgtNode = graph[node];
        if (tgtNode == -1) // No outgoing edge.
        {
            visitedOrders[node] = -2; // Current node finalizes DFS.
            return;
        }

        if (visitedOrders[tgtNode] == -1) // Unvisited yet.
            dfsCycle(tgtNode);

        int tgtNodeOrder = visitedOrders[tgtNode];

        // Target node is also still under DFS: a cycle just forms.
        if (tgtNodeOrder > 0)
        {
            // Such a cycle starts at target, and ends at current node.
            int cycleLen = visitedOrders[node] + 1 - tgtNodeOrder;
            if (cycleLen > maxCycle)
                maxCycle = cycleLen;
        }

        visitedOrders[node] = -2; // Current node finalizes DFS.
    }

public:
    int computeLongestCycle(vector<int> &edges)
    {
        graph = edges;

        // Special marks: -1 = unvisited. -2 = has finalized DFS.
        visitedOrders.assign(edges.size(), -1);

        for (int node = 0; node < edges.size(); node++)
        {
            if (visitedOrders[node] == -1) // Unvisited yet.
                dfsCycle(node);
        }

        return maxCycle;
    }
};

Python

class LongestCycle:  # LeetCode Q.2360.
    def __init__(self):
        self.edges: list[int] = []
        self.visited_orders: list[int] = []

        self.current_order = 1
        self.longest_cycle = -1

    def _dfs_cycle(self, node: int) -> None:
        self.visited_orders[node] = self.current_order
        self.current_order += 1  # Increment for the next node.

        tgt_node = self.edges[node]
        if tgt_node == -1:  # No outgoing edge.
            self.visited_orders[node] = -2  # Current node finalizes DFS.
            return

        if self.visited_orders[tgt_node] == -1:  # Unvisited yet.
            self._dfs_cycle(tgt_node)

        tgt_node_order = self.visited_orders[tgt_node]

        # Target node still under DFS: a cycle just forms.
        if tgt_node_order > 0:
            # Such a cycle starts at target, and ends at current node.
            cycle_len = self.visited_orders[node] + 1 - tgt_node_order
            if cycle_len > self.longest_cycle:
                self.longest_cycle = cycle_len

        self.visited_orders[node] = -2  # Current node finalizes DFS.

    def compute_longest_cycle_len(self, edges: list[int]) -> int:
        self.edges = edges

        # Special marks: -1 = unvisited yet. -2 = has finalized DFS.
        self.visited_orders = [-1] * len(edges)

        self.current_order = 1
        self.longest_cycle = -1

        for node, _ in enumerate(edges):
            if self.visited_orders[node] == -1:  # Unvisited yet.
                self._dfs_cycle(node)

        return self.longest_cycle

延伸问题

若你想清楚了第2360问，那就来吧😉