Cod sursa(job #2619460)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 27 mai 2020 18:59:43
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>
#define nmax 100001

using namespace std;

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

int n, x, y, D, last, dist[nmax];
bool viz[nmax];
vector < int > G[nmax];
queue < int > Q;

void Read () {
    fin >> n;
    for (int i = 1; i < n; i ++) {
        fin >> x >> y;
        G[x].emplace_back (y);
        G[y].emplace_back (x);
    }
}

void BFS (int start) {
    Q.push (start);
    dist[start] = 1, viz[start] = 1;
    while (!Q.empty()) {
        int x = Q.front();
        Q.pop();
        for (int i = 0; i < G[x].size(); i ++)
        if (!viz[G[x][i]]) {
            Q.push (G[x][i]);
            dist[G[x][i]] = dist[x] + 1;
            viz[G[x][i]] = 1;
            D = dist[G[x][i]];
            last = G[x][i];
        }
    }
}

int main() {
    ios_base::sync_with_stdio (false);
    fout.tie (0);
    Read ();
    BFS (1);
    memset (dist, 0, sizeof(dist));
    memset (viz, 0, sizeof(viz));
    BFS (last);
    fout << D;
    fout.close();
    return 0;
}