#146. [NOIP2015] 메시징

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

입력 형식


총 2행을 입력합니다.첫 번째 행에는 nn 개인을 나타내는 양의 정수 nn이 있습니다.
두 번째 행에는 nn개의 공백으로 구분된 양의 정수 T1, T2,..., TnT1, T2,..., Tn이 포함되어 있는데 그 중에서 ii의 정수인 Titi는 번호가 ii인 학우를 나타내는 정보 전달 대상은 번호가 Ti인 학우, Ti ≤nTi ≤n 및 Ti≠ iTi ≠ i이다.
데이터는 게임이 반드시 끝날 것을 보증한다.

출력 형식


출력은 모두 1줄로 1개의 정수를 포함하여 게임이 모두 몇 라운드를 진행할 수 있는지 나타낸다.

예제 1


input 
5
2 4 2 3 1

output 
3

 
이 문제는 그림을 보면 234가 강연통분량이라는 것을 알 수 있다. 그러면 그림에서 가장 작은 강연통분량이 얼마인지 구하면 ok이다. 물론 하나도 계산하지 않는다.
가장 작은 고리를 찾는 문제일 뿐만 아니라 방향도도 있다
tarjan 알아보세요.
#include
using namespace std;
const int N=2e5+5;
vectorm[N];
stackp;
int dfn[N];
int low[N];
int vis[N];
int ans=N;
int n;
int cnt=0;

void tarjan(int x)
{
    low[x]=dfn[x]=++cnt;
    p.push(x);
    vis[x]=1;
    for(int i=0;i1) ans=min(ans,flag);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        m[i].push_back(x);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]) tarjan(i);
    }
    printf("%d
",ans);
    return 0;
}

유닛에서 주머니 같은 거.
[AWS, Golang] EC2에서 ssh로 Hello World에 로그인

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage