[NOIP2015TG]信息传递 – 没事来划划水


[NOIP2015TG]信息传递
题目链接:洛谷P2661


Description
有n个同学(编号为1到n)正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象,其中,编号为i的同学的信息传递对象是编号为Ti的同学。
游戏开始时,每人都只知道自己的生日。之后每一轮中,所有人会同时将自己当前所知的生日信息告诉各自的信息传递对象(注意:可能有人可以从若干人那里获取信息,但是每人只会把信息告诉一个人,即自己的信息传递对象)。当有人从别人口中得知自己的生日时,游戏结束。请问该游戏一共可以进行几轮?


Input
2行。
1行包含1个正整数n,表示n个人。
2行包含n个用空格隔开的正整数T_1,T_2,\cdot\cdot\cdot\cdot\cdot\cdot,T_n,其中第i个整数表示编号为i的同学的信息传递对象是编号为T_i的同学,T_i\leqslant nT_i\neq i


Output
1个整数,表示游戏一共可以进行多少轮。


Sample Input 1
5
2 4 2 3 1


Sample Output 1
3


Hint
样例1解释

游戏的流程如图所示。当进行完第3轮游戏后,4号玩家会听到2号玩家告诉他自己的生日,所以答案为3。当然,第3轮游戏后,2号玩家、3号玩家都能从自己的消息来源得知自己的生日,同样符合游戏结束的条件。
对于30\%的数据,n\leqslant200
对于60\%的数据,n\leqslant2500
对于100\%的数据,n\leqslant200000


Solution
复习图论的时候划划水
按题目描述建单向边
建完单向边跑遍tarjan
答案就是所有联通块的size除1外最小的值


Code

#include<map>
#include<set>
#include<list>
#include<queue>
#include<vector>
#include<string>
#include<time.h>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
//#define Judge
//#define Online
#define maxn 200100
#define reg register
#define ll long long
#define mod 1000000007
#define inf 2147483647
#define lowbit(x) ((x)&-(x))
#define abs(x) ((x)<0?-(x):(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define ckmax(a,b) ((a)=max((a),(b)))
#define ckmin(a,b) ((a)=min((a),(b)))
using namespace std;
#ifdef Judge
#define puts io.put
#define getchar io.gc
#define putchar io.wchar
#ifdef Online
FILE*in=stdin;
FILE*out=stdout;
#else
FILE*in=fopen(".in","r+");
FILE*out=fopen(".out","w+");
#endif
struct FastIO{
    #define S 1000000
    int wpos,len,pos;char wbuf[S],buf[S];
    FastIO(){wpos=0,len=0,pos=0;}
    inline char gc(){
        if (pos==len) pos=0,len=fread(buf,1,S,in);
        if (pos==len) return 0; return buf[pos++];
    }
    inline void wchar(int x) {
        if (wpos==S) fwrite(wbuf,1,S,out),wpos=0;
        wbuf[wpos++]=x;
    }
    inline void put(const char*s) {for(; *s; ) wchar(*s++);}
    ~FastIO() {
        if (wpos) fwrite(wbuf,1,wpos,out),wpos=0;
    }
}io;
#endif
template<typename T> inline void read(T&x){T f=1;x=0;char c;
    for (c=getchar(); !isd(c); c=getchar()) f=(c=='-')?-1:f;
    for (; isd(c); c=getchar()) x=(x<<3)+(x<<1)+(c^48);x*=f;
}
template<typename T> inline void wt(T x,char c=0){char ch[(sizeof(T)+1)<<1];if (x<0) x=-x,putchar('-');
    int t=-1; do ch[++t]=x%10+'0',x/=10; while(x); do putchar(ch[t]); while(t--); if (c!=0) putchar(c);
}
int n,m,cl_cnt,cl[maxn],bo[maxn],sz[maxn];
int dfn[maxn],low[maxn],dfs_cnt,sta[maxn],top;
int fir[maxn],to[maxn],nxt[maxn],cnt,ans(inf);
inline void ins(int x,int y){
    nxt[++cnt]=fir[x],fir[x]=cnt,to[cnt]=y;
}
inline void Tarjan(int x){
    dfn[x]=++dfs_cnt;low[x]=dfs_cnt;
    bo[x]=1,sta[++top]=x;
    for (int i=fir[x]; i; i=nxt[i])
        if (!dfn[to[i]]){Tarjan(to[i]);ckmin(low[x],low[to[i]]);
        }else if (bo[to[i]]) ckmin(low[x],dfn[to[i]]);
    if (dfn[x]==low[x]) {
        bo[x]=0,cl[x]=++cl_cnt,sz[cl_cnt]=top;
        while(sta[top]!=x) {
            bo[sta[top]]=0,cl[sta[top]]=cl_cnt;
            top--;
        }
        top--;sz[cl_cnt]-=top;
    }
}
int main(int argv,char*argc[]){
    read(n);
    for (int x,i=1; i<=n; ++i) read(x),ins(i,x);
    for (int i=1; i<=n; ++i) if (!dfn[i]) Tarjan(i);
    for (int i=1; i<=cl_cnt; ++i) if (sz[i]>1) ckmin(ans,sz[i]);
    wt(ans,'\n');
    return 0;
}



点我回到主页

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google photo

You are commenting using your Google account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s