Cod sursa(job #2424750)

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

using namespace std;

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

int farthestNode, maxDist;

void dfs1(int parent, int node, int dist) {
    if (dist > maxDist) {
        maxDist = dist;
        farthestNode = node;
    }

    for (auto nextNode: V[node]) {
        if (parent != nextNode) dfs1(node, nextNode, dist + 1);
    }
}

int dfs(int parent, int node) {
    for (auto nextNode: V[node]) {
        if (nextNode != parent) return 1 + dfs(node, nextNode); 
    }

    return 1;
}

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);
    }

    dfs1(0,1,1);

    fout << dfs(0,farthestNode);



    return 0;
}