Pagini recente » Cod sursa (job #630563) | Cod sursa (job #65649) | Cod sursa (job #2979179) | Cod sursa (job #2120492) | Cod sursa (job #3295739)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
#define INF 1 << 30
void read_input(int& n, vector<vector<int>>& adj) {
ifstream fin("darb.in");
fin >> n;
adj.resize(n + 1);
int x, y;
// Arborele este un graf neorientat
for (int i = 0; i < n - 1; i++) {
fin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
fin.close();
}
// BFS care porneste dintr-un nod dat si returneaza o pereche cu:
// cel mai indepartat nod in care poate ajunge si distanta pana la acesta
pair <int, int> bfs_farthest(int node, int n, vector<vector<int>>& adj) {
vector<int> dist(n + 1, INF);
queue<int> q;
dist[node] = 0;
q.push(node);
while (!q.empty()) {
int node = q.front();
q.pop();
for (int neigh : adj[node]) {
if (dist[neigh] == INF) {
dist[neigh] = dist[node] + 1;
q.push(neigh);
}
}
}
int far_node = node;
int max_dist = 0;
for (int u = 1; u <= n; u++) {
if (dist[u] > max_dist) {
max_dist = dist[u];
far_node = u;
}
}
return {far_node, max_dist};
}
void print_output(const int& diam) {
ofstream fout ("darb.out");
fout << diam << endl;
fout.close();
}
int main() {
int n;
vector<vector<int>> adj;
read_input(n, adj);
// 1) pornesc un BFS dintr-un nod oarecare (1)
pair <int, int> p1 = bfs_farthest(1, n, adj);
int farthest_node = p1.first;
// 2) pornesc un DFS din nodul gasit, pentru a obtine diametru
pair<int, int> p2 = bfs_farthest(farthest_node, n, adj);
int diametru_in_nodes = p2.second + 1;
print_output(diametru_in_nodes);
return 0;
}