Cod sursa(job #1372078)

Utilizator alexandru.ghergutAlexandru-Gabriel Ghergut alexandru.ghergut Data 4 martie 2015 11:20:06
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

int BFS(int src, vector<int> adjList[], int N, int &maxDist);

int main()
{
    int N, a, b, i;
    ifstream f("darb.in");
    f >> N;
    vector<int> adjList[N + 1];
    for (i = 1; i < N; i++)
    {
        f >> a >> b;
        adjList[a].push_back(b);
        adjList[b].push_back(a);
    }
    f.close();

    int diameter;
    int chainHead = BFS(a, adjList, N, diameter);
    BFS(chainHead, adjList, N, diameter);

    ofstream g("darb.out");
    g << diameter + 1;
    g.close();
    return 0;
}

int BFS(int src, vector<int> adjList[], int N, int &maxDist)
{
    queue<int> q;
    int d[N + 1], i;
    bool visited[N + 1];

    for (i = 1; i <= N; i++)
    {
        d[i] = 0;
        visited[i] = false;
    }

    int x, lastNode = src;
    visited[src] = true;
    q.push(src);
    while (!q.empty())
    {
        x = q.front(), q.pop();

        for (i = 0; i < adjList[x].size(); i++)
            if (!visited[adjList[x][i]])
        {
            visited[adjList[x][i]] = true;
            d[adjList[x][i]] = d[x] + 1;
            if (d[adjList[x][i]] > d[lastNode])
                lastNode = adjList[x][i];
            q.push(adjList[x][i]);
        }
    }

    maxDist = d[lastNode];
    return lastNode;
}