PTA A_1076 Forwards on Weibo

798236606

传送门：https://pintia.cn/problem-sets/9 ... /994805392092020736

解：
BFS

1. #include <cstdio>
   
2. #include <cstring>
   
3. #include <vector>
   
4. #include <queue>
   
5. #include <utility>
   
6. 
   
7. using namespace std;
   
8. 
   
9. const int maxn = 1010;
   
10. 
    
11. int n, l, k;
    
12. vector<int> adj[maxn];
    
13. int inq[maxn];
    
14. 
    
15. int BFS(int id)
    
16. {
    
17.     memset(inq, 0, sizeof(inq));
    
18.     queue< pair<int, int> > q;
    
19.     int num = -1;
    
20. 
    
21.     q.push(make_pair(id, 0));
    
22.     inq[id] = 1;
    
23. 
    
24.     while (!q.empty())
    
25.     {
    
26.         id = q.front().first;
    
27.         int layer = q.front().second;
    
28. 
    
29.         num++;
    
30.         q.pop();
    
31. 
    
32.         if (layer == l) continue;
    
33. 
    
34.         for (int i = 0; i < adj[id].size(); i++)
    
35.             if (!inq[adj[id][i]] && ++inq[adj[id][i]])
    
36.                 q.push(make_pair(adj[id][i], layer + 1));
    
37.     }
    
38. 
    
39.     return num;
    
40. }
    
41. 
    
42. int main(void)
    
43. {
    
44.     scanf("%d %d", &n, &l);
    
45.     for (int i = 1; i <= n; i++)
    
46.     {
    
47.         int m;
    
48. 
    
49.         scanf("%d", &m);
    
50.         while (m--)
    
51.         {
    
52.             int x;
    
53. 
    
54.             scanf("%d", &x);
    
55.             adj[x].push_back(i);
    
56.         }   
    
57.     }
    
58. 
    
59.     scanf("%d", &k);
    
60.     while (k--)
    
61.     {
    
62.         int id;
    
63. 
    
64.         scanf("%d", &id);
    
65.         printf("%d\n", BFS(id));
    
66.     }
    
67. 
    
68.     return 0;
    
69. }

复制代码