Cod sursa(job #2189183)

Utilizator claudiu.gatinaFMI Claudiu Gatina claudiu.gatina Data 27 martie 2018 20:00:06
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.92 kb
#include <iostream>
#include <fstream>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

class Graf
{
    int n, m;
    vector<int> adjList[100001];

public:
    Graf()
    {
        n = 0;
        m = 0;
    }

    void add(int a, int b)
    {
        ++m;
        adjList[a].push_back(b);
        adjList[b].push_back(a);

    }

    void setN(int N)
    {
        n = N;
    }

    int mDistantaCeaMaiMare(int &start)
    {
     //   cout << start;
        vector<int> v(n, 0);
        vector<int> d(n, 0);
        v[start] = 1;
        d[start] = 1;
        int distantaCeaMaiMare = 1  ;
        int celMaiIndepartatNod = start;
        queue<int> BFS;
        BFS.push(start);
        while(!BFS.empty())
        {
            int nodCurent = BFS.front();
            for(unsigned int i = 0; i < adjList[nodCurent].size(); ++i)
            {
                int nodUrmator = adjList[nodCurent][i];
                if(!v[nodUrmator]) {
                    v[nodUrmator] = 1;
                    BFS.push(nodUrmator);
                    d[nodUrmator] = d[nodCurent] + 1;
                    if(d[nodUrmator] > distantaCeaMaiMare) {
                        distantaCeaMaiMare = d[nodUrmator];
                        celMaiIndepartatNod = nodUrmator;
                    }
                }
            }
            BFS.pop();
        }
        start = celMaiIndepartatNod;
        return distantaCeaMaiMare;
    }

    int diametru()
    {
        int start = 0;
        mDistantaCeaMaiMare(start);
        return mDistantaCeaMaiMare(start);
    }
};

int main()
{
    fstream f("darb.in", ios::in);
    fstream g("darb.out", ios::out);
    int N;
    Graf arb;

    f >> N;
    arb.setN(N);
    for(int i = 0; i < N - 1; ++i)
    {
        int a, b;
        f >> a >> b;
        arb.add(--a, --b);
    }

    g << arb.diametru();
    return 0;
}