Link

考虑先把所有边反向,问题转化为从 k k k出发,在不经过 k − > v k->v k−>v路径的条件下无法到达点 v v v的合法 v v v个数

一个点 v v v和 k k k有边时,由于是反向图

我们从 k k k走到 v v v再走到 u u u,此时在原图中就存在 u − > v − > k u->v->k u−>v−>k这条路径

那么点 u u u显然不是一个合法点

就这样我们不断枚举和 k k k相邻的点 v v v,然后钦定 v − > k v->k v−>k是原图路径的最后一步

于是我们在反向图上 b f s bfs bfs,能到的点都是在原图中可达 k k k且不通过自己和 k k k的直连边

这样每个点只会被 b f s bfs bfs到最多两次(打标记)

复杂度 O ( n ) O(n) O(n)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+10;
int n,m,k,ans[maxn],pre[maxn];
vector<int>vec[maxn];
void bfs(int s)
{
	queue<int>q; q.push( s );
	ans[s]++; pre[s] = s;
	while( !q.empty() )
	{
		int u = q.front(); q.pop();
		for(auto v:vec[u] )
		{
			if( ans[v]>=2 || v==k || v==s )	continue;
			if( pre[v]!=s )	ans[v]++, pre[v] = s, q.push( v );
		}
	}
}
signed main()
{
	cin >> n >> m >> k;
	for(int i=1;i<=m;i++)
	{
		int l,r; cin >> l >> r;
		vec[r].push_back( l );
	}
	for(auto v:vec[k] )	bfs( v );
	vector<int>res;
	for(auto v:vec[k] )	
		if( ans[v]<2 )	res.push_back( v );
	cout << res.size() << endl;
	for(auto v:res )	cout << v << endl;
}