LUOGU P2921 [USACO08DEC]在农场万圣节Trick or Treat on the Farm

解题思路

记忆化搜索，如果搜到环，就将环的大小处理出来。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

const int MAXN = 100005;

inline int rd(){

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}

    while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

    return x*f;

}

int n,nxt[MAXN],f[MAXN];

int vis[MAXN],num,k;

inline int solve(int x){  //处理环的大小

    int ret=0;int pre=x;

    while(nxt[x]!=pre) {

        ret++;

        x=nxt[x];

    }

    return ret+1;

}

inline int dfs(int x){

    if(f[x]) return f[x];

    if(vis[x]==num){

        if(x==nxt[x]) return 0;

        f[x]=solve(x);k=x;return f[x];

    }

    vis[x]=num;

    int F=dfs(nxt[x]);

    if(!k) {f[x]=F+1;return F+1;}  //k表示是否成环

    else if(k==x) {k=0;f[x]=F;return F;}

    else {f[x]=F;return F;}

}

int main(){

    n=rd();

    for(register int i=1;i<=n;i++) nxt[i]=rd();

    for(register int i=1;i<=n;i++){

        k=0;num++;

        printf("%d\n",dfs(i));

    }

    return 0;

}

巴特西

LUOGU P2921 [USACO08DEC]在农场万圣节Trick or Treat on the Farm

解题思路

代码

最新文章

热门文章