문제풀이-[Noip2015] 메시지 전달
1351 단어 문제풀이
문서 목록
묘사
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< 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
49일차 - 2022.04.20Baekjoon에서 문제풀이 1) 문제 : 첫째 줄에는 별 1개, 둘째 줄에는 별 2개, N번째 줄에는 별 N개를 찍는 문제/ 첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다. 첫째 줄부터 N번째 줄까지 차례대로 별...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
