Fork me on GitHub

PAT(甲级)渡劫(十一)-Forwards on Weibo(30)


PAT(甲级)渡劫(十一)-Forwards on Weibo(30)

题目大意:

给出每个用户id关注的人,和转发最多的层数L,求一个id发了条微博最多会有多少个人转发,
每个人只考虑转发一次。
用BFS,同时每个节点要记录下所在的层数,由于只能转发一次,所以每个节点要用vis判断之前是否入过队列,不能重复入队。

代码如下:

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
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

vector<int> v[1024];
int n,L,q,idx;

int BFS(int r){
queue<int> q;
q.push(r);
int len = 1,level = 0,result = 0,visit[1024] = {};
visit[r] = 1; // 初始化起点
while(len > 0){
int nextLen = 0;
for(int i = 0 ; i < len ; i++){
int x = q.front();
q.pop();
for(int i = 0 ; i < v[x].size() ; i++){
if(visit[v[x][i]] == 0){
q.push(v[x][i]);
visit[v[x][i]] = 1;
nextLen++; // 记录队列的长度
result++;
}
}
}
len = nextLen;
++level;
if(level >= L) break;
}
return result;
}

int main(){
//freopen("in.txt","r",stdin);
scanf("%d %d",&n,&L);
for(int i = 1 ; i <= n ; i++){
int k;
scanf("%d",&k);
while(k--){
scanf("%d",&idx);
v[idx].push_back(i); // i关注了k个用户,则k个用户可以”指向他“,用于转发文章
}
}
scanf("%d",&q);
while(q--){
scanf("%d",&idx);
printf("%d\n",BFS(idx));
}
return 0;
}

运行结果:

坚持原创技术分享,您的支持将鼓励我继续创作
-------------本文结束感谢您的阅读-------------
0%