hihocoder 1175 难题解析：拓扑排序二如何解决？

本文共计512个文字，预计阅读时间需要3分钟。

题目链接：链接：链接内容摘要：题目：无环有向图排序意义：有一张无环有向图，图中节点初始时有一些病毒。节点会将病毒传播给其后续节点，问最终所有节点所携带的病毒总数。

思路：

1.拓扑排序

2.从每个节点开始，计算传播到最终节点的病毒数，累加得到总数。

题目链接：​​拓扑排序·二​​

题目大意：有一张无环的有向图，刚开始有一些结点有病毒，他会把他所有的病毒传染到后继结点，问最后所有点的病毒总数

题目思路：拓扑排序，从入度为零的结点开始，删的时候传递结点病毒数就好了

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>

using namespace std;
const int maxn = 1e5+10;
const int mod = 142857;

vector<int>vec[maxn];
int InDeg[maxn],virus[maxn];
queue<int>q;
int T,n,m,k,u,v,x,ans;

void topsort(){
while(!q.empty()) q.pop();
for(int i = 1;i <= n;i++) if(!InDeg[i]) q.push(i);
while(!q.empty()){
int now = q.front();
q.pop();
for(int i = 0;i < vec[now].size();i++){
if(--InDeg[vec[now][i]] == 0) q.push(vec[now][i]);
virus[vec[now][i]] = (virus[vec[now][i]]+virus[now])%mod;
}
}
}

int main(){
while(~scanf("%d%d%d",&n,&m,&k)){
for(int i = 1;i <= n;i++) vec[i].clear();
memset(InDeg,0,sizeof(InDeg));
memset(virus,0,sizeof(virus));
while(k--){
scanf("%d",&x);
virus[x]++;
}
while(m--){
scanf("%d%d",&u,&v);
vec[u].push_back(v);
InDeg[v]++;
}
topsort();
for(int i = 1;i <= n;i++) ans = (ans+virus[i])%mod;
printf("%d\n",ans);
}
return 0;
}