Cod sursa(job #1379360)

Utilizator oprea1si2si3Oprea Sebastian oprea1si2si3 Data 6 martie 2015 17:33:43
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include<fstream>
#include<vector>
using namespace std;

const int kNMax = 100010;
int n, sol, rad;
bool viz[kNMax];
vector <int> G[kNMax];

void Citire() {
    ifstream in("darb.in");
    int x, y;
    in >> n;
    for (int i = 1; i < n; ++i) {
        in >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    in.close();
}

void Dfs(int nod, int adancime) {
    int vecin;
    viz[nod] = 1;
    if (adancime > sol) {
        sol = adancime;
        rad = nod;
    }
    for (int i = 0; i < G[nod].size(); ++i) {
        vecin = G[nod][i];
        if (!viz[vecin])
            Dfs(vecin, adancime + 1);
    }
}

void Dfs1(int nod, int adancime) {
    int vecin;
    viz[nod] = 0;
    if (adancime > sol)
        sol = adancime;
    for (int i = 0; i < G[nod].size(); ++i) {
        vecin = G[nod][i];
        if (viz[vecin] == 1)
            Dfs1(vecin, adancime+1);
    }
}

void Solve() {
    Dfs(1, 1);
    sol = 0;
    Dfs1(rad, 1);
}

void Afisare() {
    ofstream out("darb.out");
    out << sol << '\n';
    out.close();
}

int main() {
    Citire();
    Solve();
    Afisare();
    return 0;
}