NOIP2015 그룹 정보 전달 향상 (도론)

[문제 설명]
n명의 학우(번호 1부터 n까지)가 정보 전달 게임을 하고 있다.게임에서 모든 사람은 고정된 정보 전달 대상이 있는데 그 중에서 번호가 i인 학우의 정보 전달 대상은 번호가 Ti 학우이다.
게임이 시작되었을 때, 모든 사람은 자신의 생일만 알았다.이후 매 라운드마다 모든 사람은 자신이 현재 알고 있는 생일 정보를 각자의 정보 전달 대상에게 동시에 알려준다(주의: 누군가는 몇 명에게서 정보를 얻을 수 있지만 한 사람당 한 사람, 즉 자신의 정보 전달 대상에게만 알려준다).누군가가 다른 사람의 입에서 자신의 생일을 알게 되면 게임은 끝난다.실례지만 이 게임은 모두 몇 라운드를 진행할 수 있습니까?
[형식 입력]
총 2행을 입력합니다.첫 번째 줄에는 n 개인을 나타내는 양의 정수 n이 있습니다.두 번째 줄에는 n개의 공백으로 구분된 정수 T1, T2,......가 포함되어 있다. Tn에서 두 번째 정수 Ti는 번호가 i인 학우의 정보 전달 대상은 번호가 Ti인 학우이고 Ti≤n이며 Ti≠i 데이터는 게임이 반드시 끝날 것을 보증한다.
[출력 형식]
출력은 모두 1줄로 1개의 정수를 포함하여 게임이 모두 몇 라운드를 진행할 수 있는지 나타낸다.
[샘플 입력]
5 2 4 2 3 1
[샘플 내보내기]
3
[예제 해석]
게임의 흐름은 그림과 같다.3라운드 게임을 마친 4번 게이머는 2번 게이머가 자신의 생일을 알려주는 소리를 듣기 때문에 답은 3이다.물론 3라운드 게임 후 2번 유저, 3번 유저는 모두 자신의 소식통에서 자신의 생일을 알 수 있어 게임 종료 조건에 부합된다.　　
[데이터 범위]
30%의 데이터에 대해 n≤200;60%의 데이터에 대해 n≤2500;100% 데이터의 경우 n≤200000입니다.
【출처】
NOIP 원제
모든 사람이 출발해서 그의 메시지를 보면 오랫동안 돌아올 수 있고 최소치를 기록할 수 있다.자세한 절차는 다음과 같습니다.

#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=200005;
int d[maxn],a[maxn],n,vis[maxn],det[maxn],ans=maxn;
void init()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
}

void dfs(int i,int k)
{
    vis[i]=k;
    det[i]=1;
    if(det[a[i]]==0)
    dfs(a[i],k+1);
    if(vis[a[i]]!=0&&vis[i]-vis[a[i]]+1!=0)
    ans=min(ans,vis[i]-vis[a[i]]+1);
    vis[i]=0;// 。
}

int main()
{
    init();
    memset(d,0,sizeof(d));
    memset(det,0,sizeof(det));
    for(int i=1;i<=n;i++)
    if(det[i]==0)
    {
        dfs(i,1);
    }
    printf("%d",ans);
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

HDU 3631 Shortest Path(Floyd + 플러그인)

제목: n개의 점 m줄 테두리(단방향 테두리)와 q차 조작을 드리겠습니다. 처음에는 모든 점이 표시가 없습니다. 두 가지 조작이 있습니다. 1.0 x: x를 표시하고 가까이 표시한 경우 "ERROR! At point...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

NOIP2015 그룹 정보 전달 향상 (도론)

좋은 웹페이지 즐겨찾기