Cod sursa(job #1844983)

Utilizator hantoniusStan Antoniu hantonius Data 10 ianuarie 2017 18:27:13
Problema Diametrul unui arbore Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <vector>
#include <queue>
#include <string.h>
#define maxn 100001
using namespace std;

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

vector <int> nod[maxn];
int n, diametru, last;

void read()
{
    int x, y;

    fin >> n;
    for (int i = 0; i < n - 1; i++) {
        fin >> x >> y;
        nod[x].push_back(y);
        nod[y].push_back(x);
    }
}

void deplasare(int poz)
{
    int viz[maxn], contor[maxn], aux;
    queue <int> c;

    memset(viz, 0, maxn);
    memset(contor, 0, maxn);
    viz[poz] = 1;
    contor[poz] = 1;
    c.push(poz);
    while (!c.empty()) {
        aux = c.front();
        c.pop();
        for (int i = 0; i < nod[aux].size(); i++)
            if (viz[nod[aux][i]] == 0) {
                viz[nod[aux][i]] = 1;
                contor[nod[aux][i]] = contor[aux] + 1;
                c.push(nod[aux][i]);
                //partea specifica acestei probleme
                diametru = contor[nod[aux][i]];
                last = nod[aux][i];
            }
    }
}

int main()
{
    read();
    deplasare(1);
    deplasare(last);
    fout << diametru;
    return 0;
}