分析：首先我们来想一下为什么答案不会是0。如果答案为0，就意味着每个节点都在某个(不同)回合没有了牛。因为所有节点的出度都=1，所以从节点A到节点B的路(无论是直接还是间接)有且仅有一条，并且节点A在最多一个环中。所以如果节点A一旦失去了所有的牛，那么就再也不会有任何的牛到达节点A。
举一个例子。设想节点A。如果想要A失去所有牛之后再获得牛，那么我们可以知道至少有一个节点(记为B)有一条到A的有向边(记为B->A)。因为我们需要让A先失去牛，所以当A有牛时，B必然没有牛(因为B不能再向其他节点连边)，而下一个回合，A失去牛之后，B又要拥有牛。回到初始状态，所有节点都有一只牛，因此不会出现A(或B)先失去牛又获得牛的情况。
那么现在知道了如果节点A一直都拥有牛，那么A必定在一个环内。
关于怎么求环嘛...不难发现这是一个内向树(其实是森林), 然后很好证明内向树里面的环肯定是自环或者大小不为\(1\)的强联通分量, 所以跑一跑tarjan求出大小不为\(1\)的强联通分量, 然后特判求自环就好啦!
ps: 其实可以排除不在环内的点再判环输出答案, 比我的做法不知道高到哪儿去了.
#include#include #include #include #include using namespace std;const int MAXN = 1e5 + 20;inline int read(){ int x = 0; char ch = getchar(); while(!isdigit(ch)) ch = getchar(); while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar(); return x;}int N;int a[MAXN], ans = 0;namespace SCC{ stack sta; int low[MAXN], dfn[MAXN]; bool ins[MAXN]; int tarjan(int cur){ static int dfnclock = 0; dfn[cur] = low[cur] = ++dfnclock; sta.push(cur), ins[cur] = true; int v = a[cur]; if(!dfn[v]) low[cur] = min(low[cur], tarjan(v)); else if(ins[v]) low[cur] = min(low[cur], dfn[v]); if(dfn[cur] == low[cur]){ int cnt = 0; do{ v = sta.top(); sta.pop(); ins[v] = false; ++cnt; }while(v != cur); if(cnt > 1) ans += cnt; } return low[cur]; } void solve(){ for(int i = 1; i <= N; i++) if(!dfn[i]) tarjan(i); for(int i = 1; i <= N; i++) if(a[i] == i) ++ans; }}int main(){ cin>>N; for(int i = 1; i <= N; i++) a[i] = read(); SCC::solve(); cout< <