6.Longest path in an undirected tree

Spoj Question

Longest path 5 (node 5 to node 7)

Solution : (Using two BFS)

First BFS to find an endpoint of the longest path and second BFS from this endpoint to find the actual longest path.

#include <bits/stdc++.h>

using namespace std;

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

    while (!q.empty())
    {
        int s = q.size();

        int x = q.front();
        q.pop();

        for (auto itr = v[x].begin(); itr != v[x].end(); itr++)
        {
            if (vs[*itr] == 0)
            {
                vs[*itr] = 1;
                q.push(*itr);
                dist[*itr] = dist[x] + 1;
            }
        }
    }
    return;
}

int main()
{

    int n;
    cin >> n;
    vector<int> v[n + 1];

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

    int max = INT_MIN;
    int idx = -1;
    vector<bool> vs(n + 1);
    vector<int> dist(n + 1);
    bfs(1, v, vs, dist);

    for (int i = 1; i <= n; i++)
    {
        if (dist[i] > max)
        {
            max = dist[i];
            idx = i;
        }
    }

    int temp_max = max;

    vector<bool> vs1(n + 1);
    vector<int> dist1(n + 1);
    bfs(idx, v, vs1, dist1);

    max = INT_MIN;
    idx = -1;

    for (int i = 1; i <= n; i++)
    {
        if (dist1[i] > max)
        {
            max = dist1[i];
            idx = i;
        }
    }

    if (max > temp_max)
    {
        cout << max;
    }
    else
    {
        cout << temp_max;
    }
    return 0;
}