题解：P10933 创世纪

· · 题解

题目大意

给定一张内向基环树，求最多能选定几个点使得每个被选定的点都有至少一条未被选定的点指向它的边。

题解

特别的，以下对于 a_i=j 称 j 为 i 的父亲。

题解都是树形 dp 啊，考虑拓扑加贪心，注意到几个性质：

  1. 叶子节点绝对不能被选定，于是它的父亲就一定可以被选定，于是当拓扑时遇到了叶子节点就将它和父亲删掉并把答案加一。

  2. 对于一个大小为 siz 的环，答案显然为 \left \lfloor{siz/2 } \right \rfloor （隔一个选一个），拓扑后找环即可。

关于正确性，注意到将叶子和其父亲删掉最多破坏一个贡献，但一定会产生一个贡献。

#include<bits/stdc++.h>
using namespace std;
namespace j8{
int n,a[1001000],st[1001000],ru[1001000],tot,ans,vis[1001000];
string main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        ru[a[i]]++;
    }
    for(int i=1;i<=n;i++){
        if(!ru[i]){
            st[++tot]=i;
        }
    }
    while(tot){
        int x=st[tot],f=a[x];
        tot--;
        if(vis[x]){
            continue;
        }
        vis[x]=1;
        ru[f]--;
        if(!ru[f]){
            st[++tot]=f;
        }
        if(!vis[f]){
            vis[f]=1;
            ans++;
            ru[a[f]]--;
            if(!ru[a[f]]){
                st[++tot]=a[f];
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(vis[i]){
            continue;
        }
        vis[i]=1;
        int cnt=1,x=a[i];
        while(x!=i){
            vis[x]=1;
            x=a[x];
            cnt++;
        }
        ans+=cnt/2;
    }
    cout<<ans<<'\n';
    return "LEWISAK";
}
}
int main(){
    cerr<<j8::main();
    return 0;
}