Cod sursa(job #2648014)

Utilizator robeert.77Chirica Robert robeert.77 Data 7 septembrie 2020 23:10:23
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream fin ("darb.in");
ofstream fout ("darb.out");
vector<int> graph[200000], sum(200001, -1);
queue<int> q;
int n, lastNode;

void dfs(int node) {
    q.push(node);
    sum[node] = 1;
    while (!q.empty()) {
        for (vector<int>::iterator it = graph[q.front()].begin(); it != graph[q.front()].end(); it++) {
            if (sum[*it] == -1) {
                sum[*it] = sum[q.front()] + 1;
                q.push(*it);
                lastNode = *it;
            }
        }
        q.pop();
    }
}

int main() {
    fin >> n;
    for (int i = 0; i < n; i++) {
        int dad, children;
        fin >> dad >> children;
        graph[dad].push_back(children);
        graph[children].push_back(dad);
    }

    dfs(1);
    sum.assign(n + 1, -1);
    dfs(lastNode);
    fout << sum[lastNode];

    return 0;
}