NOIP 2015 메시징

2737 단어 <===도론===>
제목 설명
n명의 학우(번호 1부터 n까지)가 정보 전달 게임을 하고 있다.게임에서 모든 사람은 고정된 정보 전달 대상이 있는데 그 중에서 번호가 i인 학우의 정보 전달 대상은 번호가 Ti 학우이다.
게임이 시작되었을 때, 모든 사람은 자신의 생일만 알았다.이후 매 라운드마다 모든 사람은 자신이 현재 알고 있는 생일 정보를 각자의 정보 전달 대상에게 동시에 알려준다(주의: 누군가는 몇 명에게서 정보를 얻을 수 있지만 한 사람당 한 사람, 즉 자신의 정보 전달 대상에게만 알려준다).누군가가 다른 사람의 입에서 자신의 생일을 알게 되면 게임은 끝난다.실례지만 이 게임은 모두 몇 라운드를 진행할 수 있습니까?
입력 출력 형식 입력 형식:
총 2행을 입력합니다.
첫 번째 줄에는 n 개인을 나타내는 양의 정수 n이 있습니다.
두 번째 행에는 공백으로 구분된 양의 정수 T1, T2,......n이 포함되어 있으며 Tn의 i번째 정수 Ti 표시 번호는 i입니다.
의 학우의 정보 전달 대상은 Ti 번호의 학우, Ti ≤n 및 Ti≠i
데이터는 게임이 반드시 끝날 것을 보증한다.
출력 형식:
출력은 모두 1줄로 1개의 정수를 포함하여 게임이 모두 몇 라운드를 진행할 수 있는지 나타낸다.
출력 샘플 가져오기
샘플 입력 #1:5 2 4 2 3 1
샘플 내보내기 #1:3
[분석] 최소 고리의 생각을 구한다. 고리가 아닌 점을 배제한 다음에 남은 고리를 한 번 뒤져서 가장 작은 고리를 찾아낸다.
【코드】
//  P2661  
#include
#include
#define fo(i,j,k) for(i=j;i<=k;i++) 
using namespace std;
int a[200001],ru[200001],n,ans=1e8;
int main()
{
    int i,j,k,tmp;
    scanf("%d",&n);
    fo(i,1,n)
    {
        scanf("%d",&a[i]);
        ru[a[i]]++;
    }
    fo(i,1,n)
      if(!ru[i])
      {
        ru[i]=-1;
        for(j=a[i];--ru[j]==0;j=a[j])
          ru[j]=-1;    //  
      }
    fo(i,1,n)   //  
      if(ru[i]!=-1)
      {
        tmp=0;
        for(j=i;j!=i || !tmp;j=a[j])
          tmp++,ru[j]=-1;   //  
        ans=min(ans,tmp); 
      }
    printf("%d
"
,ans); return 0; }

좋은 웹페이지 즐겨찾기