思路分析:
因为流向是一定的,所以直接把每个结点的val流动看成最后一个流动的val。
主要还是熟悉一下如何写CLASS。
代码:
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct node
{
vector<int>u;//出边
int val, in_degree;
node() {
val = in_degree = 0;
u.clear();
}
};
class Graph
{
private:
static const int MOD = 142857;
vector<node>a;
int edge_num, node_num;
public:
Graph();
Graph(int node_num);
void addEdge(int s_node, int t_node);
void addNodeVal(int node_index, int val);
int getAns();
};
Graph::Graph() {
this->a.clear();
this->edge_num = this->node_num = 0;
}
Graph::Graph(int node_num) {
a.clear();
a.resize(node_num+5);
this->node_num = node_num ;
this->edge_num = 0;
}
void Graph::addEdge(int s_node, int t_node) {
this->a[s_node].u.push_back(t_node);
this->a[t_node].in_degree++;
this->edge_num++;
}
void Graph::addNodeVal(int node_index, int val) {
this->a[node_index].val = (this->a[node_index].val + val) % MOD;
}
int Graph::getAns() { // 拓扑排序
int ret = 0;
queue<int>q;
for (int i = 1; i <= node_num; i++) {
if (a[i].in_degree == 0) {
q.push(i);
}
}
while (!q.empty()) {
node& now = a[q.front()];
q.pop();
ret = (ret + now.val) % MOD;
for (int i = 0; i < now.u.size(); i++) {
a[now.u[i]].in_degree--;
a[now.u[i]].val = (a[now.u[i]].val + now.val) % MOD;
if (a[now.u[i]].in_degree == 0) {
q.push(now.u[i]);
}
}
}
return ret;
}
int main()
{
int n, m, k;
while (cin >> n >> m >> k) {
Graph g = Graph(n);
while (k--) {
int x;
cin >> x;
g.addNodeVal(x, 1);
}
while (m--) {
int node_s, node_t;
cin >> node_s >> node_t;
g.addEdge(node_s, node_t);
}
cout << g.getAns() << endl;
}
}