Cod sursa(job #2120708)

Utilizator malina2109Malina Diaconescu malina2109 Data 2 februarie 2018 19:49:51
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define L_MAX 1000001
using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");
vector<int> a[L_MAX];
int *ap1,*ap2,n,pct,mx;
void dfs(int x,int *ap)
{
    queue<int> c;
    c.push(x);
    ap[x]=1;
    while(!c.empty())
    {
        int var=c.front();
        c.pop();
        for(int i=0;i<a[var].size();i++)
            if(ap[a[var][i]]==0)
        {
            ap[a[var][i]]=ap[var]+1;
            if(ap[a[var][i]]>mx)
            {
                mx=ap[a[var][i]];
                pct=a[var][i];
            }
            c.push(a[var][i]);
        }
    }
}
int main()
{
    f>>n;
    ap1=new int[n+2];
    ap2=new int[n+2];
    for(int i=1;i<n;i++)
    {
        int x1,x2;
        ap1[i]=ap2[i]=0;
        f>>x1>>x2;
        a[x1].push_back(x2);
        a[x2].push_back(x1);
    }
   ap1[n]=ap2[n]=0;
   dfs(1,ap1);
    mx=0;
dfs(pct,ap2);
    g<<mx;
}