Cod sursa(job #1249774)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 27 octombrie 2014 14:02:11
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <vector>

#define Nmax 100100
#define Neighbour Graph[Node][i]

using namespace std;

vector <int> Graph[Nmax];
int N, Solution, Distance[Nmax];
bool used[Nmax];

void Dfs(int Node) {

    int i, theChosenOne = 0, theSecondChosenOne = 0;

    used[Node] = true;

    if(Graph[Node].size() == 0) {
        Distance[Node] = 1;
        return;
        }
    else
    for(i = 0; i < Graph[Node].size(); i++)
        if(!used[Neighbour]) {

            Dfs(Neighbour);

            if(Distance[Neighbour] > theChosenOne)
                theSecondChosenOne = theChosenOne,
                theChosenOne = Distance[Neighbour];
            else if(Distance[Neighbour] > theSecondChosenOne)
                theSecondChosenOne = Distance[Neighbour];

            }

    if(theChosenOne + theSecondChosenOne + 1 > Solution)
        Solution = theChosenOne + theSecondChosenOne + 1;

    Distance[Node] = theChosenOne + 1;

}
void Read() {

    int i, x, y;

    ifstream in("darb.in");
    in >> N;

    for(i = 1; i < N; i++) {
        in >> x >> y;
        Graph[x].push_back(y);
        Graph[y].push_back(x);
        }

    in.close();

}
void Write() {

    ofstream out("darb.out");
    out << Solution << '\n';
    out.close();

}
int main() {

    Read();
    Dfs(1);
    Write();

    return 0;
}