Who's Studio.

hihoCoder#1175 - 拓扑排序·二

Word count: 370Reading time: 1 min
2016/05/10

题目

给定一个有向无环图，在任意个节点上投放“病毒”，“病毒”会沿着有向边传播。计算最终该图中总共有多少“病毒”。
具体描述请见hihoCoder。

解题思路

因为是有向无环图，可以找到一个“起始点”，该点入度为0。从该点出发进行广度优先搜索，该点处理完后可以直接从图中移除。依次重复此操作。

时间复杂度

每个节点入队一次，每条边遍历依次，时间复杂度为N + M。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Vertex {
	int sum = 0;
	int degree = 0;
	vector<int> neighbors;
};

int calSum(vector<Vertex> A) {
	queue<int> queue;

	for (int i = 0; i < A.size(); i++)
		if (A[i].degree == 0)
			queue.push(i);

	int sum = 0;
	do {
		int root = queue.front();
		queue.pop();
		int curSum = A[root].sum;
		sum += curSum % 142857;
		sum %= 142857;
		vector<int> &neighbors = A[root].neighbors;
		for (int i = 0; i < neighbors.size(); i++) {
			A[neighbors[i]].sum += curSum;
			A[neighbors[i]].sum %= 142857;
			A[neighbors[i]].degree--;
			if (A[neighbors[i]].degree == 0)
				queue.push(neighbors[i]);
		}
	} while (!queue.empty());

	return sum;
}

int main() {
	int N = 0, M = 0, K = 0;
	cin >> N >> M >> K;
	vector<Vertex> A = vector<Vertex>(N);
	for (int i = 0; i < K; i++) {
		int a = 0;
		cin >> a;
		A[a - 1].sum++;
	}
	for (int i = 0; i < M; i++) {
		int a = 0, b = 0;
		cin >> a >> b;
		A[a - 1].neighbors.push_back(b - 1);
		A[b - 1].degree++;
	}

	cout << calSum(A);

	return 0;
}

Author：Who Watson

Link：https://wangshenghu.github.io/2016/05/10/2016-05-10-hihocoder-topology-sort/

Publish date：May 10th 2016, 5:45:11 pm

Update date：December 4th 2022, 5:04:50 pm

License：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 题目
  2. 2. 解题思路
  3. 3. 时间复杂度
  4. 4. 代码
Total : 56
2022
2016
test
笔记 算法 hihoCoder 实习经历 项目