# PAT 解题报告 1076. Forwards on Weibo (30)

### 1076. Forwards on Weibo 题目描述：

Weibo is known as the Chinese version of Twitter. One user on Weibo may have many followers, and may follow many other users as well. Hence a social network is formed with followers relations. When a user makes a post on Weibo, all his/her followers can view and forward his/her post, which can then be forwarded again by their followers. Now given a social network, you are supposed to calculate the maximum potential amount of forwards for any specific user, assuming that only L levels of indirect followers are counted.

### 1076. Forwards on Weibo 算法分析：

```#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>

int bfs(int iStart, const std::vector< std::vector<int> >& vecGraph, int N, int L)
{
int iCount = 0;
std::vector<int> vecDistance(N, -1);
std::queue<int>	  q;

q.push(iStart);
vecDistance[iStart] = 0;

while(!q.empty()) {
int iCurrentNode = q.front(); q.pop();
if(vecDistance[iCurrentNode] >= L)
break;
for(auto it = vecGraph[iCurrentNode].begin();
it != vecGraph[iCurrentNode].end(); ++it) {
if(-1 == vecDistance[*it]) {
q.push(*it);
vecDistance[*it] = vecDistance[iCurrentNode] + 1;
++iCount;
}
}
}
return iCount;
}

int main()
{
int N, L;
std::vector<std::vector<int>> vecGraph;

scanf("%d %D", &N, &L);
vecGraph.resize(N);
int iNode;
for(int i = 0; i < N; ++i) {
for(int j = 0; j < iNumForwardLink; ++j) {
scanf("%d", &iNode);
vecGraph[iNode - 1].push_back(i);
}
}
int iNumQuery;
scanf("%d", &iNumQuery);
for(int i = 0; i < iNumQuery; ++i) {
scanf("%d", &iNode);
printf("%d\n", bfs(iNode - 1, vecGraph, N, L));
}
return 0;
}
```

### 1076. Forwards on Weibo 注意点：

Written on March 7, 2014