로곡 P2661 정보 전달

제목 설명

n명의 학우(번호 1부터 n까지)가 정보 전달 게임을 하고 있다.게임에서 모든 사람은 고정된 정보 전달 대상이 있는데 그 중에서 iii 학우의 정보 전달 대상은 Ti 학우이다.
게임이 시작되었을 때, 모든 사람은 자신의 생일만 알았다.이후 매 라운드마다 모든 사람은 자신이 현재 알고 있는 생일 정보를 각자의 정보 전달 대상에게 동시에 알려준다(주의: 누군가는 몇 명에게서 정보를 얻을 수 있지만 한 사람당 한 사람, 즉 자신의 정보 전달 대상에게만 알려준다).누군가가 다른 사람의 입에서 자신의 생일을 알게 되면 게임은 끝난다.실례지만 이 게임은 모두 몇 라운드를 진행할 수 있습니까?

입력 형식

모두 두 줄.첫 번째 줄에는 n 개인을 나타내는 양의 정수 n이 있습니다.두 번째 행에는 n개의 정수 T1, T2,...

출력 형식

한 개의 정수는 게임이 모두 몇 라운드를 진행할 수 있는지를 나타낸다.

출력 샘플 가져오기

#1 복사 입력

5
2 4 2 3 1

출력 #1 복사

3

 ， 。

#include#include#includeusing namespace std;int num_edge=0,n,a,head[200001],que[200001],hed,tail,mint=200001,mark[200001],step[200001],markt[200001];struct Edge{ int to,next;}edge[200001];
void add_edge(int from,int to){ edge[++num_edge].next=head[from]; edge[num_edge].to=to; head[from]=num_edge;}
int min(int aa,int bb){ return aa>bb?bb:aa;}int main(){ cin>>n; for(int i=1;i<=n;i++) {  cin>>a;  add_edge(i,a); } for(int i=1;i<=n;i++) {  if(mark[i]==1) continue;  hed=0;tail=1;  que[tail]=i;step[i]=0;  //printf("%d",i);  while(hed  { hed++;   int headt=que[hed];   //printf(">>%d(%d)",headt,step[headt]);   if(step[headt]>mint) break;   if(headt==i&&hed!=1){    mint=min(mint,step[i]);    //printf("%d   %d",step[i],mint);    break;   }  for(int j=head[headt];j!=0;j=edge[j].next)   if(mark[edge[j].to]==0)   { mark[edge[j].to]=1;markt[edge[j].to]=i;    que[++tail]=edge[j].to;step[edge[j].to]=step[headt]+1;   }   else if(mark[edge[j].to]==1&&markt[edge[j].to]==i)   {    mint=min(mint,step[headt]+1-step[edge[j].to]);    //printf("%d   %d",step[headt]+1-step[edge[j].to],mint);    //markt[i]=1;   }  } // memset(mark,0,sizeof(int)*200001); // printf(""); } printf("%d",mint); return 0; }
 
그림을 작성하여 넓이를 우선적으로 두루 훑어보다.
주의해야 할 것은 거친 넓이가 시간을 초과할 수 있다는 것이다. 우리는 분석을 통해 알 수 있듯이 그림은 세 가지 상황, 즉 체인이나 링 또는 하나의 링이 하나의 체인을 연결하는 것이다.
매번 한 점을 훑어볼 때마다 표시할 때 놓지 않아도 된다. 상술한 세 가지 상황이 모두 훑어본 점이기 때문에 다시 한 번 기점으로 훑어볼 필요가 없다. 이럴 때 우리는 고리가 되는지 아닌지를 판단하기만 하면 고리의 점의 개수를 기록할 수 있다.
또한 주의해야 할 것은 다음 점이 이미 표시된 것이 링이 아니라는 판단이다. 왜냐하면 우리는mark수 그룹을 리셋하지 않았기 때문이다.따라서 우리는 하나의 점이 표시될 때의 출발점을 기록하기 위해markt 그룹을 열어야 한다.다음 점까지 옮겨다니면 표시된 다음에 판단합니다
markt의 값이 이때의 출발점인지, 그렇지 않으면 링이 되고, 그렇지 않으면 링이 되지 않고 이번 역경을 뛰어넘는다.