PAT甲级-11076 Forwards on Weibo (30 分)

题目:1076 Forwards on Weibo (30 分)
分析:BFS的使用,若用DFS会漏掉许多情况,比较麻烦。
#include <iostream>
#include<cstring>
#include<vector>
#include<stdio.h>
#include<queue>
#include<math.h>
#include<stack>
#include<algorithm>
#include<map>
#include<set>
#include<iostream>
using namespace std;
#define MAX 999999999
int n,m,k,ds;
struct Node{
    vector<int>user;
    int layer;
};
int visi[10001];
int cnt;
Node node[10001];
void bfs(int root)
{
    queue<int>q;
    q.push(root);
    visi[root] = 1;
    while(!q.empty())
    {
        int fro = q.front();
        for(int i = 0; i < node[fro].user.size(); i++)
            if(!visi[node[fro].user[i]] && node[fro].layer < k){
                node[node[fro].user[i]].layer = node[fro].layer + 1;
                q.push(node[fro].user[i]);
                visi[node[fro].user[i]] = 1;
                cnt ++;
            }
        q.pop();
    }
}
int main()
{
    cin>>n>>k;
    for(int i = 1; i <= n; i++)
    {
        int p;cin>>p;
        for(int j = 1;j <= p ;j++)
        {
            int x;
            cin>>x;
            node[x].user.push_back(i);
        }
    }
    cin>>m;
    for(int i = 0; i < m; i++)
    {
        int x;cin>>x;
        cnt = 0;
        node[x].layer = 0;
        memset(visi, 0 , sizeof(visi));
        bfs(x);
        cout<<cnt<<endl;
    }
    return 0;
}
上一篇:图应用拓扑排序算法python


下一篇:HDU1242,Rescue(BFS)