Pagini recente » Cod sursa (job #1786624) | Cod sursa (job #1361740) | Cod sursa (job #2115680) | Cod sursa (job #797617) | Cod sursa (job #2417820)
#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<list>
using namespace std;
void citire(vector<list<unsigned>>& arbore)
{
ifstream f("darb.in");
unsigned n;
f >> n;
arbore.resize(n);
for (unsigned i = 0; i < n - 1; i++)
{
unsigned x, y;
f >> x >> y;
arbore[x - 1].push_back(y);
arbore[y - 1].push_back(x);
}
f.close();
}
unsigned bf(const vector<list<unsigned>>& arbore, const unsigned& start, unsigned& finish)
{
vector<unsigned> tata(arbore.size(), arbore.size() + 1);
vector<bool> viz(arbore.size(), false);
queue<unsigned> coada;
coada.push(start);
viz[start - 1] = true;
while (coada.size() > 0)
{
finish = coada.front();
coada.pop();
for (auto i : arbore[finish - 1])
if (viz[i - 1] == false)
{
coada.push(i);
viz[i - 1] = true;
tata[i - 1] = finish;
}
}
unsigned diametru = 0;
unsigned x = finish;
diametru = 1;
while (x != start)
{
x = tata[x - 1];
diametru++;
}
return diametru;
}
int main()
{
vector<list<unsigned>> arbore;
citire(arbore);
unsigned nod1 = 0;
unsigned nod2 = 0;
bf(arbore, 1, nod1);
unsigned diametru = bf(arbore, nod1, nod2);
ofstream g("darb.out");
g << diametru;
g.close();
}