Cod sursa(job #2196539)

Utilizator vladcoroian2001Vlad Coroian vladcoroian2001 Data 19 aprilie 2018 18:10:27
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;
ifstream fi("darb.in");
ofstream fo("darb.out");
const int NMAX=1e5+5;
int n,x,y,D[NMAX],rez,dmax,SEEN[NMAX];
vector <int> V[NMAX];
queue <int> Q;
int bfs(int source)
{
    Q.push(source);
    SEEN[source]=1;
    while(!Q.empty())
    {
        x=Q.front();
        Q.pop();
        for(auto y:V[x])
            if(!SEEN[y])
            {
                SEEN[y]=1;
                D[y]=D[x]+1;
                Q.push(y);
            }
    }
    dmax=0;
    for(int i=1;i<=n;i++)
        if(i!=source && D[i]>dmax)
        {
            dmax=D[i];
            rez=i;
        }
}
int main()
{
    fi>>n;
    for(int i=1;i<=n;i++)
    {
        fi>>x>>y;
        V[x].push_back(y);
        V[y].push_back(x);
    }
    bfs(1);
    for(int i=1;i<=n;i++)
        SEEN[i]=0;
    D[rez]=1;
    bfs(rez);
    fo<<D[rez];
    fi.close();
    fo.close();
    return 0;
}