Pagini recente » Cod sursa (job #195996) | Cod sursa (job #916558) | Cod sursa (job #2313211) | Cod sursa (job #1839901) | Cod sursa (job #2813532)
#include <bits/stdc++.h>
using namespace std;
void Citire(vector<vector<int>> &lisAdiacenta)
{
ifstream fin("darb.in");
int N;
fin >> N;
lisAdiacenta.resize(N+1);
for(int i = 1; i <= N; ++i){
lisAdiacenta[i].push_back(-1);
}
for(int i = 1; i < N; ++i){
int x, y;
fin >> x >> y;
lisAdiacenta[x].push_back(y),lisAdiacenta[y].push_back(x);
}
}
//BFS pentru prima parcurgere - returnam ultimul nod din parcurgere
int BFS_final(vector<vector<int>> lisAdiacenta)
{
vector<bool> viz(lisAdiacenta.size()+1, 0);
queue<int> coada;
coada.push(1); viz[1] = 1;
int ultNod = 1;
while(!coada.empty()) {
int x = coada.front();
coada.pop();
ultNod = x;
for(int i = 1; i < lisAdiacenta[x].size(); ++i) {
if(!viz[lisAdiacenta[x][i]]) {
viz[lisAdiacenta[x][i]] = 1;
coada.push(lisAdiacenta[x][i]);
}
}
}
return ultNod;
}
//BFS pentru a doua parcurgere - returnam distanta de la nodul obt cu BFS_final la ultimul din parc 2
int DistantaBFS2(vector<vector<int>> lisAdiacenta, const int S)
{
vector<bool> viz(lisAdiacenta.size()+1, 0);
queue<int> coada;
coada.push(S); viz[S] = 1;
int dist = 0;
while(!coada.empty()) {
int x = coada.front();
coada.pop();
dist++;
for(int i = 1; i < lisAdiacenta[x].size(); ++i) {
if(!viz[lisAdiacenta[x][i]]) {
viz[lisAdiacenta[x][i]] = 1;
coada.push(lisAdiacenta[x][i]);
}
}
}
return dist;
}
int main()
{
vector<vector<int>> lisAdiacenta;
Citire(lisAdiacenta);
int u1 = BFS_final(lisAdiacenta);
ofstream fout("darb.out");
fout << DistantaBFS2(lisAdiacenta, u1);
return 0;
}