Pagini recente » Cod sursa (job #1553760) | Cod sursa (job #1832828) | Cod sursa (job #2418285) | Cod sursa (job #2922881) | Cod sursa (job #2207260)
#include <iostream>
#include <vector>
#include <fstream>
#include <list>
#include <queue>
#include <algorithm>
using namespace std;
int bfs(vector<pair<int, int> > arbore, int &diam,int nod) {
vector<int> viz(arbore.size() + 1, 0);
vector<int> prev(arbore.size() + 1, -1);
queue<int> q;
//for (pair<int, int> adc : arbore) cout << adc.first << " " << adc.second << endl;
viz[nod] = 1;
q.push(nod);
//cout << q.front();
while (!q.empty()) {
int i = q.front();
//cout << i<<" ";
q.pop();
for (pair<int, int> a : arbore) {
//cout << (a.first == i && !viz[a.second]);
if (a.first == i && !viz[a.second]) {
//cout << "aaa";
prev[a.second] = i;
viz[a.second] = viz[prev[a.second]] + 1;
q.push(a.second);
}else if (a.second == i && !viz[a.first]) {
//cout << "aaa";
prev[a.first] = i;
viz[a.first] = viz[prev[a.first]] + 1;
q.push(a.first);
}
}
}
//for (int a : viz) cout << a;
diam = *max_element(std::begin(viz), std::end(viz));
for (int b = 0; b < viz.size(); b++) {
if (viz[b] == diam) return b;
}
}
int diam(vector<pair<int, int> > arbore) {
int nod1,nod2;
int di = 0;
nod1=bfs(arbore, di,0);
nod2 = bfs(arbore, di, nod1);
return di;
}
int main() {
int n,a,b;
ifstream f("darb.in");
ofstream f1("darb.out");
vector < pair<int, int> > arbore;
f >> n;
while (f >> a >> b) {
arbore.push_back(make_pair(a-1, b-1));
}
f1<<diam(arbore);
f.close();
f1.close();
return 0;
}