AtCoderBeginnerContest239 F問題500点 「Construct Highway」
https://gyazo.com/83df7a2ec990e4b4f64f261c77fc730d
問題概要
制約
$ N \leq 10^5
気持ち
解法
連結成分ごとに「足りていない辺の数」の和を$ c_iとします。（$ iは$ i個目の連結成分）
このとき、以下のような手順で建設できます。
$ c_i \geq 2であるような連結成分と、$ c_j = 1であるような連結成分を結び、それぞれの連結成分の足りていない辺の数を１ずつ減らす（$ c_i \leftarrow c_i - 1）
もし上記のような $ c_i \geq 2の連結成分がない場合、$ c_i=2の連結成分がちょうど2つあるならばそれらを結ぶ
計算量
$ O(N)
新たな学び
まとめて管理できる
反省点
一つの考えに固執しない
頂点ごとにソートして計算しており、バグしか疑ってなかった
反例が見つからなくても、別のアイディアを幅広く考えたほうがよい コード
code: cpp
struct UnionFind {
vector<int> par;
vector<int> sizes;
UnionFind(int n) : par(n), sizes(n, 1) {
for (int i = 0; i < n; i++) {
}
}
int find(int x) { return x == parx ? x : parx = find(parx); } bool unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return false;
if (sizesx < sizesy) swap(x, y); return true;
}
bool same(int x, int y) { return find(x) == find(y); }
int get_size(int x) { return sizesfind(x); } bool all_same() {
bool good = true;
for (int i = 0, n = par.size(); i < n; i++)
if (find(0) != find(i)) good = false;
return good;
}
int get_connectivity() {
set<int> s;
for (int i = 0, n = par.size(); i < n; i++) s.insert(find(i));
return s.size();
}
};
int main() {
int N, M;
cin >> N >> M;
vector<int> D(N);
cin >> D;
if (accumulate(D.begin(), D.end(), 0) != 2 * (N - 1)) {
cout << "-1" << endl;
return 0;
}
UnionFind UF(N);
for (int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
a--, b--;
UF.unite(a, b);
}
vector<vector<int>> cur(N);
for (int i = 0; i < N; i++) {
cout << "-1" << endl;
return 0;
}
for (int j = 0; j < Di; j++) { }
}
vector<int> c1;
vector<vector<int>> c2;
for (int i = 0; i < N; i++) {
else if (curi.size() > 1) }
vector<pair<int, int>> ans;
for (auto dp : c2) {
for (int i = 0; i < (int)dp.size() - 1; i++) {
if (c1.empty()) {
cout << "-1" << endl;
return 0;
}
UF.unite(dpi, c1.back()); ans.push_back({dpi, c1.back()}); c1.pop_back();
}
c1.push_back(dp.back());
}
if (c1.size() != 2) {
cout << "-1" << endl;
return 0;
}
ans.push_back({c10, c11}); if (UF.get_size(0) == N) {
for (auto a : ans) {
cout << a.first + 1 << " " << a.second + 1 << endl;
}
} else {
cout << "-1" << endl;
return 0;
}
}