翻译:给定 \(n,m\) 和度数数组 \(\{d_i\}\),再给你 \(m\) 条边,请构造一棵 \(n\) 点的树包含这 \(m\) 条边,且第 \(i\) 个点的度数为 \(d_i\),或者判断无解。
显然,若 \(\sum d_i\ne 2(n-1)\),则无解。
然后对于输入的每条边,使用并查集维护,再求出在这 \(m\) 条边的基础上每个点还需要多少度数(记作 \(d_i\),注意下文 \(d_i\) 的意义与输入不同)。
如果存在 \(d_i < 0\),则无解。
然后考虑每个连通块,维护一个 vector 表示这个连通块中每个点还需要多少度数,若 \(u\) 需要 \(k\) 的度数就存 \(k\) 个 \(u\)。
将所有连通块分为两类:需要度数 \(1\)、需要度数 \(\ge 2\),下文分别称为“第一类”“第二类”。
第一类连通块显然要优先跟第二类连通块连(不然就不连通了)。我们枚举每个第二类连通块,假设这个连通块还需要 \(d\) 的度数,那么拿出 \(d-1\) 的度数连第一类连通块,剩下 \(1\) 的度数会使得这个连通块被归入第一类中。
如果某一时刻第一类连通块不够了,就无解。如果所有第二类连通块都用完了,此时剩下超过 \(2\) 个第一类连通块,就也无解。否则,此时会恰好剩下两个第一类连通块,连起来即可。最后判一下整个图是否连通,不连通还无解。否则输出即可。
这题无解情况挺多的,容易漏情况,写代码之前要想清楚。
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
uniform_int_distribution<int> dist(L, R);
return dist(rnd);
}
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
const int N = 2e5+5;
int n, m, deg[N];
vector<int> nds[N], nd1;
vector<vector<int>> nd2;
vector<tuple<int, int>> ans;
struct Dsu {
int fa[N];
void init(int x) {rep(i, 1, x) fa[i] = i;}
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
bool same(int x, int y) {return find(x) == find(y);}
bool merge(int x, int y) {
if(same(x, y)) return false;
x = find(x); y = find(y);
fa[x] = y;
return true;
}
}dsu;
int main() {
scanf("%d%d", &n, &m);
rep(i, 1, n) scanf("%d", °[i]);
if(accumulate(deg+1, deg+1+n, 0) != 2 * (n - 1)) return puts("-1")&0;
dsu.init(n);
rep(i, 1, m) {
int u, v;
scanf("%d%d", &u, &v);
dsu.merge(u, v);
--deg[u]; --deg[v];
if(deg[u] < 0 || deg[v] < 0) return puts("-1")&0;
}
rep(i, 1, n) rep(j, 1, deg[i]) nds[dsu.find(i)].push_back(i);
rep(i, 1, n) {
if((int)nds[i].size() == 1) nd1.push_back(nds[i][0]);
if((int)nds[i].size() > 1) nd2.push_back(nds[i]);
}
for(auto&& i : nd2) {
for(int j = 1; j < (int)i.size(); j++) {
if(nd1.empty()) return puts("-1")&0;
dsu.merge(i[j], nd1.back());
ans.emplace_back(i[j], nd1.back());
nd1.pop_back();
}
nd1.push_back(i[0]);
}
if((int)nd1.size() > 2) return puts("-1")&0;
dsu.merge(nd1[0], nd1[1]);
ans.emplace_back(nd1[0], nd1[1]);
rep(i, 1, n) if(!dsu.same(i, 1)) return puts("-1")&0;
for(auto&& [u, v] : ans) printf("%d %d\n", u, v);
return 0;
}
标签:连通,ABC239F,return,int,题解,back,nd1,Highway,deg
From: https://www.cnblogs.com/ruierqwq/p/abc239f.html