拓扑排序·二:有向无环图,求总的病毒感染数

http://hihocoder.com/problemset/problem/1175

举个例子,假设切断部分网络连接后学校网络如下图所示,由4个节点和4条链接构成。最开始只有节点1上有病毒。

最开始节点1向节点2和节点3传送了病毒,自身留有1个病毒:

其中一个病毒到达节点2后,向节点3传送了一个病毒。另一个到达节点3的病毒向节点4发送自己的拷贝:

当从节点2传送到节点3的病毒到达之后,该病毒又发送了一份自己的拷贝向节点4。此时节点3上留有2个病毒:

最后每个节点上的病毒为:

小Hi和小Ho根据目前的情况发现一段时间之后,所有的节点病毒数量一定不会再发生变化。那么对于整个网络来说,最后会有多少个病毒呢?

提示:拓扑排序的应用

输入

第1行:3个整数N,M,K,1≤K≤N≤100,000,1≤M≤500,000

第2行:K个整数A[i],A[i]表示黑客在节点A[i]上放了1个病毒。1≤A[i]≤N

第3..M+2行:每行2个整数 u,v,表示存在一条从节点u到节点v的网络链接。数据保证为无环图。1≤u,v≤N

输出

第1行:1个整数,表示最后整个网络的病毒数量 MOD 142857 样例输入

14 4 1 21 31 2 41 3 52 3 63 4 7
1 样例输出 2
16 2
1#include <iostream> 2#include <vector> 3#include <queue> 4using namespace std; 5 6#define MOD 142857 7 8int N, M, K;//全局变量是因为solve()中没有定义。 9vector<vector<int>> graph; 10vector<int> inDegree; 11vector<int> virus; 12int m, u, v; 13 14void solve() {//拓扑排序 严蔚敏182页算法介绍 15 int res = 0; 16 queue<int> que;//队列存放入度为0的节点。 17 for (int i = 1; i <= N; ++i) if(inDegree[i] == 0) que.push(i); 18 19 while (!que.empty()) { 20 int u = que.front();//获得 队首元素 21 que.pop();//删除 队首元素 22 for (unsigned int i=0;i<graph[u].size();i++) { 23 int v=graph[u][i];//取出graph[u]中的第i个元素v,如graph[1]={2,3}; 24 virus[v] += virus[u];//virus[v=2]=virus[v=2]+virus[u=1]。 25 virus[v] %= MOD; 26 --inDegree[v];//因为删了起点u=1,所以终点v=1的入度减1. 27 if (inDegree[v] == 0) que.push(v); 28 }//for end 29 }//while end 30 31 for (unsigned int i=0;i<virus.size();i++) { 32 res += virus[i];//遍历所有节点,求病毒总数。 33 res %= MOD; 34 } 35 //cout <<"res=" << res << endl; 36 cout << res << endl; 37} 38 39int main() { 40 // cout <<"请输入:" << endl; 41 while (cin >> N >> M >> K) { 42 graph.assign(N + 1, vector<int>());//N+1因为腾出0不用,用u作为第一个下标。 43 virus.assign(N + 1, 0);//assign初始化全0. 44 inDegree.assign(N + 1, 0); 45 for (int i = 0; i < K; ++i) { 46 cin >> m; 47 virus[m] = 1;//表示黑客在节点m上放了1个病毒 48 } 49 for (int i = 0; i < M; ++i) { 50 cin >> u >> v;//从起点u到终点v. 51 graph[u].push_back(v);//起点u对应的终点向量是graph[u]。 52 ++inDegree[v];//节点v入度加1. 53 } 54 solve(); 55 } 56 system("pause"); 57 return 0; 58} 59

代码交流 2021