Cod sursa(job #2424758)

Utilizator cyber_ghSoltan Gheorghe cyber_gh Data 23 mai 2019 20:18:42
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100010;
int N;
vector<int> V[MAXN];

int farthestNode, maxDist;
int diameter;

int bfs(int start) {
    int vis[MAXN] = {0}, dp[MAXN] = {0};

    queue<int> Q;
    Q.push(start);
    vis[start] = true;
    dp[start] = 1;
    int last = -1;
    int maxDist = -1;

    while (!Q.empty()) {
        int curr = Q.front();
        Q.pop();
        last = curr;
        for(auto nextNode: V[curr]) {
            if (!vis[nextNode]) {
                vis[nextNode] = true;
                dp[nextNode] = dp[curr] + 1;
                diameter = max(diameter, dp[nextNode]);
                Q.push(nextNode);
            }
        }     
    }

    return last;
}

int main() {
    ifstream fin("darb.in");
    ofstream fout("darb.out");
    fin >> N;
    for (int i = 1; i <= N - 1;i++) {
        int from, to;
        fin >> from >> to;
        V[from].push_back(to);
        V[to].push_back(from);
    }

    bfs(bfs(1));

    fout << diameter;


    return 0;
}