asp.net+制作网站开发,湛江网站制作专业,一个服务器做两个网站吗,自己做网站步骤 域名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
