2.BFS

Similar to Level Order Traversal

Solution

#include <bits/stdc++.h>

using namespace std;
void bfs(int node, vector<int> v[], vector<bool> &vs, vector<int> &dist)
{
    queue<int> q;
    vs[node] = 1;
    q.push(node);
    dist[node] = 1;

    while (!q.empty())
    {
        int x = q.front();
        int d = dist[x];
        q.pop();
        for (auto itr = v[x].begin(); itr != v[x].end(); itr++)
        {
            if (vs[*itr] == 0)
            {
                q.push(*itr);
                dist[*itr] = d + 1;
                vs[*itr] = 1;
            }
        }
    }
}

int main()
{
    int n;
    cin >> n;
    vector<int> v[n + 1];
    vector<bool> vs(n + 1);
    vector<int> dist(n + 1);

    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    int x;
    cin >> x;

    bfs(1, v, vs, dist);

    int count = 0;
    for (int i = 1; i <= n; i++)
    {
        if (dist[i] == x)
        {
            count++;
        }
    }
    cout << count;
    return 0;
}

Time Complexity: O(V+E)