Cod sursa(job #2648334)

Utilizator pregoliStana Andrei pregoli Data 10 septembrie 2020 12:12:44
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <bits/stdc++.h>
#define newline '\n'
#define STOP fin.close(); fout.close(); return 0;
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
///***********************
const int NMAX = 1e5 + 3;
int n, ans, ansNode;
vector<int> graph[NMAX];

void read() {
    fin >> n;
    for (int a, b, i = 1; i <= n; i++) {
        fin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
}

struct Node{
    int node, dis, daddy;
};
void bfs(int start) {
    queue<Node> q;
    q.push({start, 1, 0});
    while (!q.empty()) {
        int node = q.front().node;
        int dis = q.front().dis;
        int daddy = q.front().daddy;
        q.pop();
        if (ans < dis) {
            ans = dis;
            ansNode = node;
        }
        for (auto it : graph[node]) {
            if (it == daddy)
                continue;
            q.push({it, dis + 1, node});
        }
    }
}

int main() {
    read();
    bfs(1);
    bfs(ansNode);
    fout << ans << newline;
    STOP
}