这题非常好。。看似很简单其实比较复杂,交了一堆假算法全wa了。。
看题解也好久才弄明白
/* 给定一张有向图,确定一个点T,问有多少T0,满足所有T0->T的路径,都经过边(T0,T) 建立反图,T变为起点,求所有T0,满足T->T0所有路径都经过(T,T0) 首先确定用bfs,我们从每个和T连边T0的点开始bfs,vis[]数组记录每个点被访问的次数,如果T0被访问的次数=1,说明符合要求 但是根据题意,我们要处理两个问题: 1.有形如T->T0->T1->T2->T0的边路径,此时T0任然满足要求,但是被访问了两次 2.根据1,我们如何判断T0第二次被访问时任是通过(T,T0)这天边的 解决方法:每个点u入队时维护一个pair<u,u的起始点src>,当我们访问到u时,将这个pair从queue取出 此时如果u!=src,说明u是从别的源跑过来的, 否则如果u==src,说明u本身就是源,如果vis[u]!=0,说明此时从u出发访问了一圈又回到了u,就不用再bfs下去,反之u这个源刚开始访问,要bfs下去 */ #include<bits/stdc++.h> using namespace std; #define N 300005 #define mk make_pair vector<int>G[N]; int n,m,t,vis[N],f[N]; void bfs(int T){ queue<pair<int,int> >q; for(auto v:G[T]) q.push(mk(v,v)); while(q.size()){ int u=q.front().first,src=q.front().second; q.pop(); /* 这里为什么vis[u]>=3才continue? 一个非初始点如果在一个环内,那么前两次访问可能是交给这个环的,当其他初始点需要从这个点切入环时,就要访问一次这个点 所以vis[u]的上限要设为3(如果为2,那么其他s初始点就切不进来了) */ if(vis[u]>=3)continue; if(u!=src || u==src&&!vis[u])vis[u]++;//如果u!=其源点,那么随便怎么松弛都可以,如果u==其源点,那么不能再访问了 else continue; for(auto v:G[u]) if(v!=T)q.push(mk(v,src)); } } int main(){ //freopen("hand01.in","r",stdin); cin>>n>>m>>t;t++; for(int i=1;i<=m;i++){ int u,v;scanf("%d%d",&u,&v); u++;v++; if(v==t)f[u]=1; G[v].push_back(u); } bfs(t); vector<int>ans; for(int i=1;i<=n;i++) if(f[i] && vis[i]<=1)ans.push_back(i); cout<<ans.size()<<'\n'; for(auto x:ans)cout<<x-1<<"\n"; }