#include <algorithm>
#include <iostream>
#include <map>
#include <utility>
using namespace std;
int main() {
int N; // the number of adjacency relations
cin >> N;
map<int, map<int, int>> adj; // map<xi, map<yi, distance>>
for (int i = 0; i < N; i++) {
int xi, // the ID of a person which is adjacent to yi
yi; // the ID of a person which is adjacent to xi
cin >> xi >> yi;
// adj[xi][xi] = adj[yi][yi] = 0;
adj[xi][yi] = adj[yi][xi] = 1;
for (auto x : adj[xi])
if (yi != x.first && (!adj[yi][x.first] || adj[yi][x.first] > x.second + 1))
adj[yi][x.first] = adj[x.first][yi] = x.second + 1;
for (auto y : adj[yi])
if (xi != y.first && (!adj[xi][y.first] || adj[xi][y.first] > y.second + 1))
adj[xi][y.first] = adj[y.first][xi] = y.second + 1;
}
/*// Debug
for (const auto& x : adj) {
cerr << "From " << x.first << ":\n";
for (const auto& y: x.second)
cerr << "\tto " << y.first << ": " << y.second << "\n";
}*/
int res {-1};
for (const auto& x : adj) {
const int required_steps {max_element(x.second.cbegin(), x.second.cend(), [] (pair<int, int> a, pair<int, int> b) {return a.second < b.second;})->second};
if (res > required_steps || res == -1)
res = required_steps;
}
cout << res << endl;
return 0;
}
Sorry for using nested maps with graphs, I know it’s gross.
Basically, each time I get a new input I update the graph to turn it into a complete graph; finally, I look for the minimum maximum edge weight.
- The first three testcases work just fine.
- Testcases 4-7 and 10 output wrong results.
- Also, testcases 8-9 cause a timeout, but I’d like to debug first.
Thanks for your time!