代码拉取完成,页面将自动刷新
/**
* @file 1076.cpp
* @author Shuang Hu <hsmath@ubuntu>
* @date Wed Apr 28 23:23:03 2021
*
* @brief PAT advanced 1076,Forwards in Weibo
*
*
*/
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>
using namespace std;
class Weibo{
private:
vector<vector<int>> network;//The Network
int L;//Maximum weight
int nodenum;//# of users
vector<bool> istraversed;//traverse or not!
vector<int> height;//mark the height of each nodes
public:
Weibo(int num,int L);
void BFS(int id);//BFS from the index id
};
Weibo::Weibo(int num,int L){
this->L=L;
nodenum=num;
network.resize(nodenum);
for(int i=0;i<nodenum;i++){
int N;
cin>>N;
for(int j=0;j<N;j++){
int id;
cin>>id;
id--;//From Zero
network[id].push_back(i);
}
istraversed.push_back(false);
height.push_back(0);//Initial Height:Zero!
}
}
void Weibo::BFS(int id){//Broad-First Search
int num=0;
queue<int> q;
int tmp=id;
q.push(id);
istraversed[id]=true;
while(q.empty()==false){
tmp=q.front();
q.pop();
for(int i=0;i<network[tmp].size();i++){
if(istraversed[network[tmp][i]]==false){
q.push(network[tmp][i]);
height[network[tmp][i]]=height[tmp]+1;
istraversed[network[tmp][i]]=true;
}
}
}
for(int i=0;i<nodenum;i++){
if(height[i]>=1&&height[i]<=L){
num++;
}
}
for(int i=0;i<nodenum;i++){
height[i]=0;
istraversed[i]=false;
}
cout<<num<<endl;
}
int main(){
int users,L;
cin>>users>>L;
Weibo W(users,L);
cin>>users;
for(int i=0;i<users;i++){
int id;
cin>>id;
id--;
W.BFS(id);
}
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。