Cod sursa(job #2813530)

Utilizator MadalinaKopaczMadalina Kopacz MadalinaKopacz Data 6 decembrie 2021 21:25:40
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.89 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 = 1; 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);
    }
}

//BFS pentru prima parcurgere - returnam ultimul nod din parcurgere
int BFS_final(vector<vector<int>> lisAdiacenta)
{
    vector<bool> viz(lisAdiacenta.size()+1, 0);
    queue<int> coada;
    coada.push(1); viz[1] = 1;
    int ultNod = 1;
    while(!coada.empty()) {
        int x = coada.front();
        coada.pop();
        ultNod = x;
        for(int i = 1; i < lisAdiacenta[x].size(); ++i) {
                if(!viz[lisAdiacenta[x][i]]) {
                    viz[lisAdiacenta[x][i]] = 1;
                    coada.push(lisAdiacenta[x][i]);
                }
        }
    }
    return ultNod;
}

//BFS pentru a doua parcurgere - returnam distanta de la nodul obt cu BFS_final la ultimul din parc 2
int DistantaBFS2(vector<vector<int>> lisAdiacenta, const int S)
{
    vector<bool> viz(lisAdiacenta.size()+1, 0);
    queue<int> coada;
    coada.push(S); viz[S] = 1;
    int ultNod = 1;
    while(!coada.empty()) {
        int x = coada.front();
        coada.pop();
        ultNod = x;
        for(int i = 1; i < lisAdiacenta[x].size(); ++i) {
                if(!viz[lisAdiacenta[x][i]]) {
                    viz[lisAdiacenta[x][i]] = 1;
                    coada.push(lisAdiacenta[x][i]);
                }
        }
    }
    return ultNod;
}

int main()
{
    vector<vector<int>> lisAdiacenta;
    Citire(lisAdiacenta);
    int u1 = BFS_final(lisAdiacenta);
    ofstream fout("darb.out");
    fout << DistantaBFS2(lisAdiacenta, u1);
    return 0;
}