Cod sursa(job #1535233)

Utilizator usermeBogdan Cretu userme Data 24 noiembrie 2015 14:55:56
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

FILE* f = fopen("darb.in", "r");
FILE* h = fopen("darb.out", "w");

int n, distmax, maxnod;

bool fost[100001];

vector<int> v[100001];

void dfs(int x, int dist) {
    if (fost[x]) {
        return;
    }
    fost[x] = true;
    if (dist > distmax) {
        distmax = dist;
        maxnod = x;
    }
    for (int i = 0; i < v[x].size(); ++i) {
        dfs(v[x][i], dist + 1);
    }
}

int main() {
    fscanf(f, "%d", &n);
    for (int i = 1; i < n; ++i) {
        int x, y;
        fscanf(f, "%d %d\n", &x, &y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    distmax = 0;
    maxnod = 1;
    dfs(1,0);
    memset(fost, 0, sizeof(fost));
    distmax = 0;
    dfs(maxnod, 0);
    fprintf(h, "%d\n", distmax + 1);
    return 0;
}