Cod sursa(job #2856447)

Utilizator kontexVeres Norbert kontex Data 23 februarie 2022 21:24:56
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

ifstream be("darb.in");
ofstream ki("darb.out");
int dmaxi, di, n;

void maxiszamolas(vector <int> a)
{
    dmaxi = 0;
    di = 0;
    for(int i=0;i<n;i++)
    {
        if(a[i]>dmaxi)
        {
            dmaxi = a[i];
            di = i;
        }
    }
}
void breathfirst(int kcs,  vector<vector<int> > graf)
{
    vector<int> ut(n+1);
    vector<bool> jart(n+1,false);
    vector<int> d(n+1);
    kcs--;
    int utolso=0,elso = 0;
    jart[kcs]=true;
    ut[elso]=kcs;

    for(int i=0;i<=n;i++)
        d[i]=0;

    while(elso<=utolso)
    {
        for(int i=0;i<graf[ut[elso]].size();i++)
        {
            if(!jart[graf[ut[elso]][i]])
            {
                ut[++utolso]=graf[ut[elso]][i];
                jart[graf[ut[elso]][i]] = true;
                d[graf[ut[elso]][i]] = d[ut[elso]]+1;
            }
        }
        elso++;
    }
    maxiszamolas(d);
}
int main()
{
    be>>n;
    vector<vector<int> > graf(n);
    int a,b;
    while(be>>a>>b)
    {
      graf[a-1].push_back(b-1);
      graf[b-1].push_back(a-1);
    }
    //outGraf(graf);
    breathfirst(1,graf);
    breathfirst(di+1,graf);
    ki<<dmaxi+1<<endl;
}