1.题目
https://pintia.cn/problem-sets/994805342720868352/problems/994805392092020736
微博转发背景，给出N个用户的关注情况（关注的人有哪些）和转发层数上限L，用最初发布消息的用户编号进行查询，求在转发层数上限内消息最多会转发的用户数。
2.思路
同一层可以有多个粉丝进行转发，所以显然用BFS合适。
基础题。不过写的时候出现了是三个傻逼BUG，实在该打！
（1）在输入点的坐标的for循环时候忘记结点的编号是1~N，而不是0，所以不能习惯地对for循环里面的i从0开始遍历；
（2）由于我一开始搞的crossnum是个全局变量，每次查询后不要忘记对其进行清零，或者就定义再BFS里面也行（然后搞个返回值额）就不需要清零了；
（3）注意逻辑要清晰，Node start=Node(i,0)一开始Node的第一个参数写成了a了，导致错误。
题目给出的是当前i结点的关注的人a，不要对下标写反了，应该是adj[a].push_back(start)。
另外
（1）为了减少代码行数，可以在结构体内使用构造函数，而初始化可以用Node start=Node(i,0)。
结构体内构造函数的三种方法。
（2）memset的头文件是<string.h>，而不是头文件< string>。
最好不用DFS：
（1）由于可能成环，因此必须控制每个用户只能转发消息一次（即遍历时只能访问一次）；
（2）用DFS易出错，因有一种情况：一个用户X在第i次被访问，但此时已经达到转发层数上限（故无法继续遍历）， 但用户可以通过另一条路径更快访问到（如下图：1到5有2条路径，转发上限为L=3，即有一条路径合法）。
DFS还可能导致同一个结点的转发次数被重复计算，需额外设置一个数组记录结点是否已经转发过消息。
3.完整代码
#include<iostream> #include<stdio.h> #include<stdlib.h> #include<vector> #include<queue> #include<string.h>//memset的头文件 using namespace std; const int N=1010; int maxxx;//最大传播层数阈值 int crossnum=0; //邻接表存储 struct Node{ int v; int layer; Node(int a,int b):v(a),layer(b){ }//构造函数 Node(int a){ v=a; } }; vector<Node>adj[N]; bool inq[N]={false}; int BFS(int index){ queue<Node>q; Node start=Node(index,0); q.push(start); inq[start.v]=true; while(!q.empty()){ Node topNode=q.front(); q.pop(); int u=topNode.v; for(int i=0;i<adj[u].size();i++){ Node next=adj[u][i]; next.layer=topNode.layer+1; if(inq[next.v]==false&& ((next.layer)<=maxxx)){ q.push(next); inq[next.v]=true; crossnum++; } } } return crossnum; } int main(){ int vnum; scanf("%d%d",&vnum,&maxxx); //输入阶段(存储图) for(int i=1;i<=vnum;i++){//注意结点编号从1开始，所以i非0开始 int n1; scanf("%d",&n1);//i号用户关注的人数 for(int j=0;j<n1;j++){ int a; scanf("%d",&a);//i号用户关注的人的编号 Node start=Node(i,0);//一开始Node的第一个参数写成了a了，导致错误 adj[a].push_back(start); } } //最后一行(查询步骤) int qnum; scanf("%d",&qnum); for(int i=0;i<qnum;i++){ memset(inq,false,sizeof(inq)); crossnum=0;//每次输出之后需要清零 int startnode; scanf("%d",&startnode); BFS(startnode); printf("%d\n",crossnum); //crossnum=0;//每次输出之后需要清零 } system("pause"); }
