BFS，题意比较难懂，是求离query L层的总共人数
|
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114 |
#include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>#include <map>#include <vector>#include <queue>using
namespace std;const
int N = 1005;struct
E{ int
node;};vector<E> v[N];int
mark[N];void
add_edge(int
a, int
b){ E tmp; tmp.node = b; v[a].push_back(tmp);}struct
ANS{ int
num; int
lev;};void
BFS(int
x, int
ll){ queue<ANS> q; ANS tmp; tmp.lev = 0; tmp.num = x; q.push(tmp); mark[x] = 1; int
level = 0; int
ans = 0; while
(!q.empty()) { ANS top = q.front(); int
node = top.num; int
lev = top.lev; if
(lev >= ll) break; q.pop(); for
(int
i = 0; i < v[node].size(); i++) { if
(mark[v[node][i].node] == 0) { mark[v[node][i].node] = 1; tmp.lev = lev + 1; tmp.num = v[node][i].node; //printf("%d %d\n", tmp.num, tmp.lev); ans++; q.push(tmp); } } } printf("%d\n", ans);} int
main(){ int
n, ll; while
(scanf("%d%d", &n, &ll) != EOF) { for
(int
i = 1; i <= n; i++) { int
k, a; scanf("%d", &k); while
(k--) { scanf("%d", &a); add_edge(a, i); } } int
query_num, query; scanf("%d", &query_num); while
(query_num--) { scanf("%d", &query); memset(mark, 0, sizeof(mark)); BFS(query, ll); } } return
0;} |
Forwards on Weibo (30),布布扣,bubuko.com
原文：http://www.cnblogs.com/echobfy/p/3576803.html