Cod sursa(job #2342972)

Utilizator IrinaBuradaIrina Burada IrinaBurada Data 13 februarie 2019 16:16:32
Problema Diametrul unui arbore Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");

int d[100001];
vector <int >L[100001];
int n;

void Citire()
{
    int x, y;
    fin>>n;
    while(fin>>x>>y)
    {
        L[x].push_back(y);
        L[y].push_back(x);
    }
}

void DFS(int k)
{
    int i;
    for(int i = 0; i < L[k].size(); i ++)
     {
         int j=L[k][i];
            if(d[j] > d[k]+1)
           {
              d[j]=d[k]+1;
              DFS(j);
            }
     }
}

void Init()
{
    for(int i = 1; i <= n; i ++)
        d[i]=1e9;
}

void DetDiametru()
{
    Init();
    d[1]=0;
    DFS(1);
    int p;
    p=1;
    for(int i = 2; i <= n; i ++)
        if(d[i] > d[p]) p=i;

    Init();
    d[p]=0;
    DFS(p);
    p=1;
    for(int i = 2; i <= n; i ++)
        if(d[i] > d[p]) p = i;

    fout<<p;
}
int main()
{
    Citire();
    DetDiametru();

    return 0;
}