P2661 메시징

제목 설명

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

입력 출력 형식

입력 형식:
 
총 2행을 입력합니다.
첫 번째 줄에는 n 개인을 나타내는 양의 정수 n이 있습니다.
두 번째 행에는 공백으로 구분된 양의 정수 T1, T2,......n이 포함되어 있으며 Tn의 i번째 정수 Ti 표시 번호는 i입니다.
의 학우의 정보 전달 대상은 Ti 번호의 학우, Ti ≤n 및 Ti≠i
데이터는 게임이 반드시 끝날 것을 보증한다.
출력 형식:
 
출력은 모두 1줄로 1개의 정수를 포함하여 게임이 모두 몇 라운드를 진행할 수 있는지 나타낸다.
 

출력 샘플 가져오기

샘플 #1 입력:

5
2 4 2 3 1

샘플 내보내기 #1:

3

설명

예제 1 해석
게임의 흐름은 그림과 같다.3라운드 게임을 마친 후, 4번 유저는 2번 유저에게
자신의 생일, 그래서 답은 3.물론 3라운드 게임 후, 2번 유저, 3번 유저는 모두 자신의 소식을
자신의 생일을 알게 된 것도 마찬가지로 게임이 끝난 조건에 부합된다.
30%의 데이터에 대해 n≤200;
60%의 데이터에 대해 n≤2500;
100% 데이터의 경우 n≤200000입니다.
문제 풀이:
tarjan의 판자, ans: 첫 번째sum[i]>1의 수
AC 코드:
 

#include
#include
#include
#include
using namespace std;
#define N 200010 
int n,sd,pd,low[N],dfn[N],sum[N];
bool mark[N];
vector<int>grap[N];
stack<int>s;
void tarjan(int v){
    low[v]=dfn[v]=++pd;
    mark[v]=1;
    s.push(v);
    for(int i=0;i){
        int w=grap[v][i];
        if(!dfn[w]){
            tarjan(w);
            low[v]=min(low[v],low[w]);
        }
        else if(mark[w]){
            low[v]=min(low[v],dfn[w]);
        }
    }
    int u;
    if(low[v]==dfn[v]){
        sd++;
        do{
            u=s.top();
            s.pop();
            sum[sd]++;
            mark[v]=0;
        }while(u!=v);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1,x;i<=n;i++) scanf("%d",&x),grap[i].push_back(x);
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
    sort(sum+1,sum+sd+1);
    for(int i=1;i<=sd;i++) if(sum[i]>1){printf("%d",sum[i]);return 0;}
    return 0;
}

 
 
 
듣자니 쌓기 최적화 + 토폴로지 정렬 + 읽기 최적화도 AC, 구체적인 코드, 자체 실현
전재 대상:https://www.cnblogs.com/shenben/p/5634177.html