【洛谷P2921】Trick or Treat on the Farm

题目大意：给定一个 N 个节点的内向树森林，求从每个顶点出发能够到达的最多不重复顶点的个数是多少。

题解：内向树森林是由一个或若干个环加若干条链构成。可以先按照类似于拓扑排序的规则进行删链，再对环上的点计算答案，最后计算链上的答案即可。

代码如下

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;

int n,ans,to[maxn],indeg[maxn];
bool vis[maxn];

void read_and_parse(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&to[i]),++indeg[to[i]];
}

void del(int u){
    vis[u]=1;
    if(!--indeg[to[u]])del(to[u]);
}

int cyc(int u,int dep){
    vis[u]=1;
    if(vis[to[u]])return dep;
    else return cyc(to[u],dep+1);
}

void solve(){
    ans=0x3f3f3f3f;
    for(int i=1;i<=n;i++)if(!indeg[i]&&!vis[i])del(i);
    for(int i=1;i<=n;i++)if(indeg[i]&&!vis[i])ans=min(ans,cyc(i,1));
    printf("%d\n",ans);
}

int main(){
    read_and_parse();
    solve();
    return 0;
}

【洛谷P2921】Trick or Treat on the Farm

原文：https://www.cnblogs.com/wzj-xhjbk/p/10202256.html