P10179 题解

FantasySegmentTree · 2024-02-20 08:54:23 · 题解

题意

你要构造一颗 n 个点的树，使得在树上所有输入的 (u, v) 点对在树上的距离为 2。

思路

首先，我们可以先求出每一个点在哪一个点集合里，这一步可以使用并查集。

对于只有一个集合的情况，每相邻两个节点的距离都是2，不可能实现，输出 No。

其次，距离为 2 的点只有爷爷和孙子或者兄弟。

所以我们可以先取出一个集合中的根节点，随后把其他集合的所有点都与这个点相连，这样就解决了其他集合（兄弟），随后找一个其他集合的点，把所有这个集合中的点全部与这个点相连，这样就解决了这个集合（爷爷和孙子）。

边连边输出即可。

代码

#include <iostream>
using namespace std;

int T, n, m, fa[300005], cnt[300005], jl[300005], flag;

int find(int x) {
    if(fa[x] == x) return x;
    else return fa[x] = find(fa[x]);
}

void init() {
    for(int i = 1; i <= n; i++) fa[i] = i;
    for(int i = 1; i <= n; i++) jl[i] = 0;
}

int main() {
    cin >> T;
    while(T--) {
        cin >> n >> m;
        init();
        int flag = 0;
        for(int i = 1; i <= m; i++) {
            int u, v;
            cin >> u >> v;
            int x = find(u), y = find(v);
            if(x != y) {
                fa[x] = y;
            } else {
                flag = 1;
            }
        }
        for(int i = 1; i <= n; i++) jl[find(i)]++;
        int fla = 0, cnt = 0;
        for(int i = 1; i <= n; i++) {
            if(jl[i]) {
                fla = i;
                cnt++;
            }
        }
        if(cnt == 1) {
            cout << "No\n";
            continue;
        }   
        int flagg = 1;
        while (find(flagg) == find(fla)) flagg++;
        cout << "Yes\n";
        for(int i = 1; i <= n; i++) {
            if(find(i) != fla) {
                cout << fla << " " << i << endl;
            }
        }
        for(int i = 1; i <= n; i++) {
            if(find(i) == fla && i != fla) {
                cout << flagg << " " << i << endl;
            }
        }
    }
}