Independence [AtCoder Regular Contest 099 E]

https://beta.atcoder.jp/contests/arc099/tasks/arc099_c

前提知識

• 二部グラフ判定

考察

1. 2つのグループに分けるという所が二部グラフを連想させる
2. なんとか二部グラフに帰着させたい
3. ある二頂点間に辺が無い場合は、その二頂点は違うグループになる
4. 違うグループということは二部グラフ！
5. 補グラフが二部グラフになれば分けることができそう
6. 補グラフの連結成分について2グループに分けて、その個数を高州と橋州にうまく分類して最小値を求める
7. これはDPでいける

解説

https://beta.atcoder.jp/contests/arc099/submissions/2736602

まずは与えられたグラフの補グラフをとろう。
補グラフとは、もともとのグラフの辺があるところは無し、辺が無いところはありにしたグラフである。
このグラフについて二部グラフであるかを判定しよう。
　
二部グラフ判定はdfsで貪欲に2色に塗っていく。
途中で矛盾が生まれれば二部グラフではない、矛盾がなければ二部グラフである。
　
補グラフで連結成分が複数ある場合は、高州と橋州のどちらに入れるかで答えの辺の個数が異なってくる。
そのため、連結成分について、2つのグループの個数を数えておこう。
　
最後は以下のdpで答えを求める。
dp[i][cn] := i番目までの連結成分で高州にcn個の都市が属している状況があるか
このdpを使ってあり得る高州と橋州の分割後の個数を全探索して、個数が最小のものを答えとしよう。

int N, M;
int _E[707][707];
vector<int> E[707];
//---------------------------------------------------------------------------------------------------
int vis[707], col[707];
pair<int, int> dfs(int cu, int co = 0) {
    vis[cu] = 1;
    col[cu] = co;
 
    pair<int, int> res = { 0, 0 };
 
    if (co == 0) res.first++;
    else res.second++;
 
    fore(to, E[cu]) {
        if (vis[to]) {
            if (col[to] == co) return { -1, -1 };
        } else {
            auto p = dfs(to, 1 - co);
            if (p.first < 0) return { -1,-1 };
            res.first += p.first;
            res.second += p.second;
        }
    }
 
    return res;
}
//---------------------------------------------------------------------------------------------------
int dp[707][1007];
void _main() {
    cin >> N >> M;
    rep(i, 0, M) {
        int a, b; cin >> a >> b;
        a--; b--;
        _E[a][b] = _E[b][a] = 1;
    }
    rep(i, 0, N) rep(j, 0, N) if (!_E[i][j] and i != j) E[i].push_back(j);
 
    vector<pair<int, int>> v;
    rep(i, 0, N) if (!vis[i]) {
        auto p = dfs(i);
        if (p.first < 0) {
            printf("-1\n");
            return;
        }
        v.push_back(p);
    }
 
    int n = v.size();
    dp[0][0] = 1;
    rep(i, 0, n) rep(cn, 0, 707) if(dp[i][cn]) {
        dp[i+1][cn + v[i].first] = 1;
        dp[i+1][cn + v[i].second] = 1;
    }
 
    int ans = inf;
    rep(cn, 0, 707) if(dp[n][cn]) {
        int taka = cn;
        int hashi = N - cn;
        chmin(ans, taka * (taka - 1) / 2 + hashi * (hashi - 1) / 2);
    }
    cout << ans << endl;
}