Cod sursa(job #1094878)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 29 ianuarie 2014 22:53:05
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <vector>
#define NMax 100010

using namespace std;

int n;
int viz[NMax];
vector <int> G[NMax];
int ans, last, level_last;

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

inline void DFS(const int node, const int level)
{
    if (level > level_last)
    {
        level_last = level;
        last = node;
    }
    viz[node] = true;
    for (vector <int> :: iterator it = G[node].begin(); it!=G[node].end(); ++it)
        if (!viz[*it])
            DFS(*it, level+1);
}

inline void DFS2(const int node, const int level)
{
    ans = max(ans, level);
    viz[node] = false;
    for (vector <int> :: iterator it = G[node].begin(); it != G[node].end(); ++it)
        if (viz[*it])
            DFS2(*it, level+1);
}

void Write()
{
    ofstream g ("darb.out");
    g<<ans<<"\n";
    g.close();
}

int main()
{
    Read();
    DFS(1, 1);
    DFS2(last, 1);
    Write();
    return 0;
}