dfs 树复习

忘了

1. 参见
2. 例子

In OI By Rapiz 2019-09-05 DFS, tarjan

参见

https://www.cnblogs.com/usedrosee/p/4322074.html

《算法导论》基本的图算法

例子

信息传递：找出有向图的最小环

有人提出用 Tarjan 算法，这当然可以。但是这道题只是用了 Tarjan 算法中的一部分。更具体的说，经过阅读算导上的定义和性质后，我们发现只需要找出后向边，就可以计算出答案。

/*
 *     ____              _    
 *    / __ \____ _____  (_)___
 *   / /_/ / __ `/ __ \/ /_  /
 *  / _, _/ /_/ / /_/ / / / /_
 * /_/ |_|\__,_/ .___/_/ /___/
 *            /_/             
 *           code@rapiz.me
 *          Thu, 05 Sep 2019 22:05:11 +0800
 */
#include <bits/stdc++.h>
#define xxx(x) cerr<<(#x)<<": "<<x<<endl;
#define fastios ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
using namespace std;
const int N = 2e5 + 10;
int n, a[N], vis[N], dfn[N], ans = 1e9, clk;
void dfs(int u) {
  vis[u] = 1;
  dfn[u] = ++clk;
  if (vis[a[u]] == 0) {
    dfs(a[u]);
  }
  else if (vis[a[u]] == 1) {
    ans = min(ans, dfn[u] - dfn[a[u]] + 1);
  }
  vis[u] = 2;
}
int main() {
  fastios;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; i++) if (!vis[i]) {
    dfs(i);
  }
  cout << ans << endl;
}