Cod sursa(job #1302400)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 26 decembrie 2014 21:01:48
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <vector>
using namespace std;

const int MAX_N = 100002;

int N;
int D[MAX_N];
vector < int > v[MAX_N];
bool vis[MAX_N];

void DFS(int x) {
    vis[x] = 1;

    for(int i = 0; i < (int) v[x].size(); ++i) {
        int y = v[x][i];

        if(vis[y])
            continue;

        D[y] = D[x] + 1;
        DFS(y);

    }
}

int main() {
    ifstream f("darb.in");
    ofstream g("darb.out");

    f >> N;
    for(int i = 1; i < N; ++i) {
        int x, y;

        f >> x >> y;

        v[x].push_back(y);
        v[y].push_back(x);
    }

    D[1] = 1;
    DFS(1);

    int x = 0;
    for(int i = 1; i <= N; ++i)
        if(D[i] > D[x])
            x = i;

    for(int i = 1; i <= N; ++i)
        D[i] = vis[i] = 0;

    D[x] = 1;
    DFS(x);

    int ans = 0;
    for(int i = 1; i <= N; ++i)
        ans = max(ans, D[i]);

    g << ans << "\n";

    f.close();
    g.close();

    return 0;
}