分割統治 [ACM-ICPC JAG 模擬国内予選 2018年 E]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/JAG/Prelim/2885

前提知識

• 二部グラフ判定

考察

1. 最初のサンプルを図示してみると二部グラフ感がすごい
2. 二部グラフとして考えてみると、片方がAなら片方は必ずC, 片方がBなら片方は必ずCになるといえる
3. 二部グラフ判定をして2グループに分けたときに、1つはCだけ、もう1つはABとなる
4. AとBの要素数は等しいので、偶数個のグループを2つに分けることができる
5. 解けた

解法

https://onlinejudge.u-aizu.ac.jp/solutions/problem/2885/review/2994344/hamayanhamayan/C++14

二部グラフ判定をするにはdfsで貪欲に塗っていけばいい。
矛盾が生まれれば二部グラフではない。
答えのために2つのグループの個数も同時に数えておこう。
　
あとは、二部グラフであれば、2つのグループの個数の中で偶数の物の半分を答える。

int N, M;
vector<int> E[1010];
//---------------------------------------------------------------------------------------------------
int col[1010];
pair<int, int> dfs(int cu = 0, int c = 0) {
    pair<int, int> res = { 0, 0 };

    col[cu] = c;
    if (c == 0) res.first++;
    else res.second++;

    fore(to, E[cu]) {
        if (col[to] < 0) {
            auto p = dfs(to, 1 - c);
            if (p.first < 0) return { -1, -1 };

            res.first += p.first;
            res.second += p.second;
        }
        else {
            if (col[cu] == col[to]) return { -1, -1 };
        }
    }

    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    while (cin >> N >> M) {
        if (N == 0) return;
        rep(i, 0, N) E[i].clear();
        rep(i, 0, N) col[i] = -1;

        rep(i, 0, M) {
            int a, b; cin >> a >> b;
            a--; b--;
            E[a].push_back(b);
            E[b].push_back(a);
        }

        auto p = dfs();
        if (p.first < 0) {
            printf("0\n");
            continue;
        }

        set<int> ans;
        if(p.first % 2 == 0) ans.insert(p.first / 2);
        if (p.second % 2 == 0) ans.insert(p.second / 2);

        int n = ans.size();
        printf("%d\n", n);
        fore(i, ans) printf("%d\n", i);
    }
}