记忆宫殿

思路

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

#include<bits/stdc++.h>
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;i<G[x].size();i++)dfs(G[x][i]);
}
int 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;
}

最后

以上就是执着画笔为你收集整理的记忆宫殿的全部内容，希望文章能够帮你解决记忆宫殿所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。