Cod sursa(job #1133743)

Utilizator muresan_bogdanMuresan Bogdan muresan_bogdan Data 5 martie 2014 15:29:21
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;

ifstream fin("darb.in");
ofstream fout("darb.out");

struct nod{
    int pas;
    vector<int> vecini;
};

int n, i, x, y, maxi, s;
nod g[100001];

void dfs(int x) {
    int j;
    for(j = 0; j < g[x].vecini.size(); j++) {
        int vecin = g[x].vecini[j];
        if(g[vecin].pas == 0) {
            g[vecin].pas = g[x].pas + 1;
            if(g[vecin].pas > maxi) maxi = g[vecin].pas, s = vecin;
            dfs(vecin);
            g[vecin].pas = 0;
        }
    }
}

int main() {
    fin >> n;
    for(i = 1; i < n; i++) {
        fin >> x >> y;
        g[x].vecini.push_back(y);
        g[y].vecini.push_back(x);
    }
    g[1].pas = 1;
    dfs(1);
    g[1].pas = 0;
    g[s].pas = 1;
    dfs(s);
    fout << maxi << '\n';
    fin.close();
    fout.close();
    return 0;
}