Cod sursa(job #1916084)

Utilizator andreea_zahariaAndreea Zaharia andreea_zaharia Data 9 martie 2017 00:21:18
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream fin ("darb.in");
ofstream fout ("darb.out");

const int NMAX = 100010;

vector<int> G[NMAX];
queue<int> Q;

int N;

int viz[NMAX], lvlMax, frunza;
void DFS1 (int nod, int lvl = 1) {
    viz[nod] = 1;
    if (lvl > lvlMax) {
        frunza = nod;
        lvlMax = lvl;
    }
    for (auto &it : G[nod]) {
        if ( !viz[it]) {
            DFS1 (it, lvl + 1);
        }
    }
}

int dist[NMAX];
int DIAMETRU;
void BFS2 (int nod) {
    Q.push (nod);
    dist[nod] = 1;
    while ( !Q.empty ()) {
        int Qf = Q.front ();
        Q.pop ();

        for (auto &it : G[Qf]) {
            if (dist[it] == 0) {
                Q.push (it);
                dist[it] = dist[Qf] + 1;

                if (dist[it] > DIAMETRU) {
                    DIAMETRU = dist[it];
                }
            }
        }
    }
}

int main () {
    fin >> N;
    for (int i = 1; i <= N - 1; i++) {
        int x, y;
        fin >> x >> y;
        G[x].push_back (y);
        G[y].push_back (x);
    }

    DFS1 (1);
    BFS2 (frunza);

    fout << DIAMETRU;
    return 0;
}