SRM 682 div1 med: SuccessfulMerger

問題

TopCoder Statistics - Problem Statement

解法

最終的には, スターグラフにして, その中心みたいな頂点を capital にすることになりますね。
Star Graph -- from Wolfram MathWorld

グラフは木 + 1 本の辺, という形をしていて, 1 つだけ閉路がありますが, まずこれを検出します。スターグラフっぽくするためには, まずこの閉路を 1 つの頂点にまとめます。そうすると, まとめられた頂点にいくつかの部分木がくっついているような形になりますが, これをスターグラフにするためには, 部分木の葉だけを残すことになりますが, 部分木の葉のみを残すためには, 閉路の長さを C として, n-C-(葉の数) だけ操作をする必要があります。

また, 閉路を一つの頂点にするための操作回数は C-1 なので, 結局答えは n-1-(葉の数) です。ただ, ひとつ例外があって, 閉路に含まれる頂点のどれかに, 「閉路に含まれる頂点以外と接続していない(その頂点から部分木が伸びていない)」という性質を満たすもの(v とします)があれば, 閉路をひとつの頂点に圧縮せず, v と閉路のどれかの頂点(u とします)を残して, u を capital にしたスターグラフができるので, 操作回数を 1 減らせます。

解法としてはそんな感じなんですが, 本番では閉路上の頂点を列挙するのをどうやるのかがよくわからず死にました。この問題に関しては, かみぺさんの方法がわかりやすかったです。
https://ideone.com/Vc7yHc
グラフの葉になっている部分を queue で格納して, 葉をどんどん消していきます。この作業をして消えなかった頂点が閉路を構成します。

class SuccessfulMerger {
public:
    int minimumMergers(vector <int> road) {
        int n = road.size();
        vector<vi> G(n);
        vector<int> degree(n, 0);
        for (int i = 0; i < n; i++) {
            degree[i]++;
            degree[road[i]]++;
            G[i].push_back(road[i]);
            G[road[i]].push_back(i);
        }
        queue<int> que;
        for (int i = 0; i < n; i++) {
            if (degree[i] == 1) {
                que.push(i);
                degree[i] = 0;
            }
        }
        while (!que.empty()) {
            int now = que.front(); que.pop();
            for (int ch : G[now]) {
                if (degree[ch] == 0) continue;
                if (--degree[ch] == 1) {
                    degree[ch] = 0;
                    que.push(ch);
                }
            }
        }
        bool minus = false;
        int ans = n-1;
        for (int i = 0; i < n; i++) {
            if (degree[i] > 0) {
                if (G[i].size() == 2) minus = true;
            } else {
                if (G[i].size() == 1) ans--;
            }
        }
        if (minus) ans--;
        return ans;
    }
};