Cod sursa(job #2018291)

Utilizator GeoeyMexicanuBadita George GeoeyMexicanu Data 4 septembrie 2017 13:14:19
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>
#define N 1000010

using namespace std;

ifstream f("darb.in");
ofstream g("darb.out");

vector<int> nod[N];
queue<int> q;
int n, cnt[N],viz[N],last,diametru,i;
void bfs(int plec)
{
    memset(cnt,0,N);
    memset(viz,0,N);
    q.push(plec);
    cnt[plec]=1;
    viz[plec]=1;
    int i,el;
    while(!q.empty())
    {
        el=q.front();
        for(i=0;i<nod[el].size();i++)
            if(viz[nod[el][i]]==0)
            {
                q.push(nod[el][i]);
                viz[nod[el][i]]=1;
                cnt[nod[el][i]]=cnt[el]+1;
                diametru=cnt[nod[el][i]];
                last=nod[el][i];
            }
        q.pop();
    }
}
int main()
{
    int a,b;
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>a>>b;
        nod[a].push_back(b);
        nod[b].push_back(a);
    }
    bfs(1);
    bfs(last);
    g<<diametru;
    return 0;
}