Codeforces1019C

---

題意：一張無自環的有向圖，請找出一個點集Q，滿足Q內的點不能互相有邊，且Q內的點一定可以通過1次或2次移動，到達Q集合以外的任意一個點。

做法：思路神奇。做法就是編號小到大枚舉選的點，然后把比他大的后繼刪除，再從大到小枚舉，繼續刪除這被選中的點中互相有邊的情況。正確性可以這么考慮，第一次選出的點保證了現在的點集通過一次移動即可到達任意其余的點，且所選點集中編號小的點與編號大的點之間沒有邊。第二次刪除了編號大的到編號小的點之間的邊，現在已經保證點集內部沒有邊了，考慮刪除的點，我們可通過將他刪除的那個點到達它及與它相連的不在點集中的點。

#include <bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;++i) #define per(i,a,b) for(int i=a;i>=b;--i) #define pb push_back typedef long long ll; const int N = 1e6 + 7; using namespace std; int n,m,vis[N],cc; vector<int> G[N];int main() {scanf("%d%d",&n,&m);int x,y;rep(i,1,m) scanf("%d%d",&x,&y),G[x].pb(y);rep(i,1,n) if(!vis[i]) {vis[i] = 1;for(auto v: G[i]) if(!vis[v]) vis[v] = -1;}per(i,n,1) if(vis[i]==1) {++cc;for(auto v: G[i]) vis[v]=-1;}printf("%d\n",cc);rep(i,1,n)if(vis[i]==1)printf("%d ",i);puts(""); }

轉載于:https://www.cnblogs.com/RRRR-wys/p/9471864.html

總結

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

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