Cod sursa(job #2856444)

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

using namespace std;

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

void outGraf(vector<vector<int> > a)
{
    for(int i=0;i<a.size();i++)
    {
        cout<<i+1<<": ";
        for(int j=0;j<a[i].size();j++)
        {
            cout<<a[i][j]+1<<' ';
        }
        cout<<endl;
    }
}
void outVector(vector <int> a)
{
    for(int i=0;i<a.size();i++)
    {
        cout<<a[i]<<' ';
    }
    cout<<endl;
}
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);
    vector<bool> jart(n,false);
    vector<int> d(n);
    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;
}