こういうの苦手。。。

問題概要

整数 k と、N 頂点 0 辺のグラフが最初に与えられる。以下の M 個のクエリに答えよ。

a, b: 辺 (a, b) を追加する。この時点でグラフの各頂点を以下の条件を満たすように白黒に塗る「任意の黒い頂点は、隣接する黒い頂点を少なくとも k 個以上もつ」

考えたこと

まず単体のグラフについて上記のクエリに答えることを考えてみる。実は以下のような Greedy でよい

「グラフに次数 k 未満の頂点が残っているならば、その頂点および隣接する辺をすべて削除する」というのを繰り返す

この操作で削除される頂点は明らかに黒く塗ることはできない。またこの操作を終えて残ったグラフは

次数がすべて k 以上

という特徴をもつので、すべて黒く塗ることで条件を満たすことができる。これが黒く塗れる頂点数の最大数である。

次に、クエリを処理していくことを考える。上記の操作は毎回 $O(N+M)$ の計算時間を要するため、このままでは間に合わない。よってクエリを差分更新することを考えたい。しかし「辺を追加する」という条件を上手く扱うのは難しそうである。

そこで、発想を逆転して、「クエリを後ろから処理する」という風にしてみる。そうすると、上記の Greedy ととても相性がいい。辺を削除するたびに「新たに次数 k 未満の頂点が生じたら、上記の Greedy を繰り返す」という風にすればいい。

この操作で削除される頂点数・辺数はクエリ全体を通して $O(N+M)$ なので、結局全体の計算量は $O(N+M+Q)$ でおさまる。

#include <iostream>
#include <vector>
#include <set>
#include <queue>
using namespace std;

typedef pair<int,int> pint; // (node, edge-index)

int N, M, K;
vector<set<pint> > G;  // graph
vector<int> U, V;      // the i-th edge

int main() {
    cin >> N >> M >> K;
    G.clear(); G.resize(N); U.resize(M); V.resize(M);
    for (int i = 0; i < M; ++i) {
        scanf("%d %d", &U[i], &V[i]);
        --U[i], --V[i];
        G[U[i]].insert(pint(V[i], i));
        G[V[i]].insert(pint(U[i], i));
    }

    // get the final answer
    queue<int> dame;
    vector<int> isbad(N, 0); // bad-nodes
    for (int i = 0; i < N; ++i) if (G[i].size() < K) dame.push(i), isbad[i] = true;

    // erase dame-nodes
    vector<int> isbroken(M, 0); // bad-edges
    int cur_good_nums = N;
    while (!dame.empty()) {
        int v = dame.front(); dame.pop();
        --cur_good_nums;
        for (auto e : G[v]) {
            int nv = e.first;
            int nid = e.second;
            //G[v].erase(pint(nv, nid));
            G[nv].erase(pint(v, nid));
            isbroken[nid] = true;
            if (!isbad[nv] && G[nv].size() < K) {
                dame.push(nv);
                isbad[nv] = true;
            }
        }
        G[v].clear();
    }
    
    // back
    vector<int> res(M);
    for (int i = M-1; i >= 0; --i) {
        res[i] = cur_good_nums;

        // erase i-th edge
        if (isbroken[i]) continue;
        int u = U[i], v = V[i];
        G[u].erase(pint(v, i));
        G[v].erase(pint(u, i));
        if (!isbad[u] && G[u].size() < K) dame.push(u), isbad[u] = true;
        if (!isbad[v] && G[v].size() < K) dame.push(v), isbad[v] = true;
        while (!dame.empty()) {
            int v = dame.front(); dame.pop();
            --cur_good_nums;
            for (auto e : G[v]) {
                int nv = e.first;
                int nid = e.second;
                //G[v].erase(pint(nv, nid));
                G[nv].erase(pint(v, nid));
                isbroken[nid] = true;
                if (!isbad[nv] && G[nv].size() < K) {
                    dame.push(nv);
                    isbad[nv] = true;
                }
            }
            G[v].clear();
        }
    }

    // print
    for (int i = 0; i < M; ++i) cout << res[i] << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Codeforces Manthan Codefest 18 (Div. 1 + Div. 2) E. Trips (R2100)

問題概要

考えたこと