题解：CF1361E James and the Chase

· · 题解

Sol

不难想到如何判定一个点是不是好点，只要以其为根的 DFS 树上只有树上边和返祖边即可。

但这么判还是太慢了。事实上，当找出一个好点以及相应 DFS 树时，就已经可以找到所有好点了。有结论，除了根节点外，一个点为好点当且仅当其子树中有且仅有一条返祖边指向其祖先，且指向的祖先为好点。这是因为当前已经没有前向边与兄弟边了，故而每个点只需要考虑到其父亲的路径方案数。证明是显然的。树上差分存返祖边数，然后再对每个点记一下可以走到的最浅的祖先即可。

这要求我们找到一个好点，由于题目规定好点数量应超过 20\%，故而直接随一百个试就行。

Code

const int N=1e5+5;

int n,m;
vec<int> g[N];
int dfn[N],dcnt,to[N],cf[N],f[N];
bool ins[N];

bool dfs(int x){
    dfn[x]=++dcnt;to[dcnt]=x;
    ins[x]=1;
    for(auto y:g[x]){
        if(!dfn[y]){if(!dfs(y))return 0;cf[x]+=cf[y],chmin(f[x],f[y]);}
        else if(!ins[y])return 0;
        else ++cf[x],--cf[y],chmin(f[x],dfn[y]);
    }
    ins[x]=0;
    return 1;
}

auto rnd=mt19937(10170111);
inline void Main(){
    cin>>n>>m;
    rep(i,1,n)g[i].clear();
    rep(i,1,m){
        int a,b;cin>>a>>b;
        g[a].pub(b);
    }
    rep(i,1,100){
        int x=rnd()%n+1;
        if([&](){
            dcnt=0;
            rep(i,1,n)dfn[i]=cf[i]=0,f[i]=n+1;
            return dfs(x);
        }()){
            vec<int> ans;
            ans.pub(x);ins[1]=1;
            rep(i,2,n)if(cf[to[i]]==1&&ins[f[to[i]]])ans.pub(to[i]),ins[i]=1;
            if(ans.size()<(n+4)/5)put(-1);
            else{
                sort(ans.begin(),ans.end());
                for(auto i:ans)cout<<i<<" ";
                put("");
            }
            return;
        }
    }
    return put(-1),void();
}