【Leetcode】2360. Longest Cycle in a Graph

题目地址：

https://leetcode.com/problems/longest-cycle-in-a-graph/

给定一个$n$个点的有向图，每个点最多只有一条出边。给定每个点的出边指向的点，如果不存在则以$-1$标记。求长度最大的环的长度。若不存在环，则返回$-1$。

当然可以直接用Tarjan求一下最大的强联通分量。由于每个点只有一条出边，所以每个点只会存在于一个环中，从而可以直接模拟，直接从每个点出发，并且做标记，同时用一个哈希表记录步数。代码如下：

class Solution {
    
 public:
  int longestCycle(vector<int>& e) {
    
    int n = e.size();
    vector<bool> vis(n);
    int res = -1;
    for (int i = 0; i < n; i++) {
    
      if (!vis[i]) {
    
        unordered_map<int, int> mp;
        int x = i, time_stamp = 0;
        while (true) {
    
          mp[x] = ++time_stamp;
          vis[x] = true;
          // 找到环了
          if (mp.count(e[x])) {
    
            res = max(res, mp[x] - mp[e[x]] + 1);
            break;
          }
          // 走到了死胡同
          if (e[x] == -1 || vis[e[x]]) break;
          // 向后走一步
          x = e[x];
        }
      }
    }

    return res;
  }
};

时空复杂度$O(n)$。