K - Treeland Gym - 100513K（图论）

Nadia ·

更新时间:2024-11-13

· 880 次阅读

Treeland is an ancient country located on the territory of the modern Berland many many years ago. It is a well-known fact that Treeland consisted of n cities connected with n - 1 bidirectional roads. It was possible to travel from any city to any other one along the roads. The cities were numbered from 1 to n.

Nowadays we do not know what cities were connected by roads directly, but recently archaeologists have found new information that can help to reconstruct the road network of Treeland.

They found an ancient library with the diaries of a well-known traveler Biklouho-Baclay. The diaries contain interesting information: for each city i there is a list of all cities in the order of non-decreasing distance from i. The distances are calculated assuming that each road has length 1, so a distance between cities is the minimum number of roads to travel between them.

Formally, for each city i there is a list containing a permutation of cities (numbers from 1 to n) in such order that d(i, c i, j) ≤ d(i, c i, j + 1) for every j = 1… n - 1, where d(x, y) is a distance between cities x and y. Obviously, c i, 1 = i for each i. The cities that are equidistant from i can be listed in any order.

Your task is to restore a possible road network consistent with the found lists.

Input
The input consists of several test cases. The first line contains integer number t (1 ≤ t ≤ 1000) — the number of test cases.

Then t blocks follow, each describing a single test case. The first line of a block contains integer number n (2 ≤ n ≤ 2000) — the number of cities. The following n lines contain lists C i, one list per line.

It is guaranteed that the required road network exists for each test case. The sum of n over all test cases doesn’t exceed 2000.

Output
For each test case print n - 1 lines describing roads. Each line should contain a pair of cities connected with a road. You may print the roads and cities in a pair in any order. Print a blank line after the output of a test case.

If there are many solutions, print any of them.

Examples
Input
3
2
1 2
2 1
5
1 4 5 3 2
2 3 4 1 5
3 4 2 5 1
4 3 1 5 2
5 4 3 1 2
3
1 3 2
2 1 3
3 1 2
Output
2 1

2 3
3 4
5 4
4 1

2 1
3 1

题意：
一棵树，边权为1，给出每个点到其他点远近的排序，求出这n-1条边。

思路：
看群里讨论的，因为距离每个点最远的一个点，一定是叶子节点，那么叶子节点和对应的最近点间一定有一条边。然后删去叶子节点，再次寻找叶子节点。并且可以确定一个根节点，确定当前根节点，循环一次即可。

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 2007;
int a[maxn][maxn],vis[maxn];
map<pair,int>mp;
vector<pair >ans;
void add(int x,int y) {
    if(mp[{x,y}]) return;
    ans.push_back({x,y});
    mp[{x,y}] = mp[{y,x}] = 1;
}
int main() {
    int T;scanf("%d",&T);
    while(T--) {
        memset(vis,0,sizeof(vis));
        ans.clear();mp.clear();
        int n;scanf("%d",&n);
        for(int i = 1;i <= n;i++) {
            for(int j = 1;j <= n;j++) {
                scanf("%d",&a[i][j]);
            }
        }
        for(int i = 1;i <= n;i++) {
            if(ans.size() == n - 1) break;
            int x = a[1][n - i + 1];//叶子
            for(int j = 2;j <= n;j++) {
                if(vis[a[x][j]]) continue;
                else {
                    add(x,a[x][j]);
                    break;
                }
            }
            vis[a[1][n - i + 1]] = 1;
        }
        for(int i = 0;i < n - 1;i++) {
            printf("%d %d\n",ans[i].first,ans[i].second);
        }
        printf("\n\n\n");
    }
    return 0;
}