로곡-2661 정보 전달

제목은 n명의 학우(번호 1부터 n까지)가 정보 전달 게임을 하고 있다고 묘사했다.게임에서 모든 사람은 고정된 정보 전달 대상이 있는데 그 중에서 iii 학우의 정보 전달 대상은 Ti 학우이다.게임이 시작되었을 때, 모든 사람은 자신의 생일만 알았다.이후 매 라운드마다 모든 사람은 자신이 현재 알고 있는 생일 정보를 각자의 정보 전달 대상에게 동시에 알려준다(주의: 누군가는 몇 명에게서 정보를 얻을 수 있지만 한 사람당 한 사람, 즉 자신의 정보 전달 대상에게만 알려준다).누군가가 다른 사람의 입에서 자신의 생일을 알게 되면 게임은 끝난다.실례지만 이 게임은 모두 몇 라운드를 진행할 수 있습니까?입력 출력 형식 입력 형식: 총 2줄.첫 번째 줄에는 n 개인을 나타내는 양의 정수 n이 있습니다.두 번째 줄은 n개의 공백으로 구분된 정수 T1, T2,..., Tn을 포함한다. 그 중에서 i번째 정수 Ti는 i의 학우를 나타내는 정보 전달 대상은 Ti의 학우, Ti≤n 및 Ti≠i 출력 형식: 1개의 정수로 게임이 모두 몇 라운드를 진행할 수 있는지 나타낸다.
입력 출력 예제 입력 예제 #1:5 2 4 2 3 1
샘플 내보내기 #1:3
해석: 모든 학우를 하나의 노드로 보고 말을 방향이 있는 것으로 간주한다. 그것이 바로 그림에서 가장 작은 고리 문제를 찾는 것이다. 그러면 한 번의 dfs만 있으면 된다. 우리는 모든 점에 dfs순으로 번호를 매긴다. 그러면 표시가 있는 점까지 두루 돌아다닐 때 그 표지가 지금부터 시작된 가장 작은 DFS 번호보다 작으면 이미 두루 돌아다녔고 고리가 존재하지 않는다. 그렇지 않으면 하나의 고리이다. dfs순이 나쁘면 고리의 크기를 얻는다.

#include
#define N 200003
using namespace std;
int a[N]={0};
int n=0;
int vis[N]={0};
int ret=N+1;
int t=0;
int dfs(int x){
    int start=t+1;
    while(!vis[x]){
        vis[x]=++t;
        x=a[x];
    }
    if(start>vis[x]) return N+1;
    else return t-vis[x]+1;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            ret=min(ret,dfs(i));
        }
    }
    cout<

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

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

[못 푼 문제] 백준 10989번

sys.stdin.readline()을 사용하여 input의 시간을 줄였다. 또한 입력 가능한 수의 개수가 10,000,000개 이고 최대 입력 가능한 수가 10,000이기 때문에 모든 수를 입력 받아 리스트로 만들...

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

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

로곡-2661 정보 전달

좋은 웹페이지 즐겨찾기