Sol

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

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

这要求我们找到一个好点，由于题目规定好点数量应超过

20\%

，故而直接随一百个试就行。

Code

CPP

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();
}

题解：CF1361E James and the Chase

文章操作

Sol

Code

相关推荐

评论

题解：CF1361E James and the Chase