免费打开网站,江西城乡建设部网站首页,微站是什么东西,北京到安阳的火车票Codeforces1019C 题意#xff1a;一张无自环的有向图#xff0c;请找出一个点集Q#xff0c;满足Q内的点不能互相有边#xff0c;且Q内的点一定可以通过1次或2次移动#xff0c;到达Q集合以外的任意一个点。 做法#xff1a;思路神奇。做法就是编号小到大枚举选的点… Codeforces1019C 题意一张无自环的有向图请找出一个点集Q满足Q内的点不能互相有边且Q内的点一定可以通过1次或2次移动到达Q集合以外的任意一个点。 做法思路神奇。做法就是编号小到大枚举选的点然后把比他大的后继删除再从大到小枚举继续删除这被选中的点中互相有边的情况。正确性可以这么考虑第一次选出的点保证了现在的点集通过一次移动即可到达任意其余的点且所选点集中编号小的点与编号大的点之间没有边。第二次删除了编号大的到编号小的点之间的边现在已经保证点集内部没有边了考虑删除的点我们可通过将他删除的那个点到达它及与它相连的不在点集中的点。 #include bits/stdc.h
#define rep(i,a,b) for(int ia;ib;i)
#define per(i,a,b) for(int ia;ib;--i)
#define pb push_back
typedef long long ll;
const int N 1e6 7;
using namespace std;
int n,m,vis[N],cc;
vectorint 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
