Cod sursa(job #2198384)

Utilizator GabrielScinteieScinteie Alexandru Gabriel GabrielScinteie Data 24 aprilie 2018 13:19:18
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <fstream>
#include <vector>
#include <queue>


using namespace std;

ifstream fin("darb.in");
ofstream fout("darb.out");

vector <int> LAD[100005];//Lista de adiacenta
queue <int> q;

int n, ultim, dist[100005], diametru;
bool viz[100005];

void citire();
void bfs(int start);
void afisare();

int main()
{
    citire();
    bfs(1);
    bfs(ultim);
    fout << diametru << '\n';

    return 0;
}

void citire()
{
    int i, x, y;
    fin >> n;
    for (i = 1; i < n; i++)
    {
        fin >> x >> y;
        LAD[x].push_back(y);
        LAD[y].push_back(x);
    }
}

void bfs(int start)
{
    int nod, i;

    q.push(start);
    dist[start] = 1;

    if(start==1)
    {
        while (!q.empty())
        {
            nod = q.front();
            q.pop();
            for (i = 0; i < LAD[nod].size(); i++)
                if (!viz[LAD[nod][i]])
                {
                    q.push(LAD[nod][i]);
                    viz[LAD[nod][i]] = 1;
                    dist[LAD[nod][i]] = dist[nod] + 1;
                    diametru = dist[LAD[nod][i]];
                }
        }
        ultim = nod;
    }
    else
        while (!q.empty())
        {
            nod = q.front();
            q.pop();
            for (i = 0; i < LAD[nod].size(); i++)
                if (viz[LAD[nod][i]])
                {
                    q.push(LAD[nod][i]);
                    viz[LAD[nod][i]] = 0;
                    dist[LAD[nod][i]] = dist[nod] + 1;
                    diametru = dist[LAD[nod][i]];
                }
        }
    ultim = nod;
}