拓扑排序 hihoCoder1175 拓扑排序·二

按照拓扑排序的顺序去扩展病毒数量,这样相当于所有节点只走了一遍就出了结果


#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;
typedef long long LL;

const int mod=142857;
const int MX=100000+5;
const int INF=0x3f3f3f3f;

int vis[MX],A[MX],S[MX];
vector<int>G[MX];

int main(){
    int n,m,k;
    while(~scanf("%d%d%d",&n,&m,&k)){
        memset(A,0,sizeof(A));
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++) G[i].clear();

        for(int i=1;i<=k;i++){
            int x;
            scanf("%d",&x);
            S[x]++;
        }

        for(int i=1;i<=m;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
            A[v]++;
        }

        int ans=0;
        queue<int>work;

        for(int i=1;i<=n;i++){
            if(A[i]==0) work.push(i);
        }
        while(!work.empty()){
            int fp=work.front();
            work.pop();

            ans=(ans+S[fp])%mod;

            for(int i=0;i<G[fp].size();i++){
                int v=G[fp][i];
                S[v]=(S[v]+S[fp])%mod;

                A[v]--;
                if(!A[v]) work.push(v);
            }
        }

        printf("%d\n",ans);
    }
    return 0;
}
相关文章
相关标签/搜索
本站公众号
   欢迎关注本站公众号,获取更多程序园信息
开发小院