Official
E - Blackout 2 Editorial by nok0
大まかな方針は物理好きさんの公式解説と同様です。
ここでは少しの考察を行うことで実装を簡潔にする方法を紹介します。
問題で求められていたのは、いずれかの発電所と連結な都市の個数であり、発電所の区別はないことに注意します。このことから、発電所を全て同一視しても問題ないことがわかります。
すると、発電所と連結な都市の個数は単純に uf.size(発電所)
\(-1\) で取得でき、頂点の重みの管理といった複雑な実装が不要となります。
実装例(c++):
#include <bits/stdc++.h>
#include <atcoder/dsu>
using namespace std;
int main() {
int n, m, e;
cin >> n >> m >> e;
vector<pair<int, int>> uv;
for(int i = 0; i < e; i++) {
int u, v;
cin >> u >> v;
--u, --v;
//発電所を全て地点 N と同一視しています
uv.emplace_back(min(u, n), min(v, n));
}
int q;
cin >> q;
vector query(q, 0);
for(auto &v : query) cin >> v, --v;
vector def_edges(e, true);
for(auto v : query) def_edges[v] = false;
atcoder::dsu uf(n + 1);
for(int i = 0; i < e; i++) {
if(def_edges[i]) {
auto [u, v] = uv[i];
uf.merge(u, v);
}
}
vector<int> ans(q);
for(int i = q - 1; i >= 0; i--) {
ans[i] = uf.size(n) - 1;
auto [u, v] = uv[query[i]];
uf.merge(u, v);
}
for(auto v : ans) cout << v << endl;
}
posted:
last update: