Manthan, Codefest 18 (rated, Div. 1 + Div. 2): E. Trips
解法
逆からやる(典型)。 $O(N + M)$。
それぞれの日の夜の時点で「次数$\lt k$な頂点を再帰的に削除し残る頂点の数」が答え。 これを日付けの正順でやると毎回すべて頂点があるところからの削除が必要だが、日付けの逆順でやれば結果を使い回せて計算量が落ちる。
メモ
- 連想された問題: TopCoder SRM 736 Div1 Medium: MinDegreeSubgraph
実装
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = int(n) - 1; (i) >= 0; -- (i))
using namespace std;
vector<int> solve(int n, int m, int k, vector<pair<int, int> > const & edges) {
vector<set<int> > g(n);
for (auto edge : edges) {
int x, y; tie(x, y) = edge;
g[x].insert(y);
g[y].insert(x);
}
vector<bool> used(n, true);
int cnt = n;
function<void (int)> unuse = [&](int x) {
if (not used[x]) return;
if (g[x].size() >= k) return;
used[x] = false;
-- cnt;
for (int y : g[x]) {
g[y].erase(x);
unuse(y);
}
g[x].clear();
};
REP (x, n) {
unuse(x);
}
vector<int> answer(m, -1);
REP_R (j, m) {
answer[j] = cnt;
int x, y; tie(x, y) = edges[j];
g[x].erase(y);
g[y].erase(x);
unuse(x);
unuse(y);
}
return answer;
}
int main() {
// input
int n, m, k; scanf("%d%d%d", &n, &m, &k);
vector<pair<int, int> > edges(m);
REP (i, m) {
int x, y; scanf("%d%d", &x, &y);
-- x;
-- y;
edges[i] = make_pair(x, y);
}
// solve
auto answer = solve(n, m, k, edges);
// output
REP (i, m) {
printf("%d\n", answer[i]);
}
return 0;
}