Cod sursa(job #1996219)

Utilizator DavidLDavid Lauran DavidL Data 30 iunie 2017 16:23:54
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#define MAXN 100001
using namespace std;
ifstream fi("darb.in");
ofstream fo("darb.out");

vector <int> vecin[MAXN];
int D[MAXN],n,a,b;

void bfs(int sursa)
{
    queue <int> Q;
    Q.push(sursa);
    while (!Q.empty())
    {
        int curent=Q.front();
        Q.pop();
        for (int i=0; i<vecin[curent].size(); i++)
            if (D[vecin[curent][i]]==0)
            {
                D[vecin[curent][i]]=D[curent]+1;
                Q.push(vecin[curent][i]);
            }
    }
}

int main()
{
    ///cel mai departat nod de un nod oarecare este un capat al celui
    ///mai lung drum; daca ar exista un nod care nu e capat
    ///la o distanta mai mare de nodul ales, atunci distanta dintre
    ///acel nod si unul dintre capetele drumului cel mai lung ar fi
    ///mai mare decat distanta drumului cel mai lung -> contradictie

    fi>>n;
    for (int i=0; i<n; i++)
    {
        fi>>a>>b;
        vecin[a].push_back(b);
        vecin[b].push_back(a);
    }
    bfs(1);
    int capat=1;
    for (int i=2; i<=n; i++)
        if (D[i]>D[capat])
            capat=i;
    memset(D,0,sizeof(D));
    bfs(capat);
    int maxim=-1;
    for (int i=1; i<=n; i++)
        maxim=max(maxim,D[i]);
    fo<<maxim+1;
    fi.close();
    fo.close();
    return 0;
}