【PAT】A1076 Forwards on Weibo (30分)（图的遍历bfs）
1076 Forwards on Weibo (30分)
法一：邻接矩阵法
作者：天勤1998
题目链接
法一：邻接矩阵法
#include
#include
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 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>>l;
int counts, temp;
for(int i=1;i>counts;
for(int j=0;j>temp;
Graph[temp][i] = 1;
}
}
cin>>counts;
int query;
for(int i=0;i>query;
cout<<bfs(query)<<endl;
}
return 0;
}
法二：邻接表法
#include
#include
using namespace std;
const int maxn = 1010;
//邻接表版本
struct Node{
int id;
int depth;
Node(int _id, int _depth):id(_id),depth(_depth){}
};
vector adj[maxn];//邻接表
int n, l;
int bfs(int u)
{
int numPerson = 0;
queue 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>n>>l;
int counts, temp;
for(int i=1;i>counts;
for(int j=0;j>temp;
adj[temp].push_back(i);
}
}
cin>>counts;
int query;
for(int i=0;i>query;
cout<<bfs(query)<<endl;
}
return 0;
}
作者：天勤1998
