多久没写东西了啊。。。。
两道拓扑排序Liv.1的题。。。。方法是一样的~~
《拓扑排序·二》
题目：http://hihocoder.com/contest/hiho81/problem/1
一个电脑网路，单向边，如果存在边u->v，那么u的病毒会感染到v。
要点，不存在环！那么如果u的入度=0的话，那么u中的病毒数不会再变化。
想到拓扑排序。不断删去入度为0的点。每次删去节点u，如果存在u->v，那么病毒数
num[v] += num[u]。问题解决。
（用queue实现拓扑排序很方便~~）
代码：
1 #include<bits/stdc++.h>
2
3 using namespace std;
4 const int maxn = 100000 + 10;
5 const int mod = 142857;
6 int n, m, k;
7 int num[maxn], in[maxn];
8 vector<int> G[maxn];
9
10 int solve(){
11 queue<int> q;
12
13 int ans = 0;
14 for( int i = 1; i <= n; ++i ){
15 if(!in[i]){
16 //cout << "i: " << i << endl;
17 q.push(i);
18 }
19 }
20
21 while(!q.empty()){
22 int u = q.front(); q.pop();
23 ans = ( ans + num[u] )%mod;
24
25 for( int i = 0; i < G[u].size(); ++i ){
26 int v = G[u][i];
27 in[v]--; num[v] = (num[u] + num[v])%mod;
28 if(!in[v])
29 q.push(v);
30 }
31 }
32
33 return ans;
34 }
35
36 int main(){
37 scanf("%d%d%d", &n, &m, &k);
38
39 memset( num, 0, sizeof(num) );
40 int u, v;
41 for( int i = 0; i < k; ++i ){
42 scanf("%d", &u);
43 num[u]++;
44 }
45
46 memset( in, 0, sizeof(in) );
47 for( int i = 0; i < m; ++i ){
48 scanf("%d%d", &u, &v);
49 G[u].push_back(v); in[v]++;
50 }
51
52 int ans = solve();
53 printf("%d
", ans);
54
55 return 0;
56 }
《hiho一下 第八十一周》
题目：http://hihocoder.com/contest/hiho81/problem/1
方法相同，建图稍微难点。。。
代码：
1 #include<bits/stdc++.h>
2
3 using namespace std;
4 const int maxn = 100000 + 10;
5 const int mod = 142857;
6 int n, m;
7 vector<int> in[maxn];
8 int s[maxn], ru[maxn], num[maxn];
9 vector<int> e[maxn], G[maxn];
10
11 void init(){
12 for( int i = 0; i < maxn; ++i )
13 in[i].clear(), e[i].clear(), G[i].clear();
14 memset( s, 0, sizeof(s) );
15 memset( ru, 0, sizeof(ru) );
16 memset( num, 0, sizeof(num) );
17 }
18
19 void solve(){
20 queue<int> q;
21 for( int i = 0; i <= n; ++i ){
22 if(!ru[i])
23 q.push(i);
24 }
25
26 while(!q.empty()){
27 int u = q.front(); q.pop();
28 for( int i = 0; i < G[u].size(); ++i ){
29 int v = G[u][i];
30 ru[v]--, num[v] = (num[v] + num[u])%mod;
31 if(!ru[v])
32 q.push(v);
33 }
34 }
35 }
36
37 void print(){
38 printf("%d", num[1]);
39 for( int i = 2; i <= n; ++i ){
40 printf(" %d", num[i]);
41 }
42 printf("
");
43 }
44
45 int main(){
46 //freopen("1.in", "r", stdin);
47 int T;
48 scanf("%d", &T);
49
50 while(T--){
51 init();
52 scanf("%d%d", &n, &m);
53
54 int u, v, k;
55 s[0] = -1, num[0] = 1;
56 for( int i = 0; i < m; ++i ){
57 scanf("%d", &u);
58 e[0].push_back(u);
59 }
60
61 for( int i = 1; i <= n; ++i ){
62 scanf("%d%d", &u, &k);
63 s[i] = u; in[u].push_back(i);
64 for( int j = 0; j < k; ++j ){
65 scanf("%d", &u);
66 e[i].push_back(u);
67 }
68 }
69
70 //build graph
71 for( int i = 0; i <= n; ++i ){
72 for( int j = 0; j < e[i].size(); ++j ){
73 int sg = e[i][j];
74 for( int p = 0; p < in[sg].size(); ++p ){
75 int v = in[sg][p]; ru[v]++;
76 G[i].push_back(v);
77 }