题目

给出一棵树和一些限制关系 \((a_i,b_i)\)，

一种合法的删点序列当且仅当删除一个点之后树的大小不超过 1 或不存在孤立点，

并且 \(a_i\) 要比 \(b_i\) 先删除，问 \(\forall x\in [1,n]\)，是否可能为合法删点序列的末项

分析

考虑到限制就是 \(a_i\) 不包含 \(b_i\) 的那些子树包括 \(a_i\) 本身不可能为末项。

并且如果有一个点可能为末项，那么与其不通过被限制的点相连的也可以成为末项。

所以只要找到一个合法的末项即可，如果没有限制随便挑一个就行了。

考虑把限制看成单向边，每次把所谓的叶子加进队列，

如果叶子发现度数为 0 说明无论限制还是树均被满足，那么它就可以成为末项

代码

#include 
#include 
#include 
using namespace std;
const int N=100011;
struct node{int y,next;}e[N<<1]; vectorG[N];
int as[N],ans[N],q[N],head=1,tail,deg[N],n,et=1,m,rt;
int iut(){
	int ans=0; char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=ans*10+c-48,c=getchar();
	return ans;
}
int Topsort(){
	for (int i=1;i<=n;++i)
	    if (deg[i]==1) q[++tail]=i;
	while (head<=tail){
		int x=q[head++];
		if (deg[x]<1) return x;
		for (int i=as[x];i;i=e[i].next)
		    if (--deg[e[i].y]==1) q[++tail]=e[i].y;
		for (int i=0;i<(int)G[x].size();++i)
		    if (--deg[G[x][i]]==1) q[++tail]=G[x][i];
	}
	return tail==n;
}
void dfs(int x){
	ans[x]=1;
	for (int i=as[x];i;i=e[i].next)
	    if (!ans[e[i].y]) dfs(e[i].y);
}
int main(){
	n=iut(),m=iut();
	for (int i=1;i