1 Star 0 Fork 0

hsmath/PAT advanced

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
克隆/下载
1076.cpp 1.63 KB
一键复制 编辑 原始数据 按行查看 历史
hsmath 提交于 2021-04-29 00:08 . 1076
/**
* @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);
}
}
Loading...
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
C++
1
https://gitee.com/hsmath/pat-advanced.git
git@gitee.com:hsmath/pat-advanced.git
hsmath
pat-advanced
PAT advanced
master

搜索帮助