Cod sursa(job #1970610)

Utilizator TimoteiCopaciu Timotei Timotei Data 19 aprilie 2017 14:44:21
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cmath>
#define FOR(i, x, y) for(int i = x; i <= y; ++i)
#define FORR(i, x, y) for(int i = x; i >= y; --i)
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
#define sz() size()
#define nMax 100005

using namespace std;
bool ap[nMax];
int dp[nMax], T[nMax];
queue <int> C;
vector <int> v[nMax];
int main()
{
    ifstream fin("darb.in");
    ofstream fout("darb.out");
    int n, x, y, ans = 0;
    fin >> n;
    FOR(i, 1, n - 1){
      fin >> x >> y;
      T[y] = x;
      v[x].pb(y);
      ap[x] = 1;
    }
    FOR(i, 1, n)
      if(!ap[i]) C.push(i), dp[i] = 1, ap[i] = 1;
        else ap[i] = 0;
    while(!C.empty()){
       x = C.front();
       y = T[x];
       C.pop();
       if(!ap[y]) C.push(y), ap[y] = 1;
       dp[y] = max(dp[y], dp[x] + 1);
       ap[x] = 0;
    }
    int mx1, mx2;
    FOR(i, 1, n)
      if(v[i].sz() > 0){
        mx1 = mx2 = 0;
        FOR(j, 0, v[i].sz() - 1){
          x = v[i][j];
          if(dp[x] >= mx1) mx2 = mx1, mx1 = dp[x];
            else if(dp[x] > mx2) mx2 = dp[x];
        }
        ans = max(ans, mx1 + mx2);
      }

    fout << ans + 1;
    return 0;
}