注意计算层数的时候不是在pop之后,因为起始点不能算,所以在for里面计算
//邻接矩阵
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int maxv = 1e3 + 10;
struct node {
int v, layer;
};
int G[maxv][maxv];
bool inq[maxv];
int n, l;
int BFS(int v)
{
int ans = 0;
node start;
start.v = v;
start.layer = 0;
queue<node>q;
q.push(start);
inq[start.v] = true;
while (!q.empty())
{
node topNode = q.front();
q.pop();
int u = topNode.v;
for (int i = 1; i <= n; i++)
{
node next;
next.layer = topNode.layer + 1;
if (G[u][i]&&inq[i]==false)
{
next.v = i;
q.push(next);
inq[i] = true;
if (next.layer <= l)ans++;
}
}
}
return ans;
}
int main()
{
scanf("%d%d", &n, &l);
for (int i = 1; i <= n; i++)
{
int m, u;
scanf("%d", &m);
while (m--)
{
scanf("%d", &u);
G[u][i] = 1;
}
}
int k;
scanf("%d", &k);
while (k--)
{
int query;
memset(inq, false, sizeof(inq));
scanf("%d", &query);
int ans=BFS(query);
printf("%d\n", ans);
}
return 0;
}
邻接表写法
int BFS(int v)
{
int ans = 0;
queue<node>q;
node start;
start.v = v;
start.layer = 0;
q.push(start);
inq[start.v] = true;
while (!q.empty())
{
node topNode = q.front();
q.pop();
int u = topNode.v;
for (int i = 0; i < Adj[u].size(); i++)
{
node next;
next.v = Adj[u][i];
next.layer = topNode.layer + 1;
if (!inq[next.v] && next.layer <= l)
{
ans++;
q.push(next);
inq[next.v] = true;
}
}
}
return ans;
}
···