Pagini recente » Cod sursa (job #2880105) | Borderou de evaluare (job #2088191) | Borderou de evaluare (job #1834186) | Cod sursa (job #1974309) | Cod sursa (job #3279423)
#include <iostream>
#include <fstream>
#include <queue>
#include <fstream>
using namespace std;
int maxi = 0;
vector<vector<int>> darb(const vector<vector<int>>& g) {
int n = g.size() - 1; // Nodes are 1-indexed
vector<vector<int>> dist(n + 1, vector<int>(n + 1, -1)); // Initialize to -1 (unreachable)
for (int start = 1; start <= n; ++start) {
queue<int> q;
q.push(start);
dist[start][start] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : g[u]) {
if (dist[start][v] == -1) { // Not visited yet
dist[start][v] = dist[start][u] + 1;
q.push(v);
if (dist[start][v] > maxi)
maxi = dist[start][v];
}
}
}
}
return dist;
}
int main()
{
ifstream in("darb.in");
ofstream out("darb.out");
int n, x, y;
in >> n;
vector<vector<int>> g(n+1);
vector<vector<int>> len(n+1);
while (in >> x >> y)
{
g[x].push_back(y);
g[y].push_back(x);
}
auto dist = darb(g);
/*for (int i = 1; i <= n; ++i)
{
cout << i << ": ";
for (int j = 1; j < dist[i].size(); ++j)
cout << dist[i][j] << ' ';
cout << '\n';
}*/
out << maxi + 1 << '\n';
in.close();
out.close();
return 0;
}