낙 곡 2661 정보 전달

제목 설명
n 명의 학우 (번호 1 부터 n 까지) 가 정보 전달 게임 을 하고 있 습 니 다.게임 에서 모든 사람 은 고정된 정보 전달 대상 이 있 는데 그 중에서 i 번 학생 의 정보 전달 대상 은 Ti 학생 이다.
게임 이 시 작 될 때 모든 사람 은 자신의 생일 만 안다.이후 매 라운드 에서 모든 사람들 은 자신 이 현재 알 고 있 는 생일 정 보 를 각자 의 정보 전달 대상 에 게 동시에 알려 준다 (주의: 누 군 가 는 여러 사람 에 게 서 정 보 를 얻 을 수 있 지만 모든 사람 은 정 보 를 한 사람, 즉 자신의 정보 전달 대상 에 게 만 알려 준다).누군가가 다른 사람의 입 에서 자신의 생일 을 알 게 되 었 을 때 게임 은 끝났다.이 게임 은 모두 몇 라운드 진행 할 수 있 습 니까?
입 출력 형식
입력 형식: 총 2 줄 을 입력 하 십시오.
첫 번 째 줄 에는 n 개인 을 나타 내 는 정수 n 이 포함 되 어 있다.
두 번 째 줄 은 n 개의 빈 칸 으로 구 분 된 정수 T1, T2,.................................................................
의 학생 의 정보 전달 대상 은 Ti 번호 의 학생, Ti ≤ n 및 Ti ≠ i
데이터 보증 게임 은 반드시 끝 납 니 다.
출력 형식: 출력 은 모두 1 줄 이 고 1 개의 정 수 를 포함 하 며 게임 이 모두 몇 라운드 가 진행 되 는 지 표시 합 니 다.
입 출력 샘플
입력 샘플 \ # 1: 복사 5 2 4 2 3 1 출력 샘플 \ # 1: 복사 3 설명
사례 1 해석
게임 의 절 차 는 그림 과 같다.3 라운드 게임 이 끝나 면 4 번 유 저 는 2 번 유저 가 자신 에 게 알려 주 는 것 을 들 을 수 있 습 니 다.
자신의 생일 이기 때문에 답 은 3 이다.물론 3 라운드 게임 후 2 번 유저, 3 번 유 저 는 모두 자신의 소식 을 들 을 수 있 습 니 다.
출처 는 자신의 생일 을 알 게 되 었 고 게임 종료 조건 에 도 부합 되 었 다.
30% 의 데이터 에 대해 n ≤ 200;
60% 의 데이터 에 대해 n ≤ 2500;
100% 의 데이터 에 대해 n ≤ 200000.
생각 은 검색 이 고 가장 작은 고 리 를 찾 는 것 이다.
gett 배열 은 태그 의 역할 을 할 뿐만 아니 라 걸음 수 를 기록 할 수 있 습 니 다.

#include
using namespace std;
const int maxn=200005;
int n,cnt,a[maxn],mn=9999999,gett[maxn];   
inline int read_d(){
    int s=0;
    char c;
    while(c=getchar(),c<'0'||c>'9');
    while(c<='9'&&c>='0') {
        s=s*10+c-'0';
        c=getchar();
    }
    return s;
}
inline void dfs(int x){
    if(a[x]==0) return;
    cnt++;
    if(cnt>gett[x] && gett[x]){
        mn=min(cnt-gett[x],mn);
        cnt=0;
        a[x]=0;
        return;
    }
    gett[x]=cnt;
    dfs(a[x]);
    gett[x]=0;
    a[x]=0;
}
int main(){
    n=read_d();
    for(register int i=1;i<=n;i++){
        int x;
        x=read_d();
        a[i]=x;
    }
    for(register int i=1;i<=n;i++)  dfs(a[i]);
    printf("%d",mn);
    return 0;
}