[POI2004] SZP
题目描述：
Byteotian 中央情报局（BIA）雇佣了许多特工。他们每个人的工作就是监视另一名特工。Byteasar 国王需要进行一次秘密行动，所以他要挑选尽量多的信得过的特工。但是这项任务是如此的机密以至于所有参加行动的特工都必须至少被另一名没有参加任务的特工所监视（就是说如果某个特工参加了行动，那么原先监视他的那些特工中至少要有一个没有参加进行动）。
给出监视任务的详情，要求计算最多能有多少个特工参与其中。
数据范围：
\(1\leq k,a_k\leq n\leq 10^6\)
思路：
我们先把这个图建出来，然后仔细观察一下这个图，发现是个基环树。然后对于基环树的题目，常规考虑方式就是环和树分开来考虑。
先考虑树的情况。发现一个第一眼看起来不是很正确的贪心：对于一个节点，如果可以选择，则就必须选择。
证明：其实在一开始想到这个贪心的时候，我甚至认为这个玩意是错的。但是实际上，我们仔细想一下，会发现在树上的情况肯定是要这样选的。假设我们并没有选择这个节点 \(u\)，则要选择 \(a_u\) 这个节点，发现无论选哪个点，他们的贡献都是一样的。与其等着选后面的点，不如就选择这个点，这样后面还能有更多的可能性选择更多的点，因为他影响的位置提前了。如果不太好理解，其实可以画一个链来模拟一下。
我们对于每个树跑完后，最终就会获得若干环。可以发现，环上的点其实和外面的树之间并没有太多关系，所以钦定环上一个点选择了，然后尽可能多的选择点，其实说白了就是 \(\frac{m}{2}\)，\(m\) 为环中节点数量。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define mem(a) memset(a,0,sizeof(a))
#define set(a,b) memset(a,b,sizeof(a))
#define ls i<<1
#define rs i<<1|1
#define pb(x) push_back(x)
#define pt(x) putchar(x)
#define T int t;cin>>t;while(t--)
#define rand RAND
using namespace std;
char buf[1<<20],*p1,*p2;
#define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
template<class Typ> Typ &re(Typ &x){char ch=gc(),sgn=0; x=0;for(;ch<'0'||ch>'9';ch=gc()) sgn|=ch=='-';for(;ch>='0'&&ch<='9';ch=gc()) x=x*10+(ch^48);return sgn&&(x=-x),x;}
template<class Typ> void wt(Typ x){if(x<0) putchar('-'),x=-x;if(x>9) wt(x/10);putchar(x%10^48);}
const int inf=0x3f3f3f3f3f;
const int maxn=1e6+5;
const int mod=1e9+7;
int seed = 19243;
unsigned rand(){return seed=(seed*48271ll)%2147483647;}
int n;
int to[maxn],ind[maxn];
int vis[maxn],use[maxn];
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>to[i];
ind[to[i]]++;
}
queue<int>Q;
for(int i=1;i<=n;i++)if(!ind[i])Q.push(i);
int ans=0;
while(!Q.empty()){
int u=Q.front();
Q.pop();
vis[u]=1;
ans+=use[u];
if(!use[to[u]]&&!use[u]){
use[to[u]]=1;
Q.push(to[u]);
}
if(!--ind[to[u]]&&!use[to[u]]){
Q.push(to[u]);
}
}
for(int i=1;i<=n;i++){
if(vis[i])continue;
int cnt=0;
for(int j=i;!vis[j];j=to[j]){
cnt++;
vis[j]=1;
}
ans+=cnt/2;
}
cout<<ans<<endl;
return 0;
}