The town numbers can be given in an arbitrary order.

If more than one solution exists, any solution can be printed.

提供本题 SPJ

#include <bitset>
#include "testlib.h"
using namespace std;
int n, m, k, r;
const int maxn = 5e5 + 5, maxm = 1e6 + 5;
bitset<maxn> vis;
struct edge {
    int v;
    int n;
} e[maxm << 1];
int head[maxn], tot = 0;
inline void link(int u, int v) {
    e[++tot] = (edge){v, head[u]};
    head[u] = tot;
}
int u, v, t;
void dfs(int u, int f, int dep) {
    vis[u] = true;
    if (dep == 2) return;
    for (int i = head[u]; i; i = e[i].n) {
        v = e[i].v;
        if (v != f) dfs(v, u, dep + 1);
    }
}
bool ispe = false;
int main(int argc, char** argv) {
    registerTestlibCmd(argc, argv);
    n = inf.readInt(), m = inf.readInt(), k = inf.readInt();
    if (ouf.eof()) {
        quitf(
            _wa,
            "Wrong Anwser. Parameter r not found. You should check your output "
            "function, qwq.");
        return 0;
    }
    r = ouf.readInt();
    if (r > k) {
        quitf(_wa,
              "Wrong Anwser. You can't erect more than %d towers, but you "
              "have erected %d towers. Don't give up, qwq.",
              k, r);
        return 0;
    }
    for (int i = 1; i <= m; ++i) {
        u = inf.readInt(), v = inf.readInt();
        link(u, v), link(v, u);
    }
    while (ouf.curChar() == ' ') ouf.skipChar();
    if (!ouf.eoln()) ispe = true;
    for (int i = 1; i <= r; ++i) {
        while (ouf.curChar() == ' ') ouf.skipChar();
        if (ouf.eof()) {
            quitf(_wa,
                  "Wrong Anwser. More output needed, you should erect %d "
                  "towers, but %d erected. So how did you get r, @_@?",
                  r, i - 1);
            return 0;
        }
        if (ouf.eoln()) ispe = true;
        t = ouf.readInt();
        dfs(t, -1, 0);
    }
    inf.skipBlanks(), ouf.skipBlanks();
    if (!ouf.eof()) {
        quitf(_wa, "Wrong Anwser. Too much output, @_@.");
        return 0;
    }
    inf.readEof(), ouf.readEof();
    if (vis.count() != n)
        quitf(_wa,
              "Wrong Anwser. You still have %d points that you haven't "
              "covered. Try again, qwq.",
              n - vis.count());
    else if (ispe)
        quitf(_pe, "Presentation Error. SPJ is not stupid, >.<.");
    else
        quitf(_ok, "Accept. Good job, orz.");
    return 0;
}