847. Shortest Path Visiting All Nodes
Jul 29, 2024
class Solution {
public:
struct DSU {
vector<int> sz, f;
DSU (int n) {
sz.assign(n, 1);
f.resize(n);
iota(f.begin(), f.end(), 0);
}
int find(int x) {
while (x!=f[x]) {
x = f[x] = f[f[x]];
}
return x;
}
bool same(int x, int y) {
return find(x)==find(y);
}
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x==y) return false;
sz[x] += sz[y];
f[y] = x;
return true;
}
};
int shortestPathLength(vector<vector<int>>& graph) {
int n = graph.size();
DSU dsu(n);
vector<vector<int>> mst(n);
for (ll i=0; i<n; i++) {
for (ll j : graph[i]) if (merge(i, j)) {
mst[i].push_back(j);
mst[j].push_back(i);
}
}
auto dfs = [&] (int n, int p, auto&& dfs) {
int mx = 0;
for (ll c : mst[n]) if (c!=p) {
mx = max(mx, dfs(c, n, dfs));
}
return mx + 1;
};
vector<int> height;
for (int c : graph[0]) {
height.push_back(dfs(c, n, dfs));
}
sort(height.begin(), height.end());
int ans = 2*(n-1);
int N = height.size();
for (int i=max(0, N-2); i<N; i++) {
ans -= height[i];
}
cout << ans << endl;
}
};
Comments