NOIP2015 향상 그룹 T2 로곡 P2661 메시징

8122 단어

제목 설명


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 축소점을 찾아 포함 포인트가 가장 적은 (단 1과 같지 않음)의 축소점을 찾아내면 포함 포인트가 답이다.
각 점의 출도가 가장 많기 때문에 복잡한 방식으로 가장자리를 저장할 필요가 없고, 개수조만 열어 각 점의 행방을 기록하면 된다.
 1 /**/
 2 #include
 3 #include
 4 #include
 5 #include
 6 #include
 7 using namespace std;
 8 const int mxn=230000;
 9 int v[mxn];
10 int dtime=0;
11 bool inst[mxn]; 
12 int st[mxn],top;
13 int low[mxn],dfn[mxn];
14 //
15 int belone[mxn],cnt=0;
16 int dg[mxn];
17 //
18 int n;
19 void tarjan(int u){
20     low[u]=dfn[u]=++dtime;
21     st[++top]=u;
22     inst[u]=1;
23     //
24     if(!dfn[v[u]]){
25         tarjan(v[u]);
26         low[u]=min(low[u],low[v[u]]);
27     }
28     else if(inst[v[u]])
29         low[u]=min(low[u],dfn[v[u]]);
30     //
31     if(low[u]==dfn[u]){
32         ++cnt;
33         int w;
34         do{
35             w=st[top--];
36             dg[cnt]++;
37             inst[w]=0;
38         }while(w!=u);
39     }
40     return;
41 }
42 int main(){
43     scanf("%d",&n);
44     int i,j;
45     for(i=1;i<=n;i++){
46         scanf("%d",&v[i]);
47     }
48     for(i=1;i<=n;i++){
49         if(!dfn[i])tarjan(i);
50     }
51     int ans=5000000;
52     for(i=1;i<=cnt;i++) {if(dg[i]1)ans=dg[i];}
53     printf("%d
",ans); 54 return 0; 55 }

 
 
전재 대상:https://www.cnblogs.com/SilverNebula/p/5730377.html

좋은 웹페이지 즐겨찾기