頂点が \(1,2,\ldots,N\) 、辺が \((u _ i,v _ i) _ {i=1,2,\ldots,M}\) であるようなグラフに対して、頂点 \(u\) から頂点 \(v\) への最短距離を \(d(u,v)\) とします。

この問題で求めるものは、\(\displaystyle\max _ {1\le v\le N}d(u,v)\le K _ j\) となるような \(u\) の個数です。

頂点 \(u\) をひとつ固定したとき、すべての \(v\) に対する \(d(u,v)\) を BFS などを用いて \(O(N+M)\) 時間で求めることができます。 これをすべての頂点 \(u\) に対して繰り返すことで \(O(N(N+M))\) 時間で各頂点 \(u\) に対する \(\displaystyle\max _ {1\le v\le N}d(u,v)\) を求めることができます。

あとは、これを使ってクエリに答えればよいです。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int main() {
    int N, M, Q;
    cin >> N >> M >> Q;
    vector<vector<int>> edges(N);
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        edges[u - 1].emplace_back(v - 1);
    }

    // 頂点 u ごとに d(u, v) の最大値を求める
    vector<int> max_distance(N);
    for (int i = 0; i < N; ++i) {
        // BFS ですべての頂点 v について d(u, v) を求める
        vector distance(N, N + 1);
        queue<int> q;
        q.emplace(i);
        distance[i] = 0;
        while (!empty(q)) {
            int u = q.front();
            q.pop();
            int d = distance[u];
            for (int v : edges[u]) {
                if (distance[v] > d + 1) {
                    q.emplace(v);
                    distance[v] = d + 1;
                }
            }
        }
        // 最大値を求める
        max_distance[i] = ranges::max(distance);
    }

    // ソートして
    ranges::sort(max_distance);

    for (int i = 0; i < Q; ++i) {
        int K;
        cin >> K;
        // 二分探索
        cout << ranges::upper_bound(max_distance, K) - begin(max_distance) << endl;
    }
    return 0;
}

from collections import deque


N, M, Q = map(int, input().split())

edges = [[] for i in range(N)]
for i in range(M):
    u, v = map(int, input().split())
    edges[u - 1].append(v - 1)

# d(u, v) の最大値が k と等しい u がいくつあるか求める
max_distance_count = [0 for i in range(N + 2)]
for i in range(N):
    # BFS ですべての頂点 v について d(u, v) を求める
    distance = [N + 1 for i in range(N)]
    q = deque()
    q.append(i)
    distance[i] = 0
    while len(q) > 0:
        u = q.popleft()
        d = distance[u]
        for v in edges[u]:
            if distance[v] > d + 1:
                q.append(v)
                distance[v] = d + 1
    # 最大値を求める
    max_distance_count[max(distance)] += 1

# 累積和を求める
for i in range(N + 1):
    max_distance_count[i + 1] += max_distance_count[i]

for i in range(Q):
    print(max_distance_count[int(input())])