【PAT】A1076 Forwards on Weibo (30分)（图的遍历bfs）

1076 Forwards on Weibo (30分)

#include<iostream>
#include<queue>
using namespace std;const int maxn = 1010;int Graph[maxn][maxn] = {
    0};
int n, l; //邻接矩阵版本 
struct Node{
    int id;int depth;Node(int _id, int _depth):id(_id),depth(_depth){
    }
};int bfs(int u)
{
    int numPerson = 0;queue<Node> q;bool vis[maxn] = {
    false};struct Node node(u, 0);q.push(node);vis[u] = true;while(!q.empty()){
    struct Node temp = q.front();q.pop();if(temp.depth >= l)continue;for(int i=1;i<=n;i++){
    if(!vis[i] && Graph[temp.id][i] != 0){
    vis[i] = true;numPerson++;struct Node node(i, temp.depth+1);q.push(node);}}}return numPerson;
}int main()
{
    std::ios::sync_with_stdio(false);cin>>n>>l;int counts, temp;for(int i=1;i<=n;i++){
    cin>>counts;for(int j=0;j<counts;j++){
    cin>>temp;Graph[temp][i] = 1;}}cin>>counts;int query;for(int i=0;i<counts;i++){
    cin>>query;cout<<bfs(query)<<endl;}return 0;
}

法二：邻接表法

#include<iostream>
#include<queue>
using namespace std;const int maxn = 1010;//邻接表版本 
struct Node{
    int id;int depth;Node(int _id, int _depth):id(_id),depth(_depth){
    }
};vector<int> adj[maxn];//邻接表 
int n, l; int bfs(int u)
{
    int numPerson = 0;queue<Node> q;bool vis[maxn] = {
    false};struct Node node(u, 0);q.push(node);vis[u] = true;while(!q.empty()){
    struct Node temp = q.front();q.pop();if(temp.depth >= l)continue;for(int i=0;i<adj[temp.id].size();i++){
    if(!vis[adj[temp.id][i]]){
    vis[adj[temp.id][i]] = true;numPerson++;struct Node node(adj[temp.id][i], temp.depth+1);q.push(node);}}}return numPerson;
}int main()
{
    std::ios::sync_with_stdio(false);cin>>n>>l;int counts, temp;for(int i=1;i<=n;i++){
    cin>>counts;for(int j=0;j<counts;j++){
    cin>>temp;adj[temp].push_back(i);}}cin>>counts;int query;for(int i=0;i<counts;i++){
    cin>>query;cout<<bfs(query)<<endl;}return 0;
}