记忆宫殿

思路

• 我们此时需要判断出那些点的地位是等价的。即如果$A$发生$B$一定发生。
• 通过寻找规律可以发现
  
• 对于这样的$A,B$两点是等价的。

#include
using namespace std;
const int M=1e3+5;
bool to[M][M],son[M],same[M][M],vis[M];
vector<int>G[M];
int n,m,k,x,y,cas;
void dfs(int x){if(to[cas][x])return;to[cas][x]=1;for(int i=0;iint main(){memset(same,1,sizeof(same));scanf("%d %d %d",&n,&m,&k);while(m--){scanf("%d %d",&x,&y);G[x].push_back(y);son[y]=1;}for(cas=1;cas<=n;cas++)dfs(cas);/*找到和X代价的点,即可以达到X且度为0的节点可以达到点的交集*/for(cas=1;cas<=k;cas++){scanf("%d",&x);vis[x]=1;for(int i=1;i<=n;i++)if(!son[i]&&to[i][x])for(int j=1;j<=n;j++)same[cas][j]&=to[i][j];for(int i=1;i<=n;i++)vis[i]|=same[cas][i];}for(int i=1;i<=n;i++)if(vis[i])printf("%d ",i);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！