自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 23:10:26，当前版本为作者最后更新于2025-02-25 07:58:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

如果整张图已经是 DAG 了，输出 NIE。

那么一个点在所有回路上的充要条件是，删掉他之后图是一张 DAG。不过如果你做了这样的转化，你很大概率是写不出一些正经做法的。原因在于，DAG 的结构太过复杂，没有非常优秀的处理方法。

我们可以找到一个环。显然答案只能是这个环上的节点。

如果删掉这个环之后不是 DAG，那么至少有两个无交环，答案是空集。

否则，所有可能的回路都形如：从环上的一个点出发，走外层 DAG，回到环上的另一个点。

稍微画个图：

加上环上两点 $S$ 和 $T$，存在一条路径满足，首尾分别是 $S$ 和 $T$，且中间不经过环上任意元素，则 $S\to T$ 在环上的路径中除了 $S$ 和 $T$ 以外的节点都不会在回路的交上。（注意，$S=T$ 可能发生，这代表有一个只经过 $S$ 的回路。）

如果能把所有的 $(S,T)$ 找出来，我们已经能找到一个必要条件了。

下面证明：如果一个点不会被任何一个类似的 $S \to T$ 覆盖，那么他是合法的。

这个实际上相当简单。因为此时任何一个回路，都不可能跨过该点，必须直接走过去。

假设环上的点编号是 $1$ 到 $k$。

对于 $S$ 而说，我们可以通过 DAG 上记忆化搜索求出最大的 $T$ 使得 $S \to T$ 路径存在，以及最小的 $T$ 使得 $S \to T$ 的路径存在。

如果 $T_{\max} \ge S$，显然让 $(S,T_{\max})$ 中所有元素都不合法即可。

如果 $T_{\min} \le S$，则设 $T_0$ 为 $\le S$ 且能由 $S$ 到达的最大的节点，则 $(S,k] \cup [1,T_0)$ 都不合法。

可惜我们不太好找 $T_0$。不过把整张图反过来，通过 $T_0$ 找 $S$ 即可。（注：对于 $S$ 而言，如果 $T_{\min} \le S$，我们将 $(S,k]$ 记为不合法。而 $[1,T_0)$ 这一段通过枚举 $T_0$ 判断是否有 $S$ 进行判定。）

使用前缀和维护不合法的标记。

复杂度 $O(n+m)$（如果实现不好，会在输出的时候带 $\log$，只需要把最终的排序改成桶排就可以做到严格线性了。/tuu）

挺可爱的代码：

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=5e5+10;
int n,m,vis[MAXN],pre[MAXN],ok[MAXN];
vector<int> G[MAXN],g[MAXN];
vector<int> cir;
void dfs(int u,int rt) {
	vis[u]=1;
	for(auto v:G[u]) {
		if(v==rt) {
			int tmp=u;
			while(tmp!=rt) cir.push_back(tmp),tmp=pre[tmp];
			cir.push_back(rt);
			reverse(cir.begin(),cir.end());
			return ;
		}
		if(vis[v]) continue ;
		pre[v]=u,dfs(v,rt);
		if(!cir.empty()) return ;
	}
	return ;
}
//=====tarjan=====
int dfn[MAXN],low[MAXN],in[MAXN],tot;
int col[MAXN],cs,ccnt[MAXN];
stack<int> st;
void tarjan(int u) {
	dfn[u]=low[u]=++tot,in[u]=1,st.push(u);	
	for(auto v:G[u]) if(!ok[v]) {
		if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
		else if(in[v]) low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u]) {
		++cs,ccnt[cs]=0;
		while(1) {
			int v=st.top();
			st.pop();
			col[v]=cs,ccnt[cs]++,in[v]=0;
			if(u==v) return ;
		}
	}
	return ;
}
//====tarjan=====
int prex[MAXN];
void del(int l,int r) {
	l=max(1,l),r=min((int)cir.size(),r);
	if(l>r) return ;
	prex[l]++,prex[r+1]--;
	return ;
}
int mx[MAXN],mn[MAXN];
void solve1(int u) {
	if(vis[u]) return ;
	vis[u]=1;
	if(ok[u]) return mx[u]=mn[u]=ok[u],void();
	mx[u]=0,mn[u]=n+1;
	for(auto v:G[u]) {
		solve1(v);
		mx[u]=max(mx[u],mx[v]);
		mn[u]=min(mn[u],mn[v]);
	}
	return ;
}
void solve2(int u) {
	if(vis[u]) return ;
	vis[u]=1;
	if(ok[u]) return mx[u]=mn[u]=ok[u],void();
	mx[u]=0,mn[u]=n+1;
	for(auto v:g[u]) {
		solve2(v);
		mx[u]=max(mx[u],mx[v]);
		mn[u]=min(mn[u],mn[v]);
	}
	return ;
}
int main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	ffor(i,1,m) {int u,v;cin>>u>>v,G[u].push_back(v),g[v].push_back(u);}
	ffor(i,1,n) if(!dfn[i]) tarjan(i);
	int rt=-1;
	ffor(i,1,n) if(ccnt[col[i]]>1) rt=i;
	if(rt==-1) return cout<<"NIE",0;
	dfs(rt,rt);
	ffor(i,0,cir.size()-1) ok[cir[i]]=i+1;
	
	tot=0,cs=0;
	ffor(i,1,n) dfn[i]=low[i]=col[i]=0;
	ffor(i,1,n) if(!ok[i]&&!dfn[i]) tarjan(i);
	ffor(i,1,n) if(!ok[i]&&ccnt[col[i]]>1) return cout<<0<<'\n',0;
	

	memset(vis,0,sizeof(vis));
	for(auto id:cir) {
		for(auto to:G[id]) {
			solve1(to);
			if(mx[to]&&mx[to]>=ok[id]) del(ok[id]+1,mx[to]-1);
			if(mn[to]!=n+1&&mn[to]<=ok[id]) del(ok[id]+1,cir.size());
		}
	}
	memset(vis,0,sizeof(vis));
	for(auto id:cir) {
		for(auto to:g[id]) {
			solve2(to);
			if(mx[to]&&mx[to]>=ok[id]) del(1,ok[id]-1);
		}
	}
	
	ffor(i,1,cir.size()) prex[i]+=prex[i-1];
	vector<int> ans;
	ffor(i,1,cir.size()) if(!prex[i]) ans.push_back(cir[i-1]);
	sort(ans.begin(),ans.end());
	cout<<ans.size()<<'\n';
	for(auto id:ans) cout<<id<<' ';
	return 0;
}