Cod sursa(job #2126178)

Utilizator Y0da1NUME JMECHER Y0da1 Data 9 februarie 2018 12:20:51
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

const int maxn = 100005;

using namespace std;

int N;
int vizitat[maxn];
int maxim = 1;
int poz_max;
vector <int> G [maxn];
queue <pair <int, int> > Q;

void clear_coada()
{
    while(!Q.empty())
        Q.pop();
}

void BEFEU(int x)
{
    clear_coada();
    for(int i = 1; i <= N; ++i)
        vizitat[i] = 0;
    vizitat[x] = 1;
    Q.push(make_pair(x, maxim));
    while (!Q.empty())
    {
        pair<int, int> cur = Q.front();
        Q.pop();
        for (int i = 0; i < G[cur.first].size(); ++i)
            if(!vizitat[G[cur.first][i]])
            {
                vizitat[G[cur.first][i]] = 1;
                Q.push(make_pair(G[cur.first][i], cur.second + 1));
                //cout<<"PUN IN COADA NODUL "<<G[cur.first][i]<<" cu distanta "<<cur.second + 1<<"\n";
                if(cur.second + 1 >= maxim)
                {
                    maxim = cur.second + 1;
                    poz_max = G[cur.first][i];
                }
            }
    }

}

int main()
{
    ifstream in ("darb.in");
    ofstream out ("darb.out");
    int x, y;
    in>>N;
    for (int i = 0; i < N; ++i)
    {
        in>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    //cout<<"BEFEU 1\n";
    BEFEU(1);
    maxim = 1;
    //cout<<"\n\nBEFEU2\n";
    BEFEU(poz_max);
    out<<maxim;

    return 0;

}