CF1133F2

FiraCode · 2024-01-10 19:14:10 · 题解

思路：

可以先考虑将不经过一号点的连通分量找出来。

然后若连通分量个数 >D 则无解（因为无法通过选 D 条边而使其联通）。

否则对于 1 连接每个连通分量的边任选一条，然后剩余的边随便选即可。

最后对于每个和 1 相连的点，从他 dfs 一遍，当然不经过 1 节点，对于每个点若当前位于它联通就将这条边加上并继续 dfs，否则跳过。

Code：

代码写的有点丑（

#include <bits/stdc++.h>

using namespace std;

int n, m, D;
int idx, st[200010];
vector<int> e[200010];
int vis[200010], stt[200010];
map<pair<int, int>, int> ma1;

void dfs(int u) {
    st[u] = idx;
    for (auto v : e[u]) {
        if (v != 1 && !st[v]) {
            dfs(v);
        }
    }
}

void dfs1(int u) {
    vis[u] = 1;
    for (auto v : e[u]) {
        if (v != 1 && !vis[v]) {
            // cout << u << ' ' << v << "---\n";
            ma1[{u, v}] = 1;
            dfs1(v);
        }
    }
}

int main() {
    scanf("%d%d%d", &n, &m, &D);
    for (int i = 1; i <= m; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        if (u > v) swap(u, v);
        e[u].push_back(v);
        e[v].push_back(u);
    }

    if (e[1].size() < D) {
        puts("NO");
        // cout << 1 << endl;
        return 0;
    }

    for (auto v : e[1])
        if (!st[v]) {
            ++idx;
            dfs(v); 
        }

    for (auto v : e[1]) {
        if (stt[st[v]]) continue;
        stt[st[v]] = true;
        --D;
        if (D < 0) {
            puts("NO");
            return 0;
        }
        vis[v] = true;
        ma1[{1, v}] = 1;
    }

    for (auto v : e[1]) {
        if (D) {
            if (!vis[v]) {
                vis[v] = true;
                --D;
                ma1[{1, v}] = true;
            }
        }
    }

    puts("YES");

    for (auto v : e[1]){
        if (ma1.count({1, v})) {
            // cout << v << endl;
            dfs1(v);
        }
    }

    for (auto [u, v] : ma1) printf("%d %d\n", u.first, u.second);
    return 0;
}