題目鏈接：Birdwatching

---

顯然，只有直接與T相連的點，才可能成為答案。

對于一個點，可以成為答案，那么證明他可以到其他與T直接相鄰的點。所以我們只需要知道每個點是否可以由直接與T相鄰的點到達，所以建立反圖，然后二進制分組即可。

---

AC代碼：

#pragma GCC optimize("-Ofast","-funroll-all-loops") #include<bits/stdc++.h> //#define int long long using namespace std; const int N=1e5+10; int n,m,s,vis[N],mark[N],st[N]; vector<int> g[N],res,v; queue<int> q; inline void bfs(){while(q.size()){int u=q.front(); q.pop();for(auto to:g[u]) if(!vis[to]&&to!=s) vis[to]=1,q.push(to);}for(int i=1;i<=n;i++) if(mark[i]&&vis[i]) st[i]=1; } signed main(){cin>>n>>m>>s; s++;for(int i=1,a,b;i<=m;i++){scanf("%d %d",&a,&b),a++,b++,g[b].push_back(a);if(b==s) v.push_back(a);}for(int s=0;s<=17;s++){memset(vis,0,sizeof vis),memset(mark,0,sizeof mark);for(int i=0;i<v.size();i++){if(v[i]>>s&1) q.push(v[i]),vis[v[i]]=1;else mark[v[i]]=1;}bfs();memset(vis,0,sizeof vis),memset(mark,0,sizeof mark);for(int i=0;i<v.size();i++){if(!(v[i]>>s&1)) q.push(v[i]),vis[v[i]]=1;else mark[v[i]]=1;}bfs();}for(int i=0;i<v.size();i++) if(!st[v[i]]) res.push_back(v[i]);sort(res.begin(),res.end());cout<<res.size()<<endl;for(auto i:res) printf("%d\n",i-1);return 0; }

總結

以上是生活随笔為你收集整理的Birdwatching的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。