Cod sursa(job #2813626)

Utilizator MadalinaKopaczMadalina Kopacz MadalinaKopacz Data 7 decembrie 2021 00:06:39
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.53 kb
#include <bits/stdc++.h>
using namespace std;

void Citire(vector<vector<int>> &lisAdiacenta)
{
    ifstream fin("darb.in");
    int N;
    fin >> N;

    lisAdiacenta.resize(N+1);
    for(int i = 0; i <= N; ++i){
        lisAdiacenta[i].push_back(-1);
    }

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

void BFS_final(vector<vector<int>> lisAdiacenta, const int start, int &ultim, int &distanta)
{
    vector<bool> viz(lisAdiacenta.size()+1, 0);
    queue<int> coada;

    vector<int> dist(lisAdiacenta.size()+1, 0);
    coada.push(start); viz[start] = 1;
    dist[start] = 1;
    distanta = 0;
    while(!coada.empty()) {
        int x = coada.front();
        coada.pop();
        for(int i = 1; i < lisAdiacenta[x].size(); ++i) {
                if(!viz[lisAdiacenta[x][i]]) {
                    dist[lisAdiacenta[x][i]] = dist[x] + 1;
                    viz[lisAdiacenta[x][i]] = 1;
                    coada.push(lisAdiacenta[x][i]);
                }
        }
    }
    for (int i = 1; i <= lisAdiacenta.size(); ++i) {
        if(dist[i] > distanta){
            distanta = dist[i];
            ultim = i;
        }
    }
}

int main()
{
    vector<vector<int>> lisAdiacenta;
    Citire(lisAdiacenta);

    int u1, u2, distanta;
    BFS_final(lisAdiacenta, 1, u1, distanta);

    BFS_final(lisAdiacenta, u1, u2, distanta);

    ofstream fout("darb.out");
    fout << distanta;
    return 0;
}