记录编号	209590	评测结果	AAAAAAAAAA
题目名称	[NOIP 2015]信息传递	最终得分	100
用户昵称	TCtower	是否通过	通过
代码语言	C++	运行时间	0.184 s
提交时间	2015-11-22 21:23:30	内存使用	4.14 MiB

/*
昔日龌龊不足夸，今朝放荡思无涯。
春风得意马蹄疾，一日看尽长安花。
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#define LOCAL
//#pragma comment(linker, "/STACK:10240000000,10240000000")
const int MAXN = 200000 + 200;
using namespace std;
int V[MAXN];
int dfn[MAXN], low[MAXN], n, m;
int vis[MAXN], pos, cnt[MAXN], x;//标记是否已经出栈
stack<int> S;

void init(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &V[i]);
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(vis, 0, sizeof(vis));
    pos = 0;
}
void dfs(int u, int num){
    dfn[u]  = low[u] = num;
    //printf("%d\n", dfn[3]);
    //printf("%d\n", num);
    S.push(u);
    if (vis[V[u]]) goto w;//不要找
    if (dfn[V[u]] == 0){
        dfs(V[u], num + 1);
        low[u] = min(low[u], low[V[u]]);
    }else low[u] = min(low[u], dfn[V[u]]);
    w:if (dfn[u] == low[u]){
        pos++;
        cnt[pos] = 0;
        do{
            x = S.top();
            S.pop();
            vis[x] = 1;
            cnt[pos]++;
        }while (x != u);
    }
    return;
}

int main(){
    #ifdef LOCAL
    freopen("2015message.in", "r", stdin);
    freopen("2015message.out", "w", stdout);
    #endif

    init();
    for (int i = 1; i <= n; i++){
        if (vis[i]) continue;
        dfs(i, 1);
    }
    int Ans = n;
    for (int i = 1; i <= pos; i++) if (cnt[i] != 1) Ans = min(Ans, cnt[i]);
    printf("%d\n", Ans);
    return 0;
}