문제풀이-[Noip2015] 메시지 전달

문서 목록

설명

해석

묘사

n명의 학우(번호 1부터 n까지)가 정보 전달 게임을 하고 있다.게임에서 모든 사람은 고정된 정보 전달 대상이 있는데 그 중에서 번호가 i인 학우의 정보 전달 대상은 번호가 Ti 학우이다.게임이 시작되었을 때, 모든 사람은 자신의 생일만 알았다.이후 매 라운드마다 모든 사람은 자신이 현재 알고 있는 생일 정보를 각자의 정보 전달 대상에게 동시에 알려준다(주의: 누군가는 몇 명에게서 정보를 얻을 수 있지만 한 사람당 한 사람, 즉 자신의 정보 전달 대상에게만 알려준다).누군가가 다른 사람의 입에서 자신의 생일을 알게 되면 게임은 끝난다.실례지만 이 게임은 모두 몇 라운드를 진행할 수 있습니까?간단하게 말하면 너에게 유방향도를 하나 주고 가장 작은 고리를 찾아내게 하는 것이다.
입력 총 2행.첫 번째 줄에는 n 개인을 나타내는 양의 정수 n이 있습니다.n≤200000 두 번째 줄에는 n개의 공백으로 구분된 정수 T1, T2,......, Tn에 포함된 i번째 정수 Ti는 번호가 i인 학우의 정보 전달 대상은 번호가 Ti인 학우이고 Ti≤n 및 Ti≠i 데이터는 게임이 반드시 끝날 것을 보장한다.
출력 출력은 모두 1줄로 1개의 정수를 포함하여 게임이 모두 몇 라운드를 진행할 수 있는지 나타낸다.
샘플 입력 5 2 4 2 3 1 출력 3

해석

하나의 링을 만들고 순서대로 모든 사람의 번호를 링에 저장한다. 하나의 그룹 표시를 열고 다른 그룹은 번호를 저장한 다음에 결과를 찾으면 끝난다. 가장 작은 링을 찾으면 결과다.

#include 
using namespace std;
const int maxn=200010;
int n, fa[maxn],ans=0x3f3f3f3f;
int get(int x, int &cnt){
    cnt++;
    if(fa[x]==x)return x;
    else return get(fa[x], cnt);
}
int main () {
    cin>>n;
    for(int i=1;i<=n;i++)
        fa[i]=i;
    for(int i=1;i<=n;i++) {
        int cnt=0,f;
        cin>>f;
        if(get(f,cnt)==i){
            ans=min(ans,cnt); 
        }else{
        	fa[i]=f;
        }
    }
    cout<