Reconstruct a Tree from Pairwise Distances
Autumn Tournament (2010)
Submission name: recon.cpp
Problem summary
All labeled modules of a space station form a tree with positive integer corridor lengths. The distance between every pair of modules is known. Recover which pairs are directly connected, and print each module’s sorted neighbour list.
Input
N, then the upper triangle of the symmetric distance matrix: distances from 1 to 2…N, then from 2 to 3…N, and so on.
Output
N lines. Each gives a degree followed by its adjacent vertex numbers in increasing order. Corridor weights are not required in the output.
Constraints
3≤N≤1024; every supplied positive distance≤1024; the data comes from a tree on exactly these N modules.
Worked example
Original statement sample.
Input
5 5 14 3 7 13 2 6 11 7 4
Output
1 4 1 4 1 5 3 1 2 5 2 3 4
Solution analysis
- Treat every pair as an edge in a complete weighted graph, with its supplied tree distance as weight. Compute a minimum spanning tree of this complete graph. The result is exactly the original corridor tree; no intermediate unlabeled modules are introduced.
- Use dense Prim in O(N²): keep the cheapest connection from the current tree to each unchosen vertex, select the minimum, then update its N candidate distances. Store each selected parent edge in both adjacency lists and sort the lists before output.
- In the sample, Prim can choose 1–4 of length 3, 4–2 of length 2, 4–5 of length 4, and 5–3 of length 7. These give the requested lists: module 4 has neighbours 1,2,5, while module 5 has neighbours 3,4.
Why it works
For any non-corridor edge u–v in the complete graph, its weight is the sum of at least two positive original corridor lengths on the unique u–v path. It is strictly larger than every edge of that path. By the cycle property it cannot belong to an MST: adding it to the original tree makes it the unique heaviest cycle edge. Thus only original corridors can appear, and their N−1 edges form the unique MST.
Watch out. The argument requires positive lengths and a labeled vertex for every original module. Do not search all triples, which costs O(N³), or infer adjacency merely from the smallest distance in each row.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: For any non-corridor edge u–v in the complete graph, its weight is the sum of at least two
// positive original corridor lengths on the unique u–v path. It is strictly larger than every edge of
// that path.
#include<algorithm>
#include<iostream>
#include<limits>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<vector<int>>distance(n+1,vector<int>(n+1));
for(int a=1;a<=n;a++){
for(int b=a+1;b<=n;b++){
cin>>distance[a][b];
distance[b][a]=distance[a][b];
}
}
vector<int>best(n+1,numeric_limits<int>::max());
vector<int>parent(n+1,0);
vector<bool>chosen(n+1,false);
vector<vector<int>>graph(n+1);
best[1]=0;
for(int iteration=0;iteration<n;iteration++){
int vertex=0;
for(int candidate=1;candidate<=n;candidate++){
if(!chosen[candidate]&&(vertex==0||best[candidate]<best[vertex])){
vertex=candidate;
}
}
chosen[vertex]=true;
if(parent[vertex]!=0){
graph[vertex].push_back(parent[vertex]);
graph[parent[vertex]].push_back(vertex);
}
for(int next=1;next<=n;next++){
if(!chosen[next]&&distance[vertex][next]<best[next]){
best[next]=distance[vertex][next];
parent[next]=vertex;
}
}
}
for(int vertex=1;vertex<=n;vertex++){
sort(graph[vertex].begin(),graph[vertex].end());
cout<<graph[vertex].size();
for(int next:graph[vertex]){
cout<<' '<<next;
}
cout<<'\n';
}
}