2020?？秃偎惴ɑA(chǔ)集訓(xùn)營6 B-圖
思路：
記憶化搜索dfs
分析可知圖為出度為1的基環(huán)內(nèi)向樹森林，從一個點出發(fā)，沿著出邊一路走下去，一定會走到一個環(huán)。
所以我們選擇dfs，當遍歷到一個已在dfs棧中的節(jié)點時，就說明找到了環(huán)，可以結(jié)束統(tǒng)計。
但這樣是會超時的，于是我們選擇帶“記憶化”的dfs，從一個點開始沿著出邊走下去，每當走到一個在之前某次dfs中經(jīng)過的點時，就可以利用上一次的答案完成求解。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <map>
#include <stack>
#include <set>

using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-10;
const int INF = 0x3f3f3f3f;
const ll mod  = 1e9 + 7;
const ll maxn = 1e6 + 5;

int n,loop;
int to[maxn],f[maxn],cnt[maxn];//f[]記錄從當前點走下去一共有多少個環(huán) cnt[]記錄step數(shù)
bool vis[maxn];

int dfs(int x,int step){
	vis[x]=true;
	cnt[x]=step;
	int tx=to[x];
	if(!vis[tx]){
		int res=dfs(tx,step+1);
		if(loop){
			if(loop==x){//loop用來判斷是否出環(huán) 自環(huán)
				loop=0;
			}
			return f[x]=res;//未出環(huán)時環(huán)內(nèi)各點均為res
		}else{
			return f[x]=res+1;//出環(huán)后為該點個數(shù)+1
		}
	}else{
		if(f[tx]) return f[x]=f[tx]+1;//下一個點搜過了且下一個點有值則為其+1
		else{//下一個點搜過了但是還為0 顯然還在遍歷環(huán)切恰恰是環(huán)尾到入環(huán)點
			loop=tx;//標記入環(huán)點
			if(tx==x) loop=0;//自環(huán)
			return f[x]=cnt[x]-cnt[tx]+1;//環(huán)的大小為出換點的step-入環(huán)點的step+1
		}
	}
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>to[i];
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			vis[i]=true;
			loop=0;
			dfs(i,1);
		}
	}
	cout<<*max_element(f+1,f+1+n);
	return 0;
}