Xmas Contest 2015 夜の部 B - Broken Christmas Tree

問題

xmascontest2015.contest.atcoder.jp

解法

S: (禁止されている辺の集合), unvisit: (現時点でまだ訪れていない頂点の集合) とします。

で, ある頂点 v に訪れた時は, unvisit の頂点を見ていって, (u, v) が S に含まれるものでなかったら v -> u に辺を追加して u をさらに探索する, というようにすれば OK です。
計算量が O(N^2) かかると思うかもしれませんが, 辺を貼ろうとして NG になることは O(M) 回しか起こらないので O(NlogN + MlogM) くらいで出来そうです(若干適当)。

実装するときの注意ですが, これは dfs でやると難しいと思います(出来るかもだけど個人的には断念した)。
この問題では unvisit を set で管理する必要がありますが, dfs でやると, v -> u と訪れた時 unvisit からどれだけ頂点が削除されたかがわからないので u から帰ってきた後のイテレータがどこを指してるのかわからず探索を続行するのが難しそうです。

一方で, 幅優先探索でやると v -> u に辺を貼ることが確定した後も v で探索を続けるので, unvisit の情報が壊れることはないです。

set<pii> S;
set<int> unvisit;
const int MAX = 200020;

bool ok(int u, int v) {
    if (u > v) swap(u, v);
    return (S.find(pii(u, v)) == S.end());
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    for (int i = 1; i < N; i++) unvisit.insert(i);
    for (int i = 0; i < M; i++) {
        int p, q;
        cin >> p >> q;
        p--; q--;
        if (p > q) swap(p, q);
        S.insert(pii(p, q));
    }
    queue<int> que;
    que.push(0);
    vector<pii> ans;
    while (!que.empty()) {
        int now = que.front(); que.pop();
        auto it = unvisit.begin();
        while (it != unvisit.end()) {
            int u = *it;
            if (ok(u, now)) {
                ans.emplace_back(u, now);
                it = unvisit.erase(it);
                que.push(u);
            } else it++;
        }
    }
    if (!unvisit.empty()) {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
        for (pii p : ans) {
            cout << p.first+1 << " " << p.second+1 << endl;
        }
    }
    return 0;
}