PAT_A1076#Forwards on Weibo

Source:

Description:

Input Specification:

Output Specification:

Sample Input:

Sample Output:

Keys:

• 图的存储和遍历
• 广度优先搜索（Breadth First Search）
• queue（C++ STL）

Attention:

• 题目给的是关注列表，消息传播时的方向应该是相反的；
• 最后一个测试点的数据量很大，用DFS会爆栈，BFS剪枝才能通过；

Code:

 /*

 Data: 2019-06-20 16:47:58

 Problem: PAT_A1076#Forwards on Weibo

 AC: 15:23

 题目大意：

 在微博上，当一位用户发了一条动态，关注他的人可以查看和转发这条动态；

 现在你需要统计出某条动态最多可以被转发的次数（转发层级不超过L）

 输入：

 第一行给出，人数N<=1e3（编号从1~N），转发层级L<=6

 接下来N行，用户i关注的总人数W[i]及其各个编号

 接下来一行，给出查询次数K，和要查询的各个编号

 输出；

 L层级内可获得的最大转发量

 基本思路：

 层次遍历

 */

 #include<cstdio>

 #include<queue>

 #include<vector>

 #include<algorithm>

 using namespace std;

 const int M=1e3+,INF=1e9;

 int vis[M],layer[M],L,n;

 vector<int> adj[M];

 int BFS(int u)

 {

     fill(vis,vis+M,);

     fill(layer,layer+M,);

     queue<int> q;

     q.push(u);

     vis[u]=;

     int sum=;

     while(!q.empty())

     {

         u = q.front();

         q.pop();

         if(layer[u] > L)

             return sum;

         for(int i=; i<adj[u].size(); i++){

             if(vis[adj[u][i]]==){

                 vis[adj[u][i]]=;

                 q.push(adj[u][i]);

                 layer[adj[u][i]]=layer[u]+;

                 sum++;

             }

         }

     }

     return sum;

 }

 int main()

 {

 #ifdef ONLINE_JUDGE

 #else

     freopen("Test.txt", "r", stdin);

 #endif // ONLINE_JUDGE

     int k,v;

     scanf("%d%d", &n,&L);

     for(int i=; i<=n; i++)

     {

         scanf("%d", &k);

         for(int j=; j<k; j++)

         {

             scanf("%d", &v);

             adj[v].push_back(i);

         }

     }

     scanf("%d", &k);

     while(k--)

     {

         scanf("%d", &v);

         printf("%d\n", BFS(v));

     }

     return ;

 }